你有 n 个数 a1,a2,…,an 要进行 k 次操作,每次随机选择一个数 x∈[1,n],把 ax 减一,并将答案增加除 ax 外所有数的乘积。
求最终答案的期望,答案对 109+7 取模。
1≤n≤5000。
有个结论,ans 每次增加的量等于 ∏ai 减少的量,那么设 ai 减少了 bi,那么 ans 即为 ∏ai−∏(ai−bi)。
那么设 ai 的 EGF 为 Fi(x)=j=0∑∞(ai−j)j!xj,则答案即为 ∏ai−nk[xk]∏Fi(x)。
分母可以 O(n) 算,所以问题的难点在于 [xk]∏Fi(x),注意到有:
Fi(x)=j=0∑∞(ai−j)j!xj=j=0∑∞aij!xj−j=0∑∞jj!xj=aij=0∑∞j!xj−xj=1∑∞(j−1)!xj−1=(ai−x)ex
那么有:
[xk]∏Fi(x)=[xk](enx∏(ai−x))
由于 n≤5000,所以 ∏(ai−x) 的每一项系数 c0+c1x1+… 可以 O(n2) 算出来,然后根据 [xk]enx=nk,可以直接 O(n2) 暴力卷积算出 [xk]∏Fi(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;
}