CF891E Lust

题意：给定长度为 $n$ 序列 $a$，每次随机选择 $i\in [1, n]$，将 $r$ 加上 $\prod_{j\ne i} a_j$，然后让 $a_i$ 减 1。问 $k$ 次操作后，$r$ 的期望。$n\leq 5000$，$k\leq 10 ^ 9$，对 $10 ^ 9 + 7$ 取模。

首先给出一个结论：

$$r = \prod_{i = 1} ^ n a_i - \prod_{i = 1} ^ n a_i'$$

表示前后 $a_i$ 乘积的变化量。这个可以通过分每一步看来得到，既然单步是正确的，那么合并起来也是正确的。

现在显然是求变化后的期望。

考虑使用 EGF 计算每一步改变的哪一个位置，然后合并。单个的 EGF 可以写作：$\sum_{i = 0} \dfrac{x ^ i}{i!} (a - i)$。

那么最后变化后的期望就是：

$$\dfrac{k!}{n ^ k} [x ^ k] \prod_{i = 1} ^ n \sum_{j = 0} \dfrac{x ^ j}{j!}(a_j - x)$$

不是封闭形式不好计算，考虑对每一个 $\sum_{i = 0} \dfrac{x ^ i} {i!} (a - i)$ 变换来尝试得到封闭形式：

$$\begin{aligned} & \sum_{j = 0} \dfrac{x ^ j}{j!} (a - j)\\ =& \sum_{j = 0} \dfrac{x ^ ja}{j!} - \sum_{j = 0} \dfrac{x ^ jj}{j!}\\ =& ae ^ x - \sum_{j = 1} \dfrac{xx ^ {j - 1}}{(j - 1!)}\\ =& (a - x) e ^ x \end{aligned}$$

这样就变成的封闭形式。

乘起来可以得到：

$$\dfrac{k!}{n ^ k} [x ^ k] e ^ {nx} \prod_{i = 1} ^ n (a_i - x)$$

后面这个式子可以 $O(n\log ^ 2 n)$ 计算，但是直接 $O(n ^ 2)$ DP 计算每一位也不是不行。

下面对后面是贡献 $x ^ t$ 时 $x ^ k$ 的系数计算：

$$\dfrac{k!}{n ^ k} \times \dfrac{c_t n ^ {k - t}}{(k - t)!}$$

虽然 $k$ 很大，但是 $t$ 不大，这些都可以约到 $t$ 项，而且不同的 $t$ 可以递推计算，所以这不是难事，可以在 $O(n)$ 或者 $O(n\log k)$ 的时间内求出所有 $t\in [0, n]$ 的贡献。

总时间复杂度 $O(n ^ 2)$，狗都不写 MTT。注意代码中的 f[t] 求的是 $n - t$ 的系数。

int main()
{
	std::cin >> n >> k;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	f[0] = 1;
	for (int i = 1; i <= n; ++ i)
		for (int j = i - 1; ~j; -- j)
			f[j + 1] = (f[j + 1] + (LL) f[j] * a[i]) % Mod;
 
	int res = 0, cur = k;
	for (int i = 1; i <= n && i <= k; ++ i)
	{
		if (!(i & 1))
			res = (res + (LL) (Mod - cur) * qpow(n, k - i) % Mod * f[n - i]) % Mod;
		else res = (res + (LL) cur * qpow(n, k - i) % Mod * f[n - i]) % Mod;
		cur = (LL) cur * (k - i) % Mod;
	}
	res = (LL) res * qpow(n, Mod - 1 - k) % Mod;
	// adj(res = f[n] - res);
	std::cout << res << '\n';
	return 0;
}