Codeforces Round #446 Div1 E

题目大意

有n个数，进行k轮操作：随机一个i，让\(a_i\)减1，然后ans加上\(\Pi_{j\neq 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\n",(mo-ans+mo)%mo);

}

巴特西

Codeforces Round #446 Div1 E

题目大意

分析

最新文章

热门文章