不知道哪里来的经典题
给定 P,Q,N,M 求 \begin{aligned}\sum_{k\geq 0}^NP^kk^Q\end{aligned} \pmod M , N,M\leq 10^9, P,Q\leq 2\times 10^3
Part 1.
如果 M \in \rm Prime ，存在 O(Q^2) 的线性递推
令 S_Q = \sum_{k\geq 0}^{n}P^kk^Q
\begin{aligned}
S_Q &= \sum_{k\geq 0}^{n-1} P^{k+1}(k+1)^Q\\
&=P\sum_{k\geq 0}^{n-1}P^k\sum_{i\geq 0}^Q\binom{Q}{i}k^i\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}\sum_{k\geq 0}^{n-1}P^{k}k^i\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}\left((\sum_{k\geq 0}^{n}P^kk^i)-P^nn^i\right)\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}\left(S_i-P^nn^i\right)\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}S_i-\sum_{i\geq 0}^Q\binom{Q}{i}P^{n+1}n^i\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}S_i-P^{n+1}\sum_{i\geq 0}^Q\binom{Q}{i}n^i\\
&=P\sum_{i\geq 0}^Q\binom{Q}{i}S_i-P^{n+1}(n+1)^Q\\
&\Rightarrow (1-P)S_{Q}= P\sum_{i\geq 0}^{Q-1}\binom{Q}{i}S_i - P^{n+1}(n+1)^Q
\end{aligned}
易知要求 (1-P)^{-1} 必须存在。
对于 P = 1 的情况，考虑按照原来的式子解出 S_{Q-1} 即可。
\begin{aligned}
S_Q &= \sum_{k=1}^nP^kk^Q\\
&=\sum_{k=0}^{n-1}P^{k+1}(k+1)^Q\\
&=\sum_{k=0}^{n-1}\sum_{j=0}^Q\binom{Q}{j}k^j\\
&=\sum_{j=0}^{Q}\binom{Q}{j}\sum_{k=0}^{n-1}k^j\\
&=\sum_{j=0}^Q\binom{Q}{j}\left(S_{j}-n^j+[j=0]\right)\\
\Rightarrow S_Q&= \left(\sum_{j=0}^{Q-1}\binom{Q}{j}\left(S_j-n^j+[j=0]\right)\right)+S_Q-n^Q\\
\Rightarrow S_{Q-1}&=\frac{Qn^{Q-1}+n^{Q}-\sum_{j=0}^{Q-2}\binom{Q}{j}\left(S_j-n^j+[j=0]\right)}{Q}
\end{aligned}
Part 2.
如果 M 无要求，需要倍增绕开求逆 (容易联想到 tutte多项式倍增绕开求逆 这一操作)
令 S_{Q,n}=\sum_{k\geq 0}^{n-1}P^kk^Q ，则 S_{Q,2n+1}= S_{q, 2n} + P^{2n}(2n)^Q
\begin{aligned}
S_{Q,2n}&=\sum_{k\geq 0}^{2n-1}P^kk^Q\\
&=S_{Q,n}+\sum_{k\geq 0}^{n-1}P^{n+k}(n+k)^Q\\
&=S_{Q,n}+P^n\left(\sum_{k\geq 0}^{n-1}P^k\sum_{i\geq 0}^Q\binom{Q}{i}k^in^{Q-i} \right)\\
&=S_{Q,n}+P^n\left(\sum_{i\geq 0}^{Q}\binom{Q}{i}n^{Q-i}\sum_{k\geq 0}^{n-1}P^kk^i \right)\\
&=S_{Q,n}+P^n \sum_{i\geq 0}^{Q}\binom{Q}{i}n^{Q-i}S_{i,n}
\end{aligned}
O(Q^2)预处理二项式系数，同时对于每个 Q 预处理 n^{0...Q} 即可
显然对于某层 x 需要求出 S_{0...Q,x} 对于任意一个 S_{Q,x} 的求取是 O(Q) 的，一共 \log n层
综上总复杂度 O(Q^2\log n) 倍增即可。
Part 3.
如果 M 是 ntt 模数
设f_{Q}=\sum_{k\geq 0}^nP^kk^Q, F(x)=\sum_{Q\geq 0} \frac{1}{Q!}f_Qx^Q
\begin{aligned}
F(x)&=\sum_{Q\geq 0} \frac{1}{Q!}f_Qx^Q\\
&=\sum_{Q\geq 0}\frac{1}{Q!}\sum_{k\geq 0}^{n}P^kk^Qx^Q\\
&=\sum_{k\geq 0}^nP^k\sum_{Q\geq 0}\frac{k^Q}{Q!}x^Q\\
&=\sum_{k\geq 0}^nP^k{\rm e}^{kx}\\
&=\sum_{k\geq 0}^n(P{\rm e}^x)^k\\
&=\frac{1-\left(P{\rm e}^{x}\right)^{n+1}}{1-P{\rm e}^x}
\end{aligned}
Part 4.
回到原问题
\begin{aligned}\sum_{k\geq 0}^NP^kk^Q\end{aligned}
容易发现上面的操作基于 k \geq 0 。如果盲目变动下标，当 Q=0 \and k=0 的时候会出现错误。
Part 5. CCPC2022 Guilin D : Alice's dolls
根据分布律可以得到 n=1 时候 E(x^k)=f_k=\sum_{i\geq 1}q^{i-1}p ^1i^k
设 F(x) 是 f_k 的 \rm EGF ，根据多项式卷积系数可以知道对于 n,k 的答案即为 [x^k]F^n(x)
通过 \exp 和 求逆 在O(n\log n) 时间内得到或者 求逆 和 快速幂 在 O(n\log ^2 n) 时间内得到目标gf 的系数。
经过处理，得到
f_{k}=\frac{p}{q}\sum_{i\geq 0}q^ii^k
按照上面的方法处理得到
F(x)=\frac{p}{q(1-q{\rm e}^x)}
但是，注意到题面规定 q=1-p\in[0,1)，因此当 q=0 时， 对应的逆不存在，不能对 q^{-1} 做提取。
有两种对应方法：
- 特判，显然 \forall i,f_i=1，因此 F(x)={\rm e}^x
- 更换处理方法。
法一：
\begin{aligned}
\frac{f_k}{p}&=\sum_{i\geq 1} q^{i-1}i^k\\
&=\sum_{i\geq 0}q^i(i+1)^k\\
&=\sum_{i\geq 0}q^i\sum_{j\geq 0}^k\binom{k}{j}i^j\\
&=\sum_{j\geq 0}^k\binom{k}{j}\sum_{i\geq 0}q^ii^j\\
&=\sum_{j\geq 0}^k\binom{k}{j}\sum_{i\geq 1}q^ii^j\\
&=\sum_{j\geq 0}^k\binom{k}{j}q\sum_{i\geq 1}q^{i-1}i^j\\
&=\sum_{j\geq 0}^k\frac{k!q}{(k-j)!j!}f_j\\
\Rightarrow \frac{f_k}{k!p}-qf_k&=\sum_{j\geq 0}^{k-1}\frac{f_j}{j!}\frac{q}{(k-j)!}
\end{aligned}
看起来可以 cdq分治+ntt 在 O(n\log^2n) 的时间内求出来
法二：
不变换 f_k 的对应和式的下限，直接设 \rm EGF
\begin{aligned}
F(x)&=p\sum_{k\geq 0}\frac{1}{k!}\sum_{i\geq 1}q^{i-1}i^kx^k\\
&=p\sum_{i\geq 1}q^{i-1}\sum_{k\geq 0}\frac{x^ki^k}{k!}\\
&=p\sum_{i\geq 0}q^i{\rm e}^{(i+1)x}\\
&=p{\rm e}^x\sum_{i\geq 0}q^i{\rm e}^{ix}\\
&=p\frac{{\rm e}^x}{1-q{\rm e}^x}
\end{aligned}
多项式求逆即可。
当然，对 f 做错位相减也可以化简后得到对应的egf.