首先膜鎕~~

问题很简单，求 $\sum_{i=1}^{n}i^{k}b^{i}$。原问题是对一个质数取模，这里我们拓展为对一个质数的幂 $p^{e}$ 取模。下面分为三类讨论：

• 若 $b\equiv0\pmod{p}$，那么我们至多只需要求前 $e$ 项即可。

• 若 $b\equiv1\pmod{p}$，设 $b=up+1$，那么原式等于 $$ \begin{aligned} &\sum_{i=1}^{n}i^{k}(up+1)^{i}\\ =&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{i}{i\choose j}(up)^{j}\\ =&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{e-1}{i\choose j}(up)^{j}\\ =&\sum_{j=0}^{e-1}(up)^{j}\sum_{i=1}^{n}i^{k}{i\choose j} \end{aligned} $$ 注意到 ${i\choose j}$ 是一个关于 $i$ 的 $j$ 次多项式，因此上式是一个关于 $i$ 的 $k+e$ 次多项式。使用插值计算即可。时间复杂度 $\mathcal{O}(k+e+\log_{p}x)$。

• 其它情况（以下做法来源于tls的题解）：

  记所求式子为 $f(n)$。

  首先我们证明：原式可被表示为 $f(n)=b^{n}F(n)-F(0)$，其中 $F$ 是关于 $n$ 的某个 $k$ 次多项式。

  $k=0$ 时： $$ \begin{aligned} f(n)&=\sum_{i=1}^{n}b^{i}\\ &=\frac{b^{n+1}-b}{b-1}\\ &=b^{n}\cdot\frac{b}{b-1}-\frac{b}{b-1} \end{aligned} $$ 显然成立。

  $k\ge1$ 时： $$ \begin{aligned} bf(n)-f(n)&=\sum_{i=1}^{n}i^{k}b^{i+1}-\sum_{i=1}^{n}i^{k}b^{i}\\ &=n^{k}b^{n+1}+\sum_{i=1}^{n}b^{i}\left[(i-1)^{k}-i^{k}\right]\\ &=n^{k}b^{n+1}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}\sum_{i=1}^{n}i^{j}b^{i}\\ &=n^{k}b^{n+1}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}\left[b^{n}F_{j}(n)-F_{j}(0)\right]\\ &=b^{n}\left(bn^{k}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(n)\right)-\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(0) \end{aligned} $$ 也成立。这意味着 $F_{k}(n)=bn^{k}+\sum_{j=0}^{k-1}(-1)^{j}{i\choose j}F_{j}(n)$。

  现在我们只需要求出 $F(0),\cdots,F(k)$，即可插值求出 $f(n)$。设 $F(0)=x$，那么我们很容易用 $x$ 来表示 $F$：$F(n)=\frac{f(n)+x}{b^{n}}$。下面我们证明，$\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}F(i)=0$ 对于任何 $k$ 次多项式都成立。这样我们就得到了一个一次方程，可以解出 $x$。

  首先证明一个引理：对任意 $0\le j\le k$，$\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}{i\choose j}=0$： $$ \begin{aligned} &=\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose j}{k+1-j\choose i-j}\\ &={k+1\choose j}\sum_{i=0}^{k+1-j}(-1)^{i+j}{k+1-j\choose i}\\ &=0 \end{aligned} $$ 而 $F(i)$ 可以表示为 ${i\choose 0},{i\choose 1},\cdots,{i\choose k}$ 的线性组合，那么之前的结论是显然的。

  另外注意到这个一次方程的未知数的系数是 $\sum_{i=0}^{k+1}(-1)^{i}{k+1\choose i}\left(\frac{1}{b}\right)^{i}=\left(\frac{b-1}{b}\right)^{k+1}$，而 $b$ 模 $p$ 不为 $0$ 或 $1$，因此这个方程是有唯一解的。

  时间复杂度 $\mathcal{O}(k+\log_{p}x)$。

时间复杂度不一定准确