CF891E Lust 做题记录

你有 $n$ 个数 $a_1,a_2,\dots,a_n$ 要进行 $k$ 次操作，每次随机选择一个数 $x \in [1,n]$，把 $a_x$ 减一，并将答案增加除 $a_x$ 外所有数的乘积。

求最终答案的期望，答案对 $10^9 + 7$ 取模。

$1\le n\le 5000$。

有个结论，$ans$ 每次增加的量等于 $\prod a_i$ 减少的量，那么设 $a_i$ 减少了 $b_i$，那么 $ans$ 即为 $\prod a_i-\prod (a_i-b_i)$。

那么设 $a_i$ 的 EGF 为 $F_i(x)=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!}$，则答案即为 $\prod a_i-\frac{[x^k]\prod F_i(x)}{n^k}$。

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

$\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}$

那么有：

$[x^k]\prod F_i(x)=[x^k]\left(e^{nx}\prod (a_i-x)\right)$

由于 $n\le 5000$，所以 $\prod (a_i-x)$ 的每一项系数 $c_0+c_1x^1+\dots$ 可以 $O(n^2)$ 算出来，然后根据 $[x^k]e^{nx}=n^k$，可以直接 $O(n^2)$ 暴力卷积算出 $[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;
}