Codeforces Round #446 Div1 E

题目大意

有n个数,进行k轮操作:随机一个i,让(a_i)减1,然后ans加上(Pi_{j eq i}a_i)
求ans的期望。

分析

发现,造成的伤害就是原来的ai的积减去k轮操作后的ai的积(其实我在看题解前根本没发现)。
题目就变成了求k轮操作后的ai的积的期望。
设ai经过了k轮操作减去了bi

[E(Pi_{i=1}^{n}(a_i-b_i))=dfrac{1}{n^k}sum_{sum_{i=1}^{n}b_i=k}Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)C_{k}^{b_1}C_{k-b_1}^{b_2}C_{k-b_1-b_2}^{b_3}... ]

[=dfrac{1}{n^k}sum_{sum_{i=1}^{n}b_i=k}Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)dfrac{k!}{Pi_{i=1}^{n}b_i!} ]

考虑如何求

[sum_{sum_{i=1}^{n}b_i=k}Pi_{i=1}^{n}(a_i-b_i)(a_i-b_i)dfrac{1}{Pi_{i=1}^{n}b_i!} ]

设生成函数

[F_i(x)=sum_{j=0}^{infty}dfrac{a_i-j}{j!}x^j=sum_{j=0}^{infty}dfrac{a_i}{j!}x^j-sum_{j=0}^{infty}dfrac{1}{(j-1)!}x^j=(a_i-x)e^x ]

于是就

[=Pi_{i=1}^{n}F_i(x)=e^{nx}Pi_{i=1}^{n}(a_i-x) ]

我们就要求出(e^{nx}Pi_{i=1}^{n}(a_i-x))的第k项的系数
(Pi_{i=1}^{n}(a_i-x))就可以用分治FFT来求。
然后对于(Pi_{i=1}^{n}(a_i-x))第i项乘上(e^{nx})第k-i项加起来就是(e^{nx}Pi_{i=1}^{n}(a_i-x))的第k项的系数了。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <vector>
const int inf=2147483647;
const long long mo=998244353;
const int N=400005;
using namespace std;
long long f[20][N],W[N];
int n,m;
long long ans,a[N],ny;
long long poww(long long x,long long y)
{
	long long s=1;
	for(;y;y>>=1,x=x*x%mo)
		if(y&1) s=s*x%mo;
	return s;
}
void NTT(long long *f,int fn,int z)
{
	for(int i=0,p=0;i<fn;i++)
	{
		if(i<p) swap(f[i],f[p]);
		for(int j=fn>>1;(p^=j)<j;j>>=1);
	}
	for(int i=2;i<=fn;i<<=1)
	{
		int half=i>>1,pe=fn/i;
		for(int j=0;j<half;j++)
		{
			long long w0=z?W[j*pe]:W[fn-j*pe];
			for(int k=j;k<fn;k+=i)
			{
				long long x=f[k],y=f[k+half]*w0%mo;
				f[k]=(x+y)%mo,f[k+half]=(x-y+mo)%mo;
			}
		}
	}
}
void dc(int deep,int l,int r)
{
	if(l==r)
	{
		f[deep][0]=a[l],f[deep][1]=-1;
		return;
	}
	int mid=(l+r)>>1,fn;
	for(fn=1;fn<=r-l+2;fn<<=1);

	dc(deep+1,l,mid);

	for(int i=0;i<fn;i++) f[deep][i]=f[deep+1][i],f[deep+1][i]=0;

	dc(deep+1,mid+1,r);

	W[0]=1,W[1]=poww(3,(mo-1)/fn);
	for(int i=1;i<=fn;i++) W[i]=W[i-1]*W[1]%mo;
	NTT(f[deep],fn,1),NTT(f[deep+1],fn,1);
	for(int i=0;i<fn;i++) f[deep][i]=f[deep][i]*f[deep+1][i]%mo;
	NTT(f[deep],fn,0);
	ny=poww(fn,mo-2);
	for(int i=0;i<fn;i++) f[deep][i]=f[deep][i]*ny%mo;

	for(int i=0;i<fn;i++) f[deep+1][i]=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	dc(1,1,n);
	long long val=m;
	ny=poww(n,mo-2);
	for(int i=1;i<=min(n,m);i++)
	{
		val=val*ny%mo;
		ans=(ans+f[1][i]*val%mo)%mo;
		if(m-i>=1) val=val*(m-i)%mo;
	}
	printf("%lld
",(mo-ans+mo)%mo);
}
原文地址:https://www.cnblogs.com/chen1352/p/9099523.html