G.
定义一次操作：随机选择 $i \in [1, n]$，对所有 $j \in [i, n]$，使得 $a_j = a_j + v$。
$n \leq 5000, m, v \leq 10^9$，m 为操作次数。
求 $\prod a_i$ 的期望值。
$\prod (ai+v+…)$ 每个括号里面选一个产生贡献，只有三种情况。
- 选择 $a_i$
- 选择以前用过的 $v$，贡献系数为 $j \times v$，$j$ 为之前操作过的次数。
- 选择以前没有用过的 $v$，贡献系数为 $(m-j) \times i \times v$，$m - j$ 表示在没有选过的里面选一个，$i$ 表示可以操作在 $[1, i]$。
所以定义 $f_{i, j}$ 为目前长度为 $i$，使用了 $j$ 次操作的期望乘法值。
最后答案为 $\frac{\sum f_{i,j} \times n^{m-j}}{n^m}$。
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
| const int P = 1e9 + 7;
int power(int x, int y) {
int res = 1;
while (y) {
if (y % 2 == 1) {
res = 1ll * res * x % P;
}
x = 1ll * x * x % P;
y /= 2;
}
return res;
}
int inv(int x) { return power(x, P - 2); }
void md(int &x) {
if (x >= P)
x -= P;
}
void solve() {
int n, m, v;
cin >> n >> m >> v;
vi a(n);
rep(i, n) cin >> a[i];
vc<vi> f(n + 1, vi(n + 2));
f[0][0] = 1;
rep(i, n) {
rep(j, min(n, m) + 1) {
md(f[i + 1][j] += 1ll * (a[i] + (1ll * j * v) % P) * f[i][j] % P);
md(f[i + 1][j + 1] += 1ll * (m - j) * (i + 1) % P * v % P * f[i][j] % P);
}
}
int ans = 0;
rep(i, min(n, m) + 1) md(ans += 1ll * f[n][i] * power(n, m - i) % P);
cout << 1ll * ans * inv(power(n, m)) % P << "\n";
}
|
