2020-2021:teams:alchemist:hardict:powersum
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 10:35] hardict [伯努利数以及生成函数] |
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 10:56] (当前版本) hardict [伯努利数以及生成函数] |
||
|---|---|---|---|
| 行 36: | 行 36: | ||
| $ | $ | ||
| - | B_{0}=1,B_{1}=-\frac{1}{2},B_{2}=\frac{1}{6}\\ | + | 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_{3}=0,B_{4}=-\frac{1}{30},B_{5}=0\\\\ |
| B_{6}=\frac{1}{42},B_{7}=0,B_{8}=-\frac{1}{30} | B_{6}=\frac{1}{42},B_{7}=0,B_{8}=-\frac{1}{30} | ||
| $ | $ | ||
| 行 54: | 行 54: | ||
| $$ | $$ | ||
| - | $考虑C(x)=\sum_{i=0}^{\infty}\frac{B_{i}}{i!}x^{i}$ | + | $ |
| + | 考虑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} | ||
| + | $ | ||
| - | $有e^{x}C(x)=C(x)+x \quad (加x是因为n>1导致第一项缺失,而n=0时上述等式也是成立的)$ | + | 故可以利用递推$O(n^{2})$或利用NTT$O(nlogn)$预处理 |
| - | $得到关于\frac{B_{n}}{n!}的生成函数\frac{x}{e^{x}-1}$ | ||
| + | 伯努利数与自然数幂和关系为 | ||
| + | |||
| + | $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.1588991754.txt.gz · 最后更改: 2020/05/09 10:35 由 hardict
