2020-2021:teams:alchemist:hardict:powersum
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 10:16] hardict [递推] |
2020-2021:teams:alchemist:hardict:powersum [2020/05/09 10:56] (当前版本) hardict [伯努利数以及生成函数] |
||
|---|---|---|---|
| 行 34: | 行 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.1588990598.txt.gz · 最后更改: 2020/05/09 10:16 由 hardict
