description
给定 \(n,a,k\)，求 \(\sum\limits_{i=1}^n a^ii^k\)
-
\(n\leq 10^{18}\)
-
\(k\leq 2\cdot10^3\)
solution
\(k\) 很小，使用第二类斯特林数处理 \(i^k\) 得：
- \(\sum\limits_{i=1}^n a^i \sum\limits_{j=0} \begin{Bmatrix} k \\ j\end{Bmatrix} \dbinom{i}{j}j!\)
调换求和顺序得：
- \(\sum\limits_{j=0}^{\min(n,k)} j!\begin{Bmatrix} k\\j \end{Bmatrix} \sum\limits_{i=\min(1,j)}^n a^i \dbinom{i}{j}\)
左边的可以枚举，主要考虑如何计算右边。把 \(k=0\) 特判掉，答案变成 \(i\) 取下界 \(j\) 的答案再 \(-1\)。
记 \(f_{j,n}=\sum\limits_{i=j}^n a^i\dbinom{i}{j}\)。
根据组合数递推式，有：
- \(f_{j,n}=\sum\limits_{i=j}^n a^i (\dbinom{i-1}{j}+\dbinom{i-1}{j-1})=\sum\limits_{i=j}^n a^i\dbinom{i-1}{j}+\sum\limits_{i=j}^n a^i \dbinom{i-1}{j-1}=af_{j,n-1}+af_{j-1,n-1}\)
设 \(F_n(x)\) 是 \(\{f_{j,n}\}_{j=0}^{+\infty}\) 得生成函数，则有 \(F_{n}(x)=a(x+1)F_{n-1}(x)+1\)。（注意最后这个 \(+1\)，是常数项需要特殊处理的，可以把 \(f_{i,j}\) 打表出来就会发现这一点）
于是可以多项式矩阵快速幂求出 \(F_n(x) \pmod {x^{k+1}}\) 了。问题是模数是 1e9+7，\(O(k\log k\log n)\) 在矩阵和任意模数的巨大常数下会很慢，而且代码太复杂。
解决办法是用朴素的多项式乘法代替 NTT，虽然时间复杂度变为 \(O(k^2\log n)\)，但是常数小了，也好写。
开 O2 勉强卡过去。
当然，也可以对生成函数进行进一步推导，发现需要多项式快速幂 + 多项式求逆。朴素做多项式乘法的话求逆和 \(\ln \exp\) 都是 \(O(k^2)\) 的，所以可以做到 \(O(k^2)\) 的时间复杂度。