今天考了机房最强妹子wyj的互测题，跪在了T2
然后uoj大佬说这是一道51nod上的题，于是我便去创建了一个账号
然后发现51nod上有5道这样的题目
于是我就立下了一个flag，然将这5道题目切掉
(flag毕竟是flag，有很大的可能性刚不动而弃疗
序列求和$level 1$
【一句话题意】
给定$n$和$k$，求$\sum_{i=1}^{n}i^k$，结果对$10^9+7$取模
【解析】
有一个叫做伯努利数的东西，它是这样定义的：$\sum_{k=0}^{n} C_{n+1}^kB_{k}=0$
通过定义我们可以得到它的递推式：$b_{n}=-\frac{1}{n+1}(C_{n+1}^0B_{0}+C_{n+1}^1B_{1}+…+C_{n+1}^{n-1} B_{n-1})$
然后给出自然数幂求和的公式(我不会证明)：$\sum_{i=1}^{n}i^k=\frac{1}{k+1}\sum_{i=1}^{k+1} C_{k+1}^i B_{k+1-i} (n+1)^i$
那么这个问题就完美的解决了，我们只需要递推出所有的伯努利数，就能求出自然数幂的和
时间复杂度：$O(n^2)$
【AC代码】(话说这东西直接在51nod上看还得花60个点头盾)
|
|
序列求和$level2$
【一句话题意】
给定$n$，$k$，$r$，求$\sum_{i=1}^{n}i^k r^i$，结果对$10^9+7$取模
【解析】
错位相减法 （似乎是高中数学知识）
设$S(n,k)=\sum_{i=1}^{n}i^k r^i$，那么有：
$S(n,k)=1^k r^1+2^k r^2+…+n^k r^n$
$rS(n,k)=1^k r^2+2^k r^3+…+n^k r^{n+1}$
$(1-r)S(n,k)=r+(2^k-1^k)r^2+(3^k-2^k)r^3+…+[(n+1)^k-n^k)]r^{n+1}-(n+1)^k r^{n+1}$
重点关注$(n+1)^k-n^k$，因为我们发现$(n+1)^k$可以使用二项式定理展开
$(n+1)^k-n^k=C_{k}^1 n^{k-1}+C_{k}^2 n^{k-2}+…+C_{k}^k n^0$
所以$S(n,k)=\sum_{i=1}^{k} \sum_{j=1}^{n}C_{k}^i j^{k-i}r^j+r-(n+1)^k r^{n+1}$
所以$S(n,k)=\sum_{i=1}^{k}C_{k}^{i} S(n,k-i)+r-(n+1)^k r^{n+1}$
这是一个递归式，当$k=0$时，$S(n,0)=\frac{r(r^n-1)}{r-1}$
所以我们使用记忆化搜索就能解决这个问题
注意当$r=1$时，分母为$0$，此时需要特判，解法和$level1$是一样的
【AC代码】
|
|
序列求和$level3$
【一句话题意】
给定$n$和$k$，求$\sum_{i=1}^{n} f[i]^k$，其中$f[i]$为斐波那契数列第$i$项，结果对$10^9+9$取模
【解析】
首先我们知道菲波那切数列的通项为$f[n]=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]$
所以$ans=\sum_{i=1}^{n}(\frac{1}{\sqrt 5})^k [(\frac{1+\sqrt 5}{2})^i-(\frac{1-\sqrt 5}{2})^i]^k$
根据二项式定理展开得到：$ans=(\frac{1}{\sqrt 5})^k \sum_{i=1}^{n} \sum_{j=0}^{k} (-1)^j C_{k}^{j} [(\frac{1+\sqrt 5}{2})^{k-j}-(\frac{1-\sqrt 5}{2})^j]^i$
变换求和号位置得到：$ans=(\frac{1}{\sqrt 5})^k \sum_{i=0}^{k} (-1)^i C_{k}^{i} \sum_{j=1}^{n} [(\frac{1+\sqrt 5}{2})^{k-i}-(\frac{1-\sqrt 5}{2})^i]^j$
然后我们发现$\sum_{j=1}^{n} [(\frac{1+\sqrt 5}{2})^{k-i}-(\frac{1-\sqrt 5}{2})^i]^j$相当于等比数列求和，直接计算就好了
时间复杂度：$O(k\log n)$
注意：求$\sqrt 5$在模意义下的值需要使用二次剩余，即计算$x^2 = 5 (mod p)$的方程的解
【AC代码】
|
|
序列求和$level4$
【一句话题意】
给定$n$和$k$，求$\sum_{i=1}^{n}i^k$，结果对$10^9+7$取模
$level4$是$level1$的加强版
【解析】
$k$的范围到了$50000$，所以我们不能用$level1$中的方法预处理伯努利数了，要想办法把$N^2$的复杂度降下来
伯努利数的生成函数是$G(x)=\sum_{i=0}^{+oo}\frac{B_i}{i!} x_i$
其中$G(x)$的计算式为$G(x)=\frac{x}{e^x-1}$
将$e^x$进行泰勒展开得到$G(x)=\frac{1}{\sum_{i=0}^{+oo} \frac{x^i}{(i+1)!}}$
所以我们只需要求多项式$\frac{1}{\sum_{i=0}^{+oo} \frac{x^i}{(i+1)!}}$的逆元就能求出$G(x)$，从而预处理出伯努利数
时间复杂度：$O(n\log n)$
注意：多项式逆元需要用到$NTT$，但是模数不符合要求，所以我们采用三模数$NTT$再用$CRT$还原系数
写起来非常糟心，博主调了整整三天才A掉，千万注意$CRT$还原系数时必须一步一步还原
具体参考代码，不明白的地方可以留言
【AC代码】
|
|