[codeforces 891E]Lust

题目大意

给定大小为n的数组，还有一个变量res（初始为0）。进行k次操作，每次随机选择一个数ai，然后给res加上$\prod_{j≠i}aj$，然后ai-1
问最终res的期望值模$1e9+7$的值。

n≤5000，0≤ai,k≤$10^9$

分析

首先转化题意：每一次加的数可以看成操作前所有数的乘积减操作后所有数的乘积。那么只需求最终序列累乘的期望值，然后用初始的值减去它即可。
接下来设第i项减去x次的生成函数为$F_i(x)$，易得$F_i(x)=\sum_{j≥0}\frac{(ai-j)x^j}{j!}=\sum_{j≥0}(ai-j)e^x$
把所有生成函数乘起来，那么总体的生成函数是$F(x)=\sum_{j≥0}e^{nx}\prod(ai-x)$
现在需要求$[x^k]F(x)$
n只有5000，那么我们可以直接暴力求出后面部分的第0到n项的系数ci
然后得到$E=k!\frac{\sum_{i=0}^n c_i*\frac{n^{k-i}}{(k-i)!}}{n^k}=\frac{\sum_{i=0}^n c_i*n^{k-i}\sum_{j=k-i+1}^{k}j}{n^k}$

时间复杂度$O(n^2)$

#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;
}