第一次听没听懂，补个笔记。弄懂这种奇妙拆贡献后感觉非常厉害。
答案的形式为：\(\prod (a_i + k \cdot v)\)，这些 \(v\) 是前面的操作带来的影响。
我们考虑一个个加入这个 \((a_i + k \cdot v)\)，并且维护很多个等价类，使得这个值可以根据分开等价类的那个标志被确认。
\(k\)，不过是前面的数字被操作了多少次。因此划分等价类的标志是：前面的数字一共被操作了多少次。即：\(f_{i, j}\) 表示：考虑前 \(i\) 个数，这些数字加起来被操作了 \(j\) 次，\(\prod (a_i + k \cdot v)\) 值之和。
转移：
\[f_{i, j} (a_i + v(j + k)) \to f_{i, j+k} \]这个是 \(O(n^3)\) 的，过不去。
发现复杂度瓶颈是枚举 \(k\)，也就是，操作多少次当前点。我们拆开这 \(k\) 次操作，也不计算这 \(k\) 次操作带来的贡献。或者说，这 \(k\) 次操作直到后面才会影响不同的值，因此，到后面再做区分。
因为不区分多次操作，这启示我们分开所有 \(v\) 的贡献，即：用分配律拆开全部式子，每一项是 \(v\) 或一个 \(a_i\)，计算和。
转移时，枚举产生贡献的是 \(a_i\)，已经被使用过的操作带来的 \(v\)，还是新开一次操作，同时枚举它的对象，让它的 \(v\) 产生贡献。
\(f_{i, j}\) 意义不变，转移式：
\[\begin{cases} f_{i, j} \cdot j \cdot v \to f_{i+1, j} \\ f_{i, j} \cdot (i+1) \cdot (m-j) \to f_{i+1, j+1} \\ f_{i, j} \cdot a_{i+1} \to f_{i+1, j} \end{cases} \]第二个转移同时枚举了操作的标号、操作的位置。
这样的本质是什么呢，是操作直到后面生效时才会被区分。通过把贡献式拆成 \(a_i\) 和 \(v\) 的乘积，每一项最多只会涉及一次操作，这样就降下了枚举操作次数的复杂度。
注意到有一些操作直到最后都没有被区分，答案是 \(\sum f_{n, i} n^{m-i}\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
int n, m;
modint v;
scanf("%d %d %d", &n, &m, &v);
std::vector<modint> a(n);
for (modint &x : a) scanf("%d", &x);
std::vector<modint> f(n + 1);
f[0] = 1;
for (int i = 0; i < n; i++) {
std::vector<modint> g(n + 1);
for (int j = 0; j <= i; j++) {
g[j] += f[j] * j * v;
g[j + 1] += f[j] * (i + 1) * (m - j) * v;
g[j] += f[j] * a[i];
}
f = g;
}
modint ans;
for (int i = 0; i <= m && i <= n; i++) {
ans += f[i] * qpow(n, m - i);
}
ans = ans / qpow(n, m);
printf("%d\n", ans);
return 0;
}