CF1842G 题解
namelessgugugu
·
·
题解
组合意义保平安。
题意
有一个长度为 n 的数组 a 和常数 v，对数组进行 m 次操作，每一次操作中，均匀随机一个 [1, n] 中的整数 p，对于所有 p \leq i \leq n，让 a_i \gets a_i + v，求最后 \prod\limits_{i=1}^n a_i 的期望值，对 10^9 + 7 取模。
#### 题解
考虑 $\prod a_i$ 的组合意义，相当于有一个 $n+1$ 个点顺次连接形成的道路，一个人从第 $1$ 个点出发，从第 $i$ 个点走到第 $i+1$ 个点有 $a_i$ 种方案，问这个人走到 $n+1$ 共有多少种方案。
而修改的意义是什么呢，相当于在 $p$ 处放下了一个神奇妙妙工具，这个人走到 $p$ 的时候会拿起这个工具，之后对于任意的 $i$，可以选一个手上有的工具以 $v$ 的方案数从 $i$ 走到 $i+1$。
注意到被使用过的工具数量不超过 $n$，可以考虑在 DP 时记录这个状态，复杂度应该能降下来。
具体地，定义 $f_{i, j}$ 表示考虑了前 $i$ 处，使用了 $j$ 个工具的方案数，转移分三类：
1. 使用 $a_{i+1}$，$f_{i + 1, j} \gets f_{i, j} \cdot a_{i+1}$；
2. 使用一个被使用过的工具，$f_{i+1, j} \gets f_{i, j} \cdot j \cdot v$；
3. 使用一个还未被使用过的工具，需要先确定这个工具是哪里来的，$f_{i+1, j+1} \gets f_{i, j} \cdot (i+1) \cdot (m-j)\cdot v$。
最后的答案即为 $\sum\limits_i \frac{f_{n, i}}{n^i}$。
#### 代码
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
typedef unsigned long long ull;
const int N = 5005, mod = 1000000007;
int n, m, v, a[N], f[N][N];
inline int qpow(int x, int y)
{
int res = 1;
for (; y; y >>= 1, x = 1ll * x * x % mod)
if (y & 1)
res = 1ll * res * x % mod;
return res;
}
int main(void)
{
scanf("%d%d%d", &n, &m, &v);
for (int i = 1; i <= n;++i)
scanf("%d", a + i);
f[0][0] = 1;
for (int i = 0;i < n;++i)
for (int j = 0; j <= std::min(m, i);++j)
{
f[i + 1][j] = (f[i + 1][j] + 1ll * f[i][j] * a[i + 1]) % mod;
f[i + 1][j] = (f[i + 1][j] + 1ll * f[i][j] * j % mod * v) % mod;
f[i + 1][j + 1] = (f[i + 1][j + 1] + 1ll * f[i][j] * (i + 1) % mod * v % mod * (m - j)) % mod;
}
int res = 0;
int iv = qpow(n, mod - 2);
for (int i = 0; i <= std::min(n, m); ++i)
res = (res + 1ll * f[n][i] * qpow(iv, i)) % mod;
printf("%d\n", res);
return 0;
}
```