题解 P5907

· · 个人记录

学习了一个式子：

i^k=\left[\frac{x^k}{k!}\right]e^{ix}

即 i^k 是 e^{ix} EGF 的第 k 项。

用斯特林很难推的时候试试这个。

\sum_{i=0}^{n-1} i^ka^i =\left[\frac{x^k}{k!}\right]\sum_{i=0}^{n-1} e^{ix}a^i =\left[\frac{x^k}{k!}\right]\sum_{i=0}^{n-1} (ae^x)^i =\left[\frac{x^k}{k!}\right]\dfrac{(ae^x)^n-1}{ae^x-1}

重点：这里将 (ae^x-1)^{-1} 看成 (a(e^x-1)+a-1)^{-1}，就能广义二项式定理展开（a=1 时不能展开，但是原式变为 \sum_{i=1}^ni^k，这个可以拉插做到 O(k)）：

=\left[\frac{x^k}{k!}\right]((ae^x)^n-1)\sum_{i\ge 0}\dbinom{-1}{i}(a(e^x-1))^i(a-1)^{-1-i}

令 p=\frac{1}{1-a}，则：

=\left[\frac{x^k}{k!}\right]((ae^x)^n-1)(-p)\sum_{i\ge 0}(-1)^i(a(e^x-1))^i(-p)^i =\left[\frac{x^k}{k!}\right]((ae^x)^n-1)(-p)\sum_{i\ge 0}(pa(e^x-1))^i

发现求的是第 k 项系数，所以 i 只用枚举到 k：

=\left[\frac{x^k}{k!}\right]((ae^x)^n-1)(-p)\sum_{i=0}^k(pa)^i(e^x-1)^i

继续二项式定理展开：

=\left[\frac{x^k}{k!}\right]((ae^x)^n-1)(-p)\sum_{i=0}^k(pa)^i\sum_{j=0}^i\dbinom{i}{j}e^{jx}(-1)^{i-j}

把前面的东西乘进去：

=\left[\frac{x^k}{k!}\right](-p)\sum_{i=0}^k(pa)^i\sum_{j=0}^i\dbinom{i}{j}(a^n(e^x)^{j+n}-e^{jx})(-1)^{i-j}

这里把开头的式子逆运用一下：

=(-p)\sum_{i=0}^k(pa)^i\sum_{j=0}^i\dbinom{i}{j}(a^n(j+n)^k-j^k)(-1)^{i-j} =(-p)\sum_{j=0}^k(a^n(j+n)^k-j^k)\sum_{i=0}^k(pa)^i\dbinom{i}{j}(-1)^{i-j}

后面的枚举到了 k，考虑递推：

f_j=\sum_{i=0}^k(pa)^i\dbinom{i}{j}(-1)^{i-j} f_j-f_{j-1}=\sum_{i=0}^k(pa)^i\dbinom{i}{j}(-1)^{i-j}+\sum_{i=0}^k(pa)^i\dbinom{i}{j-1}(-1)^{i-j} =\sum_{i=0}^k(pa)^i\dbinom{i+1}{j}(-1)^{i-j} =\sum_{i=1}^{k+1}(pa)^{i-1}\dbinom{i}{j}(-1)^{i-j-1} =\dfrac{-f_j+(-1)^j-(pa)^{k+1}\binom{k+1}{j}(-1)^{k-j}}{pa}

所以：

f_{j-1}=f_j+\dfrac{f_j-(-1)^j+(pa)^{k+1}\binom{k+1}{j}(-1)^{k-j}}{pa}

可以 O(k) 递推。前面的 j^k 可以线性筛，(j+n)^k 可以区间筛。

注意 n\le k 时不能用这个式子，但是发现直接做复杂度就是对的。