CF_#446(Div. 1)_E

题目传送门
题意: 给你一个序列并执行$k$次操作,每次选择一个数减一,并给$res$加上其它数的乘积,求最后$res$的期望值

分析: 思考一下就会发现,对于每种操作方案,最后的$res$都是初始序列各数的乘积减去操作完后各数乘积.
所以最后的期望答案就是$ans = \prod_{i=1}^{n}a_{i} - k!/ n^{k} \sum_{\sum_{i=1}^{n}x_{i}=k}\prod_{i=1}^{n}(a_{i} - x_{i})/x_{i}!$
我们可以发现上述式子中存在一个卷积,并且存在分母为阶乘的分式,那么就可以很自然的想到指数型生成函数.
因为$\sum (a_{i} - j)x^{j}/j!=(a_{i} - x)e^{x}$,所以有$ans=\prod_{i=1}^{n}a_{i} - k!/ n^{k}e^{nx}\prod_{i=1}^{n}(a_{i} - x)$,我们只需要求出这个生成函数的第$x^{k}$项的系数即可.
通过$n^{2}$暴力求解最右边的连乘,然后枚举连乘部分所占的指数系数大小即可求得答案.

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
45
46
47
48
49
50
51
52
53
54
55
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int add(int x,int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int mul(int x,int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int powt(int a,int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(r,a);
a = mul(a,a);
b >>= 1;
}
return r;
}
int a[5005],f[5005];
int main(){
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,k,i,j,u,s,ans = 0;
scanf("%d%d",&n,&k);
for(i = 0,s = f[0] = 1;i < n; i++) {
scanf("%d",&a[i]);
s = mul(s,a[i]);
for(j = i;j >= 0; j--) {
f[j + 1] = add(f[j + 1],mod - f[j]);
f[j] = mul(f[j],a[i]);
}
}
for(i = 0,u = 1;i <= min(k,n); i++) {
ans = add(ans,mul(mul(u,f[i]),powt(n,k - i)));
u = mul(u,k - i);
}
ans = add(s,mod - mul(ans,powt(powt(n,k),mod - 2)));
printf("%d\n",ans);
return 0;
}