##lv. 1
求 $$\sum_{i=1}^ni^k,\quad n\leq10^{18},k\leq2000$$ ，答案对 $10^9+7$ 取模。
本题是一切数列求和的基础，解法众多：
- 公式法
- 拉格朗日插值法
- 差分法
- ……
对于这道题的数据范围，最好写的当属预处理出伯努利数直接套公式啦。
根据等幂求和公式：
$$
\sum_{i=1}^ki^k=\frac{1}{k+1}\sum_{i=1}^{k+1}\binom{k+1}{i}B_{k+1-i}(n+1)^i
$$
其中 $B$ 为伯努利数，其定义为：
$$
\sum_{i=0}^n\binom{n+1}{i}B_i=0
$$
稍作变形可得：
$$
B_n=-\frac{1}{n+1}\sum_{i=0}^{n-1}\binom{n+1}{i}B_i
$$
那么我们可以 $O(n^2)$ 预处理出 $B$ ，然后 $O(n)$ 求出答案。
1 |
|
##lv. 2
求 $$\sum_{i=1}^ni^kr^i,\quad n,r\leq10^{18},k\leq5\times10^4$$ ，答案对 $10^9+7$ 取模。
先用小学生的套路：错位相减
设答案为 $F_{n,k,r}$
$$
\begin{eqnarray}
F_{n,k,r}&=&1^kr^1+2^kr^2+\dots+n^kr^n \tag{1}\
rF_{n,k,r}&=&1^kr^2+2^kr^3+\dots+n^kr^{n+1} \tag{2}\
\end{eqnarray}
$$
$(1)-(2)$ 得：（为方便表示，我们在 $(1)$ 后加一项 $(n+1)^kr^{n+1}$ 再减去）
$$
\begin{eqnarray}
(1-r)F_{n,k,r}&=&r+(2^k-1^k)r^2+(3^k-2^k)r^3+\dots+[(n+1)^k-n^k]r^{n+1}-(n+1)^kr^{n+1}\
&=&\sum_{i=1}^n[(i+1)^k-i^k]r^{i+1}+r-(n+1)^kr^{n+1}
\end{eqnarray}
$$
考虑继续化简， $(i+1)^k-i^k$ 可以用二项式定理展开为 $\displaystyle \sum_{j=1}^k\binom{k}{j}i^{k-j}$
带入原式：
$$
\begin{eqnarray}
(1-r)F_{n,k,r}&=&\sum_{i=1}^n\sum_{j=1}^k\binom{k}{j}i^{k-j}r^{i+1}+r-(n+1)^kr^{n+1}\
&=&r\sum_{j=1}^k\binom{k}{j}\sum_{i=1}^ni^{k-j}r^i+r-(n+1)^kr^{n+1}\
&=&r\sum_{j=1}^k\binom{k}{j}F_{n,k-j,r}+r-(n+1)^kr^{n+1}
\end{eqnarray}
$$
整理得：
$$
F_{n,k,r}=\frac{(n+1)^kr^{n+1}-r\left(\sum_{j=1}^k\binom{k}{j}F_{n,k-j,r}+1\right)}{r-1},\quad r\neq1
$$
这样，我们就得到了一个递归式，边界是 $\displaystyle F_{n,0,r}=\sum_{i=1}^nr^i=\frac{r(r^n-1)}{r-1}$
当 $r=1$ 时，$\displaystyle F_{n,k,1}=\sum_{i=1}^ki^k=\frac{1}{k+1}\sum_{i=1}^{k+1}\binom{k+1}{i}B_{k+1-i}(n+1)^i$
1 |
|
lv. 4
求 $$\sum_{i=1}^ni^k,\quad n\leq10^{18},k\leq5\times10^4$$ ，答案对 $10^9+7$ 取模。
lv. 1 的加强版，$k$ 数据范围达到了 $5\times10^4$ ， $O(n^2)$ 的做法行不通了。
这道题其实有一个非常妙的解法，博主的思维刚开始局限在伯努利数上，没有想到。
下面先叙述最无脑的解法：
我们考虑伯努利数还有一个生成函数定义：
$$
\frac{x}{e^x-1}=\sum_{i=0}^{\infty}B_i\frac{x_i}{i!}
$$
将 $e^x$ 泰勒展开得：
$$
\frac{1}{\sum_{i=0}^x\frac{x_i}{(i+1)!}}=\sum_{i=0}^{\infty}B_i\frac{x_i}{i!}
$$
那么只需求出 $\sum_{i=0}^x\frac{x_i}{(i+1)!}$ 在 $\mod x^\text{MAXK}$ 下的逆元，再乘上 $i!$ 就可以求出 $[0,\text{MAXK}]$ 范围内的伯努利数了。
由于 $10^9+7$ 不满足 NTT 模数要求，于是可以用三模数 NTT ，找三个费马质数，使得他们的乘积超过 $nP^2$ 即可，每次乘法算出在三个费马质数意义下的答案再用 CRT 合并即可（注意万万不可求完之后再合并）。
不过这样的做法有一个很棘手的问题：三个模数都是 $10^9$ 数量级的，那么普通的 CRT 合并时就需要处理 $10^{27}$ 数量级的数字，这就需要高精了，十分麻烦，于是有一种骚操作可以解决此问题：
问题可以表示成如下形式：
$$
\left{
\begin{aligned}
x&\equiv a_0(\mod M_0)\
x&\equiv a_1(\mod M_1)\
x&\equiv a_2(\mod M_2)
\end{aligned}
\right.\
\text{求 }x\mod P
$$
先合并前两个同余方程，得到：
$$
\left{
\begin{aligned}
x&\equiv a_{01}(\mod M_{01})\
x&\equiv a_2(\mod M_2)
\end{aligned}
\right.
$$
设 $x=kM_{01}+a_{01}=\lambda m_2+a_2$解出 $k\equiv(a_2-a_{01})M_{01}^{-1}(\mod M_2)$
再将求出的 $k$ 带入原式求出 $x \mod P$ 即可
这样就可预处理出伯努利数了，然后我们用 lv. 1 的做法即可解决此问题。
1 |
|
代码实现极其繁琐，其实本题可以使用拉格朗日插值法 $O(k)$ 求解：
设答案为 $f_{n,k}$ , 根据之前的求和公式，$f_{n,k}$ 是关于 $n$ 的 $k+1$ 次多项式，那么大体思路就是处理出 $f_{1,k},f_{2,k},\dots,f_{k+1,k}$ ，然后用 $\sum_{i=0}^{k+1}\lambda_i f_{i,k}$ 表示出答案。
首先预处理：注意到 $x^k$ 是完全积性函数，我们可以老套路线性筛 $O(k)$ 预处理。
然后推公式：注意到 $n\geq k+1$ 时 $\binom{n}{i},0\leq i\leq k+1$ 是一个关于 $n$ 的 $i$ 次多项式，并且可以证明它们之间线性无关，也就是说，我们可以用 $\binom{n}{0},\binom{n,1},\dots,\binom{n}{k+1}$ 这 $k+2$ 个数表示出答案，这正符合我们的预期。
设 $$f_{n,k}=\sum_{i=0}^{k+1}\binom{n}{i}a_i$$ ，按照计划，我们需要用 $f$ 表示出 $a$ 即可，$$a_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_{i,k}$$
$$
\begin{aligned}
f_{n,k}&=\sum_{i=0}^{k+1}\binom{n}{i}\sum_{j=0}^j(-1)^{i-j}\binom{i}{j}f_{j,k}\
&=\sum_{i=0}^{k+1}f_{i,k}\sum_{j=i}^{k+1}(-1)^{j-i}\binom{n}{j}\binom{j}{i}\
&=\sum_{i=0}^{k+1}f_{i,k}\binom{n}{i}\sum_{j=i}^{k+1}(-1)^{j-i}\binom{n-i}{j-i}
\end{aligned}
$$
引理 1 :
$$
\sum_{i=0}^k(-1)^{i}\binom{n}{i}=(-1)^k\binom{n-1}{k}
$$
应用引理 1 ：
$$
\begin{aligned}
f_{n,k}&=\sum_{i=0}^{k+1}(-1)^{k-i+1}f_{i,k}\binom{n}{i}\binom{n-i-1}{k-i+1}\
&=\sum_{i=0}^{k+1}(-1)^{k-i+1}f_{i,k}\frac{\prod_{0\leq j\leq k+1,j\neq i}n-j}{i!(k-i+1)!}
\end{aligned}
$$
其实完全不必如此繁琐，此处给出了拉格朗日插值法的证明，实际上可以直接使用。
1 |
|
lv. 5
求 $$\sum_{i=1}^ni^kr_i,\quad k\leq2\times10^5$$ ，答案对 $985661441$ 取模。
在 lv. 4 的基础上进行拓展。
若 $r\equiv0$ 答案为 $0$ ;
若 $r\equiv1$ , 则原问题退化为求 $\sum_{i=1}^ni^k$ 的值，套用 lv. 4 解法二的做法。
若 $r\not\equiv 1$ , 我们套用 lv. 2 的做法，依然是错位相减，只不过中间应用二项式反演做一下变形：
$$
\begin{aligned}
(r-1)f_{n,k}&=\sum_{i=1}^ni^kr^{i+1}-\sum_{i=1}^ni^kr^i\
&=\sum_{i=1}^{n+1}(i-1)^kr^i-\sum_{i=1}^ni^kr^i\
&=n^kr^{n+1}-\sum_{i=1}^n[(i-1)^k-i^k]r^i\quad\text{（提取 }i=n+1\text{ 项）}\
&=n^kr^{n+1}-\sum_{i=1}^n\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}i^jr^i\quad\text{（应用二项式定理、二项式反演）}\
&=n^kr^{n+1}-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}f_{n,j}
\end{aligned}
$$
整理得： $$f_{n,k}=\frac{n^kr^{n+1}-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}f_{n,j}}{r-1}$$
我们现在的得到了一个与 $r\equiv1$ 的情况下形式相近的公式，但 $r\not\equiv1$ 的情况下无法快速预处理出来 $f_{1,k},\dots,f_{k-1,k}$ , 因此我们需要转化一下，大体的思想就是新设一个 $F$ ，使得其能快速求出，然后再求 $f$ 的值。
引理 2 ：
$$
\forall f_{n,i},i\in[0,k],\ \exists F_{n,i}\in Q^i[x],\text{ 使得 } f_{n,i}=r^{n+1}F_{n,i}-r{F_{0,i}}
$$
证明：
当 $i=0$ 时显然；
当 $i=k$ 时，假设结论对 $i\in [0,k-1]$ 成立：
$$
\begin{aligned}
f_{n,k}&=\frac{n^kr^{n+1}-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}f_{n,j}}{r-1}\
&=\frac{n^kr^{n+1}-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}(r^{n+1}F_{n,j}-r{F_{0,j}})}{r-1}\
&=\frac{r^{n+1}\left[n^k-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}F_{n,j}\right]+r\left[\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}F_{0,j}\right]}{r-1}
\end{aligned}
$$
那么只要 $F_{n,k}=n^k-\sum_{j=0}^{k-1}(-1)^{k-j+1}\binom{k}{j}F_{n,j}$ , 就满足题设条件，命题得证。
但是此时 $F$ 的表达式依然无法快速求出。
由引理 2得：
$$
\begin{aligned}
(n+1)^kr^{n+1}&=f_{n+1,k}-f_{n,k}\
&=r^{n+2}F_{n+1,r}-r^{n+1}F_{n,i}\
\therefore F_{n+1,k}&=\frac{(n+1)^k+F_{n,k}}{r}
\end{aligned}
$$
之后可以利用两个递推式求出 $F_{0,k},\dots,F_{k+1,k}$ ，然后用拉格朗日插值法即可求出 $F_{n,k}$ ，带入引理 2式中即可得到 $f_{n,k}$ .
1 |
|