[ABC409G] Accumulation of Wealth 题解

linjunye · 2025-06-08 10:33:29 · 题解

一道很不错的多项式题。

我们先转化题意：有 n-1 次操作。操作一有 p 的概率触发，操作为将当前数组最大值加一并放到数组中；操作二有 1-p 的概率触发，操作为随机在数组中选一个数，并将它复制一份放到数组中。数组一开始有一个数 1，最后求每个数出现次数的期望。

那么，如果一直做操作一，我们发现数组会先加入 2，然后是 3，再是 4，以此类推。

首先我们要求的是期望 E_k。我们发现当 k\ge 2 时，它们一开始都没有在数组中出现过，所以我们可以将它们归为一个处理，而 k=1 的情况单独处理。

接下来处理 k\ge 2：

我们要算它第一次出现的概率。那么我们假设操作了 i 次它才出现。根据上面的发现，我们在出现 k 之前肯定做了 k-2 次操作一，然后第 i 次又做了操作一。容易得在前 i-1 次操作中，出现 k-2 次操作一的概率为 \binom{i-1}{k-2}p^{k-2}。然后剩下会有 i-k+1 次操作二，概率为 (1-p)^{i-k+1}，在加上第 i 次出现操作一的概率，总概率为 \binom{i-1}{k-2}p^{k-1}(1-p)^{i-k+1}。

那么假设它已经出现了，这时候后面还有 n-1-i 次操作。让我们定义 f(i) 表示在刚出现一个数 x 之后剩余的 i 次操作，x 出现次数的期望。那么，k 在剩余的 n-1-i 次操作后出现次数的期望为 f(n-1-i)。

接下来我们考虑计算 f(i)。

首先如果现在有 m 个数，当前的出现次数为 c，容易得到一次操作后的期望为：c+(1-p)\times\frac{c}{m}=c\times\frac{1-p+m}{m}。于是我们能得到递推式 f(i)=f(i-1)\times\frac{1-p+(n-i)}{n-i}，你可以感性理解。

不难得出边界条件 f(0)=1（因为 k 已经出现了一次），然后转移是 O(1) 的，所以总体复杂度为 O(n)。如果你不是用 O(n) 预处理逆元的话，复杂度为 O(n\log n)。

接下来，我们只需要将前 i 次操作出现 k 的概率和后面的期望相乘即可。但是我们并不知道 k 会在那一次出现，所以我们要枚举 i，不难得到递推式：E_k=\sum_{i=k-1}^{n-1}\binom{i-1}{k-2}p^{k-1}(1-p)^{i-k+1}f(n-1-i)。

我们开始化简。首先我们可以将 i 的下界变成 0，这时候 E_k=\sum_{i=0}^{n-k}\binom{i+k-2}{k-2}p^{k-1}(1-p)^{i}f(n-i-k)。

然后我们将组合数展开：E_k=\sum_{i=0}^{n-k}\frac{(i+k-2)!}{(k-2)!i!}p^{k-1}(1-p)^{i}f(n-i-k)。

然后将与 i 无关的提到前面：E_k=\frac{p^{k-1}}{(k-2)!}\sum_{i=0}^{n-k}\frac{(i+k-2)!}{i!}(1-p)^{i}f(n-i-k)=\frac{p^{k-1}}{(k-2)!}\sum_{i=0}^{n-k}\frac{(i+k-2)!}{i!}(1-p)^{i}f(n-k-i)。

接着做一个很巧妙的转化：E_k=\frac{p^{k-1}}{(k-2)!}\sum_{i=0}^{n-k}\frac{(1-p)^{i}}{i!}(i+k-2)!f(n-k-i)=\frac{p^{k-1}}{(k-2)!}\sum_{i=0}^{n-k}\frac{(1-p)^{i}}{i!}(n-(n-k-i)-2)!f(n-k-i)。

注意到 i+(n-k-i)=n-k，而 n-k 是我们 i 的上界。这好像一个多项式乘法啊！

那么我们定义多项式 F(x)=\sum_{i=0}^{n-2}\frac{(i-p)^i}{i!}x^i，G(x)=\sum_{i=0}^{n-2}\frac{(i-p)^i}{i!}(n-i-2)!f(i)x^i。注意不要混淆 F(x) 和 f(i)。

那么 E_k 就是两个多项式乘起来后 x^{n-k} 的系数，再乘上前面提出来的 \frac{p^{k-1}}{(k-2)!}。形式化的，E_k=\frac{p^{k-1}}{(k-2)!}[x^{n-k}]F(x)G(x)。

多项式乘法可以用 NTT 或者 FFT，容易做到 O(n\log n)。然后计算 \frac{p^{k-1}}{(k-2)!} 可以用快速幂做到 O(\log n)（当然你可以通过预处理做到 O(1)），多项式的构造可以做到 O(n\log n)（当然你可以通过预处理做到 O(n)）。阶乘和它的逆元可以 O(n) 预处理。

这时候，我们不难发现 E_1 其实就是 n-\sum_{k=2}^{n}E_k，这是 O(n) 的。

因此，总复杂度为 O(n\log n)，可以通过。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300010;
const int mod=998244353;
const int G=3;//mod 的原根
const int Gi=332748118;//原根的逆元
int inv[N];
int ijc[N];
int jc[N];
void init(int n){
    inv[1]=1;
    jc[0]=1;
    ijc[0]=1;
    for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;//逆元
    for(int i=1;i<=n;i++){
        jc[i]=jc[i-1]*i%mod;//阶乘
        ijc[i]=ijc[i-1]*inv[i]%mod;//阶乘的逆元
    }
    return;
}
int C(int n,int m){//可以省略
    if(n<m)return 0;
    int fz=jc[n];
    int fm=ijc[m]*ijc[n-m]%mod;
    return fz*fm%mod;
}
int ksm(int a,int b){//快速幂
    int z=1;
    while(b){
        if(b&1)z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
int Inv(int x){//O(n log n)求逆元
    return ksm(x,mod-2);
}
int a[N],b[N];
int r[N];
void NTT(int len,int *a,int on){//Not Too TLE (NTT 多项式乘法qwq)
    for(int i=0;i<len;i++)
        if(i<r[i])
            swap(a[i],a[r[i]]);
    for(int mid=1;mid<len;mid<<=1){
        int Wn=ksm(on==1?G:Gi,(mod-1)/(mid*2));
        int B=mid<<1;
        for(int i=0;i<len;i+=B){
            int W=1;
            for(int j=0;j<mid;j++,W=(W*Wn)%mod){
                int A=a[i+j];
                int B=a[i+j+mid];
                a[i+j]=((A+W*B)%mod+mod)%mod;
                a[i+j+mid]=((A-W*B)%mod+mod)%mod;
            }
        }
    }
    if(on==1)return;
    int _inv=Inv(len);
    for(int i=0;i<=len;i++)a[i]=(a[i]*_inv)%mod;
    return;
}
int n,m,p;
int f[N];
int E[N];
int _=1,l;
void solve(){//做多项式乘法
    _=1;l=0;
    while(_<=m+m){
        _<<=1;
        l++;
    }
    for(int i=0;i<_;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l-1); 
    NTT(_,a,1);
    NTT(_,b,1);
    for(int i=0;i<=_;i++)a[i]=a[i]*b[i]%mod;
    NTT(_,a,-1);
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init(N-10);
    cin>>n>>p;
    m=n-2;//多项式上界
    p=p*inv[100]%mod;//p=p/100
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*(n-i+1-p)%mod*inv[n-i]%mod;//预处理f(i)
    for(int i=0;i<=m;i++)a[i]=ksm((1-p+mod)%mod,i)*ijc[i]%mod;//填充多项式 F
    for(int i=0;i<=m;i++)b[i]=f[i]*jc[n-i-2]%mod;//填充多项式 G
    solve();//多项式乘法
    for(int i=2;i<=n;i++)E[i]=ksm(p,i-1)*ijc[i-2]%mod*a[n-i]%mod;//求期望
    int ss=0;
    for(int i=2;i<=n;i++)ss=(ss+E[i])%mod;//求sum_{k=2}^{n}E_i
    E[1]=(n-ss)%mod;//求 E_1
    for(int i=1;i<=n;i++)E[i]=(E[i]%mod+mod)%mod;
    for(int i=1;i<=n;i++)cout<<E[i]<<"\n";
    return 0;
}
/*
*/

确实很不错。