自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:29:50，当前版本为作者最后更新于2021-03-14 16:36:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

让我们跳过 DP，快进到生成函数

$$\prod\limits_{i=1}^n \frac{1-(ix)^i}{1-ix}$$

反手一个 ln / exp，

$$\exp \sum\limits_{i=1}^n (\ln (1-(ix)^i)-\ln(1-ix)) $$

然后

$$\begin{aligned} \sum\limits_{i=1}^n \ln (1-(ix)^i) &= -\sum\limits_{i=1}^n \sum\limits_{j\ge 1}\frac{(ix)^{ij}}{j} \end{aligned} $$

所以只需要调和级数复杂度地直接计算即可。

然后

$$\begin{aligned} \sum\limits_{i=1}^n \ln (1-ix) &= -\sum\limits_{i=1}^n \sum\limits_{j\ge 1}\frac{(ix)^j}{j} \\ &= -\sum\limits_{j\ge 1} \frac{x^j}{j} \sum\limits_{i=1}^n i^j \\ &= -\sum\limits_{j\ge 1} \frac{x^j}{j(j+1)} \sum\limits_{i=0}^j \binom{j+1}i B_i (n+1)^{j-i+1} \end{aligned} $$

其中 $\{B_i\}$ 为伯努利数，我们知道它的 EGF 即为 $\frac x{{\rm e}^x-1}$。
因此做一次求逆做一次卷积即可。

时间复杂度 $O(k \log k)$。

---

另外，关于 @cqbzljsqwq 提到的「规律」，我们可以在 Elegia：「营业日志 2020.5.20」 中查阅到更强的结论和 EI 给出的四个角度的证明。