题解 P7423 【简单构造题】

· · 题解

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

自然的想法是拆开贡献，长为 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 回去就好了.