2020-2021:teams:alchemist:hardict:powersum
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 09:46] hardict 创建 |
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 10:56] (当前版本) hardict [伯努利数以及生成函数] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ===== 积分法 ===== | + | ===== 递推 ===== |
| + | $令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)$ | ||
| ===== 拉格朗日插值法 ===== | ===== 拉格朗日插值法 ===== | ||
| 行 16: | 行 34: | ||
| ===== 伯努利数以及生成函数 ===== | ===== 伯努利数以及生成函数 ===== | ||
| + | |||
| + | $ | ||
| + | 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)!}即可得到上述公式 | ||
| + | $ | ||
2020-2021/teams/alchemist/hardict/powersum.1588988815.txt.gz · 最后更改: 2020/05/09 09:46 由 hardict
