CF891E Lust

生成函数,期望

题意

你有 nn 个数 a1,a2,…,ana_1,a_2,\dots,a_n 要进行 kk 次操作，每次随机选择一个数 x∈[1,n]x \in [1,n]，把 axa_x 减一，并将答案增加除 axa_x 外所有数的乘积。

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

1≤n≤5000,  1≤k≤109,  0≤ai≤1091\le n \le 5000,\;1\le k\le 10^9,\;0\le a_i\le 10^9

题解

可以发现，答案的增加量等于 ∏ai\prod a_i 的减少量。设最后得到的序列为 {bi}\left\{b_i\right\} ，那么答案为：

∏i=1nai−∏i=1n(ai−bi)\prod_{i=1}^{n} a_i - \prod_{i=1}^{n} (a_i-b_i)

右边，求期望值

E=1nk(∑∑bi=kk!∏bi!∏i=1n(ai−bi))=k!nk∑∑bi=k∏i=1nai−bibi!\begin{aligned} \mathbb{E}&=\frac{1}{n^k} \left(\sum_{\sum_{b_i}=k}\frac{k!}{\prod b_i!} \prod_{i=1}^n (a_i-b_i)\right)\\ &=\frac{k!}{n^k}\sum_{\sum_{b_i}=k} \prod_{i=1}^n \frac{a_i-b_i}{b_i!}\\ \end{aligned}

含义：nkn^k 表示操作序列总数，显然每种情况概率是一样的故 1nk\frac{1}{n^k} ，右边便是计算所有情况的总和，先是枚举 {bi}\left\{b_i\right\} 满足 ∑bi=k\sum_{b_i}=k ，对于这组确定的 {bi}\left\{b_i\right\} 显然对应 k!∏bi!\dfrac{k!}{\prod b_i!} 个操作序列（熟知的多重集排列数），然后 ∏i=1n(ai−bi)\prod_{i=1}^{n} (a_i-b_i) 对应贡献。

然后就是要算 ∑∑bi=k∏i=1nai−bibi!\displaystyle\sum_{\sum_{b_i}=k} \prod_{i=1}^n \frac{a_i-b_i}{b_i!} ，这坨东西构造生成函数：

fi^(x)=∑j=0∞ai−jj!xj=∑j=0∞aij!xj−∑j=1∞x(j−1)!xj−1=(ai−x)ex\begin{aligned} \hat{f_i}(x)&=\sum_{j=0}^{\infty} \frac{a_i-j}{j!}x^j\\ &=\sum_{j=0}^{\infty} \frac{a_i}{j!}x^j -\sum_{j=1}^{\infty} \frac{x}{(j-1)!}x^{j-1}\\ &=(a_i-x) e^{x} \end{aligned}

整个式子：

F^(x)=∏i=1nfi^(x)=enx∏i=1n(ai−x)\hat{F}(x)=\prod_{i=1}^n \hat{f_i}(x)=e^{nx}\prod_{i=1}^n (a_i-x)

令 G(x)=∏i=1n(ai−x)G(x)=\prod_{i=1}^n (a_i-x) ，可以方便得求出所有系数 gp=[xp]G(x)g_p=[x^p]G(x) 。

我们要求的是 [xk]F^(x)[x^k]\hat{F}(x) ：

[xk]F^(x)=[xk]G(x)∗enx=∑j=0kgjnk−j(k−j)!\begin{aligned} \left[x^k\right]\hat{F}(x)&=[x^k]G(x)\ast e^{nx}\\ &=\sum_{j=0}^{k} g_{j} \frac{n^{k-j}}{(k-j)!} \end{aligned}

然后 jj 枚举其实到 nn 就够了，G(x)G(x) 只有 nn 项。可得答案：

E=k!nk∑j=0ngjnk−j(k−j)!=∑j=0nkj‾gjnj\begin{aligned} \mathbb{E}&=\frac{k!}{n^k}\sum_{j=0}^{n} g_{j} \frac{n^{k-j}}{(k-j)!}\\ &=\sum_{j=0}^{n} k^{\underline{j}}\frac{g_{j}}{n^j}\\ \end{aligned}

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
template<typename _Tp>
inline void read(_Tp &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(_Tp)(ch^48),ch=getchar();
    if(fg) x=-x;
}
template<typename _Tp,typename... Args>void read(_Tp &t,Args &... args){read(t);read(args...);}
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 5005;
int n,k,a[N];
ll g[2][N],invn;
ll fpow(ll a,ll b=mod-2) {
    ll r=1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) r=r*a%mod;
    return r;
}
template<typename Tp> void Add(Tp &x, Tp y) {x=(x+y)%mod;}
template<typename Tp> void Mul(Tp &x, Tp y) {x=(x*y)%mod;}

int main() {
    read(n,k);
    ll ans=1,pp=1;
    for(int i=1;i<=n;++i) read(a[i]),Mul(ans,(ll)a[i]);
    g[0][0]=1; bool V=0;
    invn=fpow(n);
    for(int i=1;i<=n;++i) {
        memset(g[V^1],0,sizeof(g[V^1]));
        for(int j=0;j<i;++j) {
            g[V^1][j+1]=(mod-g[V][j]);
            Add(g[V^1][j],g[V][j]*a[i]%mod);
        }
        V^=1;
    }
    for(int j=0;j<=n;++j) {
        Add(ans,mod-pp*g[V][j]%mod);
        Mul(pp,(ll)invn*(k-j)%mod);
    }
    printf("%lld\n",ans);
    return 0;
}