专栏文章

[ABC409G] Accumulation of Wealth 题解

llinjunye
AT_abc409_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip4cxob
此快照首次捕获于
2025/12/03 05:57
3 个月前
此快照最后确认于
2025/12/03 05:57
3 个月前
查看原文
一道很不错的多项式题。
我们先转化题意：有 n−1n-1 次操作。操作一有 pp 的概率触发，操作为将当前数组最大值加一并放到数组中；操作二有 1−p1-p 的概率触发，操作为随机在数组中选一个数，并将它复制一份放到数组中。数组一开始有一个数 11，最后求每个数出现次数的期望。
那么，如果一直做操作一，我们发现数组会先加入 22，然后是 33，再是 44，以此类推。
首先我们要求的是期望 EkE_k。我们发现当 k≥2k\ge 2 时，它们一开始都没有在数组中出现过，所以我们可以将它们归为一个处理，而 k=1k=1 的情况单独处理。
接下来处理 k≥2k\ge 2：
我们要算它第一次出现的概率。那么我们假设操作了 ii 次它才出现。根据上面的发现，我们在出现 kk 之前肯定做了 k−2k-2 次操作一，然后第 ii 次又做了操作一。容易得在前 i−1i-1 次操作中，出现 k−2k-2 次操作一的概率为 (i−1k−2)pk−2\binom{i-1}{k-2}p^{k-2}。然后剩下会有 i−k+1i-k+1 次操作二，概率为 (1−p)i−k+1(1-p)^{i-k+1}，在加上第 ii 次出现操作一的概率，总概率为 (i−1k−2)pk−1(1−p)i−k+1\binom{i-1}{k-2}p^{k-1}(1-p)^{i-k+1}。
那么假设它已经出现了，这时候后面还有 n−1−in-1-i 次操作。让我们定义 f(i)f(i) 表示在刚出现一个数 xx 之后剩余的 ii 次操作，xx 出现次数的期望。那么，kk 在剩余的 n−1−in-1-i 次操作后出现次数的期望为 f(n−1−i)f(n-1-i)。
接下来我们考虑计算 f(i)f(i)。
首先如果现在有 mm 个数，当前的出现次数为 cc，容易得到一次操作后的期望为：c+(1−p)×cm=c×1−p+mmc+(1-p)\times\frac{c}{m}=c\times\frac{1-p+m}{m}。于是我们能得到递推式 f(i)=f(i−1)×1−p+(n−i)n−if(i)=f(i-1)\times\frac{1-p+(n-i)}{n-i}，你可以感性理解。
不难得出边界条件 f(0)=1f(0)=1（因为 kk 已经出现了一次），然后转移是 O(1)O(1) 的，所以总体复杂度为 O(n)O(n)。如果你不是用 O(n)O(n) 预处理逆元的话，复杂度为 O(nlog⁡n)O(n\log n)。
接下来，我们只需要将前 ii 次操作出现 kk 的概率和后面的期望相乘即可。但是我们并不知道 kk 会在那一次出现，所以我们要枚举 ii，不难得到递推式：Ek=∑i=k−1n−1(i−1k−2)pk−1(1−p)i−k+1f(n−1−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)。
我们开始化简。首先我们可以将 ii 的下界变成 00，这时候 Ek=∑i=0n−k(i+k−2k−2)pk−1(1−p)if(n−i−k)E_k=\sum_{i=0}^{n-k}\binom{i+k-2}{k-2}p^{k-1}(1-p)^{i}f(n-i-k)。
然后我们将组合数展开：Ek=∑i=0n−k(i+k−2)!(k−2)!i!pk−1(1−p)if(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)。
然后将与 ii 无关的提到前面：Ek=pk−1(k−2)!∑i=0n−k(i+k−2)!i!(1−p)if(n−i−k)=pk−1(k−2)!∑i=0n−k(i+k−2)!i!(1−p)if(n−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)。
接着做一个很巧妙的转化：Ek=pk−1(k−2)!∑i=0n−k(1−p)ii!(i+k−2)!f(n−k−i)=pk−1(k−2)!∑i=0n−k(1−p)ii!(n−(n−k−i)−2)!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−ki+(n-k-i)=n-k，而 n−kn-k 是我们 ii 的上界。这好像一个多项式乘法啊！
那么我们定义多项式 F(x)=∑i=0n−2(i−p)ii!xiF(x)=\sum_{i=0}^{n-2}\frac{(i-p)^i}{i!}x^i，G(x)=∑i=0n−2(i−p)ii!(n−i−2)!f(i)xiG(x)=\sum_{i=0}^{n-2}\frac{(i-p)^i}{i!}(n-i-2)!f(i)x^i。注意不要混淆 F(x)F(x) 和 f(i)f(i)。
那么 EkE_k 就是两个多项式乘起来后 xn−kx^{n-k} 的系数，再乘上前面提出来的 pk−1(k−2)!\frac{p^{k-1}}{(k-2)!}。形式化的，Ek=pk−1(k−2)![xn−k]F(x)G(x)E_k=\frac{p^{k-1}}{(k-2)!}[x^{n-k}]F(x)G(x)。
多项式乘法可以用 NTT 或者 FFT，容易做到 O(nlog⁡n)O(n\log n)。然后计算 pk−1(k−2)!\frac{p^{k-1}}{(k-2)!} 可以用快速幂做到 O(log⁡n)O(\log n)（当然你可以通过预处理做到 O(1)O(1)），多项式的构造可以做到 O(nlog⁡n)O(n\log n)（当然你可以通过预处理做到 O(n)O(n)）。阶乘和它的逆元可以 O(n)O(n) 预处理。
这时候，我们不难发现 E1E_1 其实就是 n−∑k=2nEkn-\sum_{k=2}^{n}E_k，这是 O(n)O(n) 的。
因此，总复杂度为 O(nlog⁡n)O(n\log n)，可以通过。
代码：
CPP
#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;
}
/*
*/
确实很不错。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...