Warning: session_start(): open(/tmp/sess_a76190b035d11b419d73abd233ca881e, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 递推 ===== $令f_{k}(n)=\sum_{i=1}^{n}i^{k}$ $$ \begin{align} f_{k+1}(n+1) & =f_{k+1}(n)+(n+1)^{k+1} &\\ & =1+\sum_{i=1}^{n}(i+1)^{k+1} &\\ & =1+\sum_{i=1}^{n}\sum_{j=0}^{k+1} \binom{k+1}{j} i^{j} &\\ & =1+\sum_{j=0}^{k+1}\binom{k+1}{j} \sum_{i=1}^{n} &\\ & =1+\sum_{i=0}^{k+1}\binom{k+1}{i} f_{i}(n) &\\ & =1+f_{k+1}(n)+(k+1)f_{k}(n)+\sum_{i=0}^{k-1}\binom{k+1}{i} f_{i}(n) &\\ \end{align} $$ $得到了:(k+1)f_{k}(n)=(n+1)^{k+1}-1 - \sum_{i=0}^{k-1}\binom{k+1}{i} f_{i}(n)$ $可以写成: f_{k-1}(n)=\frac{(n+1)^{k}-1}{k} - \frac{1}{k}\sum_{i=0}^{k-2}\binom{k}{i} f_{i}(n)$ ===== 拉格朗日插值法 ===== 对于$\sum_{i=1}^n i^k=f[n][k]$，$f[][k]$具体表达是一个$k+1$次多项式，我们求解$f[0\sim k+1][k]$，然后进行插值即可 对于具体计算$f[n]=\sum_{i=0}^{k+1} f[i]\frac{\prod_{j=0,j\neq i}^{k+1}(n-j)}{\prod_{j=0,j\neq i}^{k+1}(i-j)}$ $\prod_{j=1,j\neq i}^{k+1}(n-j)=\prod_{j=1}^{i-1}(n-j)\prod_{j=i+1}^{k+1}(n-j)$是前缀积$\times$后缀积 $\prod_{j=0,j\neq i}^{k+1}(i-j)=i!(k+1-i)!(-1)^{k+1-i}$ 于是，可以$O(k)$预处理$f[]$以及阶乘，前后缀然后$O(k)$计算 这种方法对不同$f[n]$计算速度一样，而针对多次询问则需要利用生成函数计算伯努利数 ===== 伯努利数以及生成函数 ===== $ B_{0}=1,B_{1}=-\frac{1}{2},B_{2}=\frac{1}{6}\\\\ B_{3}=0,B_{4}=-\frac{1}{30},B_{5}=0\\\\ B_{6}=\frac{1}{42},B_{7}=0,B_{8}=-\frac{1}{30} $ $可以利用:B_{0}=1, \sum_{i=0}^{n}B_{i}\binom{n+1}{i}=0 \Rightarrow B_{n}=-\frac{1}{n+1}\sum_{i=0}^{n-1}B_{i}\binom{n+1}{i} 计算$ $$ \begin{align} & \sum_{i=0}^{n-1}B_{i}\binom{n}{i}=0 &\\ & \sum_{i=0}^{n}B_{i}\binom{n}{i}=B_{n} (n > 1)&\\ & \sum_{i=0}^{n}\frac{1}{i!(n-i)!}B_{i} = \frac{B_{n}}{n!} (n > 1)& \end{align} $$ $ 考虑C(x)=\sum_{i=0}^{\infty}\frac{B_{i}}{i!}x^{i}\\\\ 有e^{x}C(x)=C(x)+x \quad (加x是因为n>1导致第一项缺失,而n=0时上述等式也是成立的)\\\\ 得到关于\frac{B_{n}}{n!}的生成函数\frac{x}{e^{x}-1} $ 故可以利用递推$O(n^{2})$或利用NTT$O(nlogn)$预处理 伯努利数与自然数幂和关系为 $f_{k}(n-1) =\sum_{i=0}^{n-1}i^{k} =\frac{1}{k+1}\sum_{i=0}^{k}\binom{k+1}{i}B_{i}n^{k+1-i}$ $ 考虑F(x)=\sum_{k=0}^{\infty}(\sum_{i=0}^{n-1}i^{k})\frac{x^{k}}{k!}\\\\ F(x)=\sum_{i=0}^{n-1}\sum_{k=0}^{\infty}i^{k}\frac{x^{k}}{k!}=\sum_{i=0}^{n-1}e^{ix}=\frac{e^{nx}-1}{e^{x}-1}\\\\ 注意到C(x)=\frac{x}{e^{x}-1},F(x)=C(x)\frac{e^{nx}-1}{x}, \frac{e^{nx}-1}{x}=\sum_{i=0}^{\infty}\frac{n^{i+1}x^{i}}{(i+1)!}\\\\ F(x)中x^{k}系数\frac{f_{k}(n-1)}{k!}=\sum_{i+j=k}\frac{B_{i}}{i!}\frac{n^{j+1}}{(j+1)!}即可得到上述公式 $