题解 P7435 【简单的排列计数】
Aleph1022
·
·
题解
让我们跳过 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 给出的四个角度的证明。