自动搬运

查看原文

来自洛谷，原作者为

	warzone 梦违科学世纪

搬运于2025-08-24 22:15:30，当前版本为作者最后更新于2021-11-03 23:19:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

可能更好的阅读体验

题目大意

给定 $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)$ 。

$g(x)$ 为 $k$ 次函数，因此其 $(k+1)$ 阶差分为 $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$ 次，直接插值即可。