[数学记录]P5850 calc加强版

**题意** : 写一个长度为 $n$ 的数列 $A$ ,要求值域在 $[1,k]$ (整数),不能出现相同的数,权值为所有数的乘积。 问所有合法数列的权值和。 ------------ 首先题目中给出的的数列是有序的,去掉个$n!$就变成无序的。 然后考虑每个数只能选一次,而且占1个位置,大概是个背包。 弄一弄得到$F(x)=\prod\limits_{p=1}^k(1+px)$就是答案。 直接分治NTT肯定药丸,我们考虑对每个式子 $\ln$ 之后加起来再$EXP$回去。 (可以参照`P4389`) 由$\ln(F(x))=∫F'(x)F(x)^{-1}$ $(1-x)'=-1$ $\dfrac{1}{1-x}=\{1,1,1,1...\}$ $\dfrac{(1-x)'}{1-x}=-1*\{1,1,1,1...\}$ $ln(1-x)=-1*\{0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4}...\}$ 这就是说$ln(1-x)=-\sum\limits_{i=1}^n\dfrac{x^i}{i}$ 代入用 $-px$ 代换 $x$ 得到 : $\ln(1+px)=-\sum\limits_{i=1}^n\dfrac{(-px)^i}{i}=-\sum\limits_{i=1}^n\dfrac{(-1)^{i}p^i}{i}x^i$ 那么 $\ln(F(x))=\sum\limits_{p=1}^k\ln(1+px)=$ $-\sum\limits_{p=1}^k\sum\limits_{i=1}^n\dfrac{(-1)^{i}p^i}{i}x^i$ $=-\sum\limits_{i=1}^n\dfrac{(-1)^{i}\sum\limits_{p=1}^kp^i}{i}x^i$ 现在问题就在于快速求自然数幂和,这里一共要求$\sum\limits_{p=1}^kp^i\ (i∈[1,n])$。 考虑这东西的`EGF` : $\sum\limits_{i=0}\dfrac{x^i\sum_{p=1}^kp^i}{i!}$ $=\sum_{p=1}^k\sum\limits_{i=0}\dfrac{(px)^i}{i!}$ $=\sum_{p=1}^k(e^x)^p=\dfrac{1-e^{x(k+1)}}{1-e^x}$ 写个多项式求逆就好了,注意这个分式上下有公因式 $x$ 要消掉,不能直接莽。 最后一个 EXP 带走就好,复杂度 $O(n\log n)$。 [评测记录](https://www.luogu.com.cn/record/28964923)