自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:29:44，当前版本为作者最后更新于2021-03-06 19:12:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

鱼推得有点过于神秘，，，展开了大量的不必要的细节. 这是个正常的推法

自然的想法是拆开贡献，长为 $i$ 的区间有贡献系数 $(n-i+1)m^{n-i}$，于是只需要求出每种长度的区间的贡献之和. 对每种权值分别考虑，则答案的 EGF 即

$$\prod_{i=1}^m\left(1+\sum_{j\geq 1}\frac{ji^jx^j}{j!}\right)=\prod_{i=1}^m(1+ixe^{ix}) $$

我们直接一般化为计算

$$\prod_{i=1}^mF(ix)$$

简单起见，假设 $[x^0]F(x)=1$. 取对数，得

$$\begin{aligned} &\sum_{i=1}^m\ln F(ix) \\=&\sum_{i=1}^m\sum_{j\geq 1}\left([x^j]\ln F(x)\right)i^j \\=&\sum_{j\geq 1}\left([x^j]\ln F(x)\right)\left(\sum_{i=1}^mi^j\right) \end{aligned} $$

于是只需要求出 $\ln F(x)$ 以及自然数幂和. 自然数幂和容易计算:

$$\sum_{i\geq 0}\frac{x^i}{i!}\sum_{j=1}^mj^i=\sum_{j=1}^me^{jx}=e^x\frac{1-e^{mx}}{1-e^x} $$

把两个东西点乘最后 exp 回去就好了.