题目大意
给定一个有 \(n\) 个整数的序列 \({a_n}\)，有一个初始为 \(0\) 的值 \(res\)，重复下面的过程 \(k\) 次：
随机选择一个 \([1,n]\) 之间的下标
\(x\)，\(res\) 加上所有满足 \(i\neq x\) 的 \(a_i\) 的乘积，然后将 \(a_x\) 减去 \(1\)。
求最后 \(res\) 的期望值，对 \(10^9+7\) 取模。
\(1\leq n\leq5\times10^3,1\leq
k\leq10^9\)
题目分析
可以发现，每一次 \(res\)
加上的值其实就是操作之前的 \(a\)
的积减去操作之后的 \(a\) 的积。
将这一连串的求和相消，发现最后只剩下最开始的 \(a\) 的积减去最后 \(a\) 的积。
我们现在只要求最后的 \(a\)
的积的期望。
我们令 \(F_j(x)\) 表示序列第 \(j\) 个数对答案贡献的生成函数，显然有：
\[
\begin{align}
F_j(x)&=\sum_{i=0}^\infty \frac{(a_j-i)x^i}{i!}\\
&=(a_j-x)e^x
\end{align}
\]
那么答案的生成函数是
\[
\begin{align}
F(x)&=\prod_{i=1}^n{F_i(x)}\\
&=e^{nx}\prod_{i=1}^n(a_i-x)
\end{align}
\]
\(e^{nx}\) 很好求，后面的直接 \(O(n^2)\) 的 dp 暴力展开就好了。
时间复杂度\(O(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
| #include <iostream>
#include <cstdio>
using namespace std;
const int P=1000000007;
const int N=5005;
int f[N][N];
int a[N];
int n,k,ans,mul;
inline int calc(int st,int en)
{
int ret=1;
for (int i=st;i<=en;++i) ret=1ll*ret*i%P;
return ret;
}
inline int quick_power(int x,int y)
{
int ret=1;
for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
return ret;
}
int main()
{
freopen("lust.in","r",stdin),freopen("lust.out","w",stdout);
scanf("%d%d",&n,&k),mul=1;
for (int i=1;i<=n;++i) scanf("%d",&a[i]),mul=1ll*mul*a[i]%P;
f[0][0]=1;
for (int i=1;i<=n;++i)
for (int j=0;j<=i;++j)
f[i][j]=(1ll*f[i-1][j]*a[i]%P+(j?P-f[i-1][j-1]:0))%P;
ans=0;
for (int i=0;i<=n&&i<=k;++i) (ans+=1ll*f[n][i]*quick_power(n,k-i)%P*calc(k-i+1,k)%P)%=P;
ans=(mul+P-1ll*ans*quick_power(quick_power(n,k),P-2)%P)%P;
printf("%d\n",ans);
fclose(stdin),fclose(stdout);
return 0;
}
|