AtCoder Grand Contest 038 E - Gachapon 题解

传送门
题目大意：
有一个随机数生成器会随机生成$[1,N]$的一个整数，第$i$个数被生成的概率是$\frac{A_i}{{\sum }_j{A}_j}$,每次调用这个生成器生成一个数，把生成的数排成一个序列，当对于每个数$i$都出现了不少于$B_i$次时停止，求序列的期望长度。
$\sum A_i\le 400,\sum B_i\le 400$
做法：
官方题解的做法过于神仙，这里给出一种爆推生成函数的做法。
定义$a_i=\frac{A_i}{{\sum }_j{A}_j}$,$p_i$表示在第$i$步内结束的概率，$P(x)$是$p$序列的指数型生成函数，即$P(x)=\sum p_i\frac{x^i}{i!}$
显然有$P(x)={\prod }_i({\sum }_{j\ge B_i}\frac{(a_{i}x{)}^j}{j!})={\prod }_i(e^{a_{i}x}-{\sum }_{j<B_i}\frac{(a_{i}x{)}^j}{j!})$
暴力展开可以化为$P(x)={\sum }_i{\sum }_j{c}_{i,j}{x}^i{e}^{jx}$其中$c_{i,j}$是系数
最后的答案的形式是${\sum }_{n=0}^{\infty }[\frac{x^n}{n!}](e^x-P(x))$
我们发现$e^x-P(x)$所有与$e$相关的项$e$的指数都小于$1$,所以这个生成函数是收敛的，可以计算它的系数和。
单独考虑其中的一项
${\sum }_{n=0}^{\infty }[\frac{x^n}{n!}](x^s{e}^{tj})={\sum }_{n=0}^{\infty }(n+s{)}^{\underline{s}}{j}^n$
暴力展开$(n+s{)}^{\underline{s}}$,现在的问题就变成了给定$s$，求${\sum }_{n=0}^{\infty }{n}^s{j}^n$
令$F(s)={\sum }_{n=0}^{\infty }{n}^s{j}^n$,$F$可以通过差分递推求得。
至此整个问题就解决了。
每一步的时间复杂度都是$O((\sum A_i{)}^3)$的(假定$\sum A_i$和$\sum B_i$同阶)
代码：

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const LL mod=998244353;
const int Maxn=405;
int n,a[Maxn],b[Maxn];
LL p[Maxn],pw[Maxn][Maxn];
LL fact[Maxn],ivf[Maxn];
LL qp(LL x,LL p){
	LL ret=1;
	while (p){
		if (p&1) ret=ret*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ret;
}
LL inv(LL x){
	return qp(x,mod-2);
}
LL dp[Maxn][Maxn][Maxn],S[Maxn];
LL _coef[Maxn][Maxn],tmp[Maxn][Maxn],C[Maxn][Maxn];
void Add(LL &x,LL y){
	x+=y;
	if (x>=mod) x-=mod;
}
void _init(){
	fact[0]=1;
	for (int i=1;i<Maxn;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	for (int i=0;i<Maxn;i++) ivf[i]=inv(fact[i]);
	for (int i=0;i<Maxn;i++){
		for (int j=0;j<=i;j++){
			C[i][j]=fact[i]*ivf[j]%mod*ivf[i-j]%mod;
		}
	}
	_coef[0][0]=1;
	for (int j=1;j<Maxn;j++){
		for (int k=0;k<Maxn;k++){
			_coef[j][k]=_coef[j-1][k]*j%mod;
			if (k) Add(_coef[j][k],_coef[j-1][k-1]%mod);
		}
	}
}
int main(){
	_init();
	scanf("%d",&n);
	int sa=0;
	for (int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]),sa+=a[i];
	for (int i=1;i<=n;i++) p[i]=1ll*a[i]*inv(sa)%mod;
	for (int i=1;i<=n;i++){
		pw[i][0]=1;
		for (int j=1;j<Maxn;j++){
			pw[i][j]=pw[i][j-1]*p[i]%mod;
		}
	}
	dp[0][0][0]=1;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=400;j++){
			for (int k=0;k<=sa;k++){
				
				if (k>=a[i]){
					Add(dp[i][j][k],dp[i-1][j][k-a[i]]);
				}
				for (int l=0;l<b[i];l++){
					if(j>=l) Add(dp[i][j][k],(mod-pw[i][l]*ivf[l]%mod)*dp[i-1][j-l][k]%mod);
				}
			}
		}
	}
	LL ans=0;
	for (int k=0;k<sa;k++){
		LL v=1ll*k*inv(sa)%mod;
		S[0]=inv((1-v+mod)%mod);
		LL t=S[0];
		for (int i=1;i<Maxn;i++){
			S[i]=0;
			for (int l=0;l<i;l++){
				LL coef=(i-l)&1?(1):(mod-1);
				coef=coef*C[i][l]%mod;
				if (l)S[i]+=coef*S[l];
				else S[i]+=coef*(S[l]-1);
				S[i]%=mod;
			}
			if (S[i]<0) S[i]+=mod;
			S[i]=S[i]*t%mod;
		}
		for (int j=0;j<=400;j++){
			if (dp[n][j][k]){
				LL c=mod-dp[n][j][k];
				if (k==0){
					ans+=c*fact[j];ans%=mod;
					continue;
				}
				LL res=0;
				for (int k=0;k<Maxn;k++){
					if (_coef[j][k]!=0){
						res+=_coef[j][k]*S[k];
						res%=mod;
					}
				}
				ans+=c*res;
				ans%=mod;
			}
		}
	}
	printf("%lldn",ans);
	return 0;
}

最后

以上就是活力心锁为你收集整理的AtCoder Grand Contest 038 E - Gachapon 题解的全部内容，希望文章能够帮你解决AtCoder Grand Contest 038 E - Gachapon 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。