给定大小为n的数组,还有一个变量res(初始为0)。进行k次操作,每次随机选择一个数ai,然后给res加上
∏j≠iaj
,然后ai-1
问最终res的期望值模
1e9+7
的值。
n≤5000,0≤ai,k≤ 109
首先转化题意:每一次加的数可以看成操作前所有数的乘积减操作后所有数的乘积。那么只需求最终序列累乘的期望值,然后用初始的值减去它即可。
接下来设第i项减去x次的生成函数为
Fi(x)
,易得
Fi(x)=∑j≥0(ai−j)xjj!=∑j≥0(ai−j)ex
把所有生成函数乘起来,那么总体的生成函数是
F(x)=∑j≥0enx∏(ai−x)
现在需要求
[xk]F(x)
n只有5000,那么我们可以直接暴力求出后面部分的第0到n项的系数ci
然后得到
E=k!∑ni=0ci∗nk−i(k−i)!nk=∑ni=0ci∗nk−i∑kj=k−i+1jnk
时间复杂度 O(n2)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5005,mo=1e9+7;
typedef long long LL;
int n,K,m,ans,a[N],f[N][N];
int quick(int x,int y)
{
if (!y) return 1;
int s=quick(x,y>>1); s=(LL)s*s%mo;
if (y&1) s=(LL)s*x%mo;
return s;
}
int main()
{
scanf("%d%d",&n,&K);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0][0]=1;
for (int i=1;i<=n;i++)
{
f[i][0]=(LL)f[i-1][0]*a[i]%mo;
for (int j=1;j<=i;j++) f[i][j]=((LL)f[i-1][j]*a[i]-f[i-1][j-1])%mo;
}
for (int i=0;i<=min(n,K);i++)
{
int calc=1;
for (int j=K-i+1;j<=K;j++) calc=(LL)calc*j%mo;
ans=(ans+(LL)f[n][i]*quick(n,K-i)%mo*calc)%mo;
}
ans=(LL)ans*quick(quick(n,K),mo-2)%mo;
m=1;
for (int i=1;i<=n;i++) m=(LL)m*a[i]%mo; ans=(m-ans)%mo;
if (ans<0) ans+=mo;
printf("%d\n",ans);
return 0;
}