CF1866M

· · 题解

CF1866M

这篇题解较为详细地展示了 dp 式子的化简过程。

由于石子必须一个一个堆上去，所以设 f_i 表示从第 i-1 层堆到第 i 层的期望次数。

分两种情况转移：掉到非零层，掉到第零层。

转移时考虑这次堆叠掉落到了那一层，初始 f_0=0。

f_i=1+\sum_{j=1}^{i-1}({P_i}^{i-j}(1-P_i)\sum_{k=j+1}^{i}f_k)+{P_i}^{i}\sum_{j=1}^{i}f_j

把 (1-P_i) 拆开，得到：

f_i=1+\sum_{j=1}^{i-1}({P_i}^{i-j}\sum_{k=j+1}^{i}f_k)-\sum_{j=1}^{i-1}({P_i}^{i-j+1}\sum_{k=j+1}^{i}f_k)+{P_i}^{i}\sum_{j=1}^{i}f_j

把第四项合并到第二项上（1 也是一项哦），得到：

f_i=1+\sum_{j=0}^{i-1}({P_i}^{i-j}\sum_{k=j+1}^{i}f_k)-\sum_{j=1}^{i-1}({P_i}^{i-j+1}\sum_{k=j+1}^{i}f_k)

将第三项的 j 整体往左移一位，得到：

f_i=1+\sum_{j=0}^{i-1}({P_i}^{i-j}\sum_{k=j+1}^{i}f_k)-\sum_{j=0}^{i-2}({P_i}^{i-j}\sum_{k=j+2}^{i}f_k)

把第三项合并到第二项上（即括号内的数相减），得到：

f_i=1+\sum_{j=0}^{i-2}({P_i}^{i-j}f_{j+1})+P_if_i

将第三项挪到左边，得到：

(1-P_i)f_i=1+\sum_{j=0}^{i-2}{P_i}^{i-j}f_{j+1}

将 (1-P_i) 除过去，得到：

f_i=\frac{1+\sum_{j=0}^{i-2}{P_i}^{i-j}f_{j+1}}{1-P_i}

此时已经可以 O(n^2) dp 了，需要优化。发现瓶颈在 sigma 求值上，而且很难用前缀和之类的优化。

发现 P_i 仅有 100 种取值，考虑把这 100 种直接暴力计入状态。

具体的，设 g_{t,i} 表示钦定 P_i=t\% 时的 \sum_{j=0}^{i-2}{t}^{i-j}f_{j+1}。

自行推导不难得出，f,g 的转移。

g_{t,i}=tg_{t,i-1}+t^2f_{i-1},f_i=\frac{1+g_{P_i,i}}{1-P_i}

成功做到 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define mod 998244353
int n,a[N],p[105];
int f[N],g[105][N];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int qpow(int x,int y){int ret=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)ret=1ll*ret*x%mod;return ret;}
int main()
{
    scanf("%d",&n);
    int inv100=qpow(100,mod-2);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<100;i++) p[i]=1ll*i*inv100%mod;
    for(int i=1;i<=n;i++)
    {
        if(i>1) for(int t=0;t<100;t++) g[t][i]=add(1ll*p[t]*g[t][i-1]%mod,1ll*p[t]*p[t]%mod*f[i-1]%mod);
        f[i]=1ll*add(1,g[a[i]][i])*qpow(del(1,p[a[i]]),mod-2)%mod;
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=add(ans,f[i]);
    printf("%d",ans);
}