[数学记录]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)。

评测记录