当前位置: 首页 > 工具软件 > code saturne > 使用案例 >

[codeforces 891E]Lust

萧晔
2023-12-01

题目大意

给定大小为n的数组,还有一个变量res(初始为0)。进行k次操作,每次随机选择一个数ai,然后给res加上 jiaj ,然后ai-1
问最终res的期望值模 1e9+7 的值。

n≤5000,0≤ai,k≤ 109

分析

首先转化题意:每一次加的数可以看成操作前所有数的乘积减操作后所有数的乘积。那么只需求最终序列累乘的期望值,然后用初始的值减去它即可。
接下来设第i项减去x次的生成函数为 Fi(x) ,易得 Fi(x)=j0(aij)xjj!=j0(aij)ex
把所有生成函数乘起来,那么总体的生成函数是 F(x)=j0enx(aix)
现在需要求 [xk]F(x)
n只有5000,那么我们可以直接暴力求出后面部分的第0到n项的系数ci
然后得到 E=k!ni=0cinki(ki)!nk=ni=0cinkikj=ki+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;
}
 类似资料:

相关阅读

相关文章

相关问答