CF891E Lust 做题记录

你有 nn 个数 a1,a2,,ana_1,a_2,\dots,a_n 要进行 kk 次操作,每次随机选择一个数 x[1,n]x \in [1,n],把 axa_x 减一,并将答案增加除 axa_x 外所有数的乘积。

求最终答案的期望,答案对 109+710^9 + 7 取模。

1n50001\le n\le 5000

有个结论,ansans 每次增加的量等于 ai\prod a_i 减少的量,那么设 aia_i 减少了 bib_i,那么 ansans 即为 ai(aibi)\prod a_i-\prod (a_i-b_i)

那么设 aia_i 的 EGF 为 Fi(x)=j=0(aij)xjj!F_i(x)=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!},则答案即为 ai[xk]Fi(x)nk\prod a_i-\frac{[x^k]\prod F_i(x)}{n^k}

分母可以 O(n)O(n) 算,所以问题的难点在于 [xk]Fi(x)[x^k]\prod F_i(x),注意到有:

Fi(x)=j=0(aij)xjj!=j=0aixjj!j=0jxjj!=aij=0xjj!xj=1xj1(j1)!=(aix)ex\begin{aligned} F_i(x)&=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!}\\ &=\sum\limits_{j=0}^\infin a_i\frac{x^j}{j!}-\sum\limits_{j=0}^\infin j\frac{x^j}{j!}\\ &=a_i\sum\limits_{j=0}^\infin\frac{x^j}{j!}-x\sum\limits_{j=1}^\infin \frac{x^{j-1}}{(j-1)!}\\ &=(a_i-x)e^x \end{aligned}

那么有:

[xk]Fi(x)=[xk](enx(aix))[x^k]\prod F_i(x)=[x^k]\left(e^{nx}\prod (a_i-x)\right)

由于 n5000n\le 5000,所以 (aix)\prod (a_i-x) 的每一项系数 c0+c1x1+c_0+c_1x^1+\dots 可以 O(n2)O(n^2) 算出来,然后根据 [xk]enx=nk[x^k]e^{nx}=n^k,可以直接 O(n2)O(n^2) 暴力卷积算出 [xk]Fi(x)[x^k]\prod F_i(x)

代码如下:

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5005,p=1000000007;

int n,k,a[S];
int c[S],tmp[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	if(n<m||n<0||m<0) return 0;
	int re=1,div=1;
	for(int i=n;i>=n-m+1;i--) re=1ll*re*i%p;
	for(int i=1;i<=m;i++) div=1ll*div*i%p;
	return 1ll*re*qpow(div,p-2)%p;
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	c[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=n;j++) tmp[j]=c[j];
		for(int j=0;j<=n;j++) c[j]=1ll*c[j]*a[i]%p;
		for(int j=0;j<=n-1;j++) c[j+1]=(c[j+1]-tmp[j]+p)%p;
	}
	for(int i=0,fra=1;i<=n;i++) fra=1ll*fra*max(i,1)%p,c[i]=1ll*fra*c[i]%p;
	int prod=0;
	for(int i=k;i>=k-n&&i>=0;i--) prod=(prod+1ll*qpow(n,i)*c[k-i]%p*C(k,k-i)%p)%p;
	int mul=1;
	for(int i=1;i<=n;i++) mul=1ll*mul*a[i]%p;
	int ans=(mul-1ll*prod*qpow(qpow(n,k),p-2)%p+p)%p;
	printf("%d\n",ans);
	return 0;
}