题解 P5907 数列求和加强版 / SPOJ MOON4

· · 题解

可能更好的阅读体验

题目大意

给定 n,a,k，求

\sum_{i=1}^ni^ka^i

答案对 998244353 取模。

\texttt{Data Range:} 1\le k\le 10^7,1\le n,a\le 998244352

题解

前置芝士：有限微积分

原做法 因需求第二类斯特林数有着 \Theta(n\log n) 的瓶颈，这一做法不再适用。

但原做法仍有相当程度的借鉴性，具体地，设 f(n)=\displaystyle{\sum}_0^n{x^ka^x\delta x}，

则 f(x)=a^xg(x)-a^0g(0),g(x) 为 k 次函数。答案即 f(n+1)-f(1)。

若已知 g(0),g(1),g(2),\cdots g(k)，我们可以 \Theta(k) 拉格朗日插值求出 g(n+1)。

考虑如何求出 g(m)\ (0\le m\le k)，显然线性筛出 i^k 后 f(m) 可以 \Theta(k) 递推，于是

g(m)=a^{-m}(g(0)+f(m))

问题变成了如何求出 g(0) 。

$$\Delta^{k+1}g(0)=\sum_{i=0}^{k+1}\dbinom{k+1}{i}(-1)^{k+1-i}\mathrm{E}^ig(0)=0$$ $$\sum_{i=0}^{k+1}\dbinom{k+1}{i}(-1)^{k+1-i}g(i)=0$$ $$\sum_{i=0}^{k+1}\dbinom{k+1}{i}(-1)^{k+1-i}a^{-i}(g(0)+f(i))=0$$ $$g(0)(a^{-1}-1)^{k+1}+\sum_{i=0}^{k+1}\dbinom{k+1}{i}(-1)^{k+1-i}a^{-i}f(i)=0$$ $$g(0)=-(1-a^{-1})^{-k-1}\sum_{i=0}^{k+1}\dbinom{k+1}{i}(-a)^{-i}f(i)$$ 代入即可 $\Theta(k)$ 算出 $g(0)$。 特别的，$a=1$ 时，$f(x)=g(x),g(x)$为 $k+1$ 次而非 $k$ 次，直接插值即可。