题意简述

给定长度为 $n$ 的数组 $a$ 和整数 $v$。执行 $m$ 次操作，每次操作均匀随机选择一个位置 $p \in [1, n]$，然后对 $a_p, a_{p+1}, \dots, a_n$ 加上 $v$。求最终 $\prod_{i=1}^n a_i$ 的期望值，结果对 $M = 10^9 + 7$ 取模。

---

思路分析

1. 将增量视为随机变量

设随机变量 $x_{k,i}$ 表示第 $k$ 次操作对 $a_i$ 的增量。若该次操作选择的位置 $p_k \le i$，则 $x_{k,i} = v$；否则 $x_{k,i} = 0$。
操作完成后：

$$a_i' = a_i + \sum_{k=1}^m x_{k,i}$$

目标为计算：

$$E\left[\prod_{i=1}^n \left(a_i + \sum_{k=1}^m x_{k,i}\right)\right] $$

2. 展开乘积与期望的线性性

将乘积完全展开，每一项是从 $n$ 个因子中各选一项（选 $a_i$ 或某个 $x_{k,i}$）相乘。由期望的线性性，我们可对每一项单独求期望再求和。

考虑展开式中的某一项。对于固定的操作 $k$，假设它在下标集合 $S_k \subseteq [1,n]$ 的位置上被选中（即该项中包含了 $x_{k,i}, i \in S_k$）。若 $S_k = \emptyset$，该操作对此项无贡献（相当于因子 $1$）。若 $S_k \neq \emptyset$，该项非零当且仅当 $p_k \le \min S_k$，此时所有被选中的 $x_{k,i} = v$。因此该操作带来的因子期望为：

$$E\left[\prod_{i \in S_k} x_{k,i}\right] = v^{|S_k|} \cdot \Pr(p_k \le \min S_k) = v^{|S_k|} \cdot \frac{\min S_k}{n} $$

由于不同操作的 $p_k$ 相互独立，整个项的期望等于各操作期望的乘积，再乘上那些选择了 $a_i$ 的常数因子。

3. 动态规划状态设计

为了高效计算所有项期望的总和，我们可以逐位置构建因子，同时维护有多少个不同的操作已经“出现”。这里“出现”是指该操作的最小选中位置已经确定。

设 $\text{dp}[i][j]$ 表示：已经处理了前 $i$ 个位置（下标 $1 \sim i$），且在这些位置中，恰好有 $j$ 个不同的操作已经至少被选中一次（即它们的最小选中位置 $\le i$）时，所有已构造的部分项期望之和。

初始状态：$\text{dp}[0][0] = 1$。

4. 状态转移

当我们考虑第 $i$ 个因子（即 $a_i'$ 的组成）时，有两种选择：

• 选择原始 $a_i$ 或已出现操作的贡献
  若前 $i-1$ 个位置已有 $j$ 个操作出现，它们对当前位置 $i$ 一定会贡献 $v$（因为它们的 $p_k \le i-1 < i$）。加上 $a_i$ 自身，这部分贡献为 $a_i + j \cdot v$。
  这类选择不会增加新操作，转移至 $j$ 不变：

  $$\text{dp}[i][j] \mathrel{+}= \text{dp}[i-1][j] \times (a_i + j \cdot v) $$

• 选择一个新的操作
  我们要引入一个之前从未出现过的操作，并且该操作必须在位置 $i$ 首次被选中（即它的 $p_k = i$）。这样其最小选中位置就是 $i$。
  一次操作恰好在 $i$ 处首次出现的期望贡献为 $v \cdot \frac{i}{n}$。未使用的操作还有 $m - j$ 个，从中任选一个作为新操作。因此转移为：

  $$\text{dp}[i][j+1] \mathrel{+}= \text{dp}[i-1][j] \times \frac{i \cdot v}{n} \times (m - j) $$

在实现时，除法用模 $M$ 下的逆元处理，$n$ 的逆元可预处理。注意 $j$ 至多为 $\min(n, m)$，复杂度 $O(n \cdot \min(n, m))$，在 $n \le 5000$ 时完全可行。

5. 最终答案

处理完所有 $n$ 个位置后，所有项都已计入对应的 $\text{dp}[n][j]$ 中（$j$ 为该项实际使用到的不同操作个数）。因此答案就是对所有可能的 $j$ 求和：

$$\text{ans} = \sum_{j=0}^{\min(n,m)} \text{dp}[n][j] \bmod M $$

---

复杂度

• 时间复杂度：$O(n \cdot \min(n, m))$，即 $O(n^2)$。
• 空间复杂度：$O(n^2)$ 或使用滚动数组优化至 $O(n)$。

---

参考代码（逻辑与标程一致）

#include <bits/stdc++.h>
using namespace std;

const int N = 5008, P = 1e9 + 7;
int n, m, v, a[N], dp[N][N];

long long Pow(long long a, int k) {
    long long res = 1;
    while (k) {
        if (k & 1) res = res * a % P;
        a = a * a % P, k >>= 1;
    }
    return res;
}

int main() {
    cin >> n >> m >> v;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    dp[0][0] = 1;
    long long inv_n = Pow(n, P - 2);
    
    for (int i = 1; i <= n; ++i) {
        long long coef = i * inv_n % P * v % P;  // v * i / n
        for (int j = 0; j < i; ++j) {
            // 选择新操作
            dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j] * coef % P * (m - j)) % P;
            // 选择原始 a_i 或已出现的操作
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * (a[i] + 1LL * j * v % P)) % P;
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= n; ++j)
        ans = (ans + dp[n][j]) % P;
    cout << ans << '\n';
    return 0;
}