幂前缀和的生成函数
问题描述：
对于给定的大数(m)，求(displaystyle kin[1,n],F_k=sum _{i=1}^m i^k)
(F_k=sum _{i=1}^m i^k)，每一项的组合意义即：为(k)个元素每个染上(i)种颜色中的一个
下面是用斯特林数的推导
带入第二类斯特林数的组合意义，得到
(displaystyle F_k=sum_{i=1}^m sum_{j=0}^{infty} inom{i}{j}egin{Bmatrix}k\ jend{Bmatrix}j!)
合并外层循环的组合数前缀和
(displaystyle F_k=sum_{i=0}^{infty} inom{m+1}{i+1}egin{Bmatrix}k\ iend{Bmatrix}i!)
我们知道第二类斯特林数的( ext{EGF})
(displaystyle S(x)=sum egin{Bmatrix}i\m end{Bmatrix}frac{x^i}{i!}=frac{1}{m!}(e^x-1)^m)
其意义是合并每一种颜色的元素的( ext{EGF})，要求每种颜色个数(ge 1)，同时颜色之间无序，最后除掉
带入(F_k)的式子，得到(F_k)的( ext{EGF})
(displaystyle F(x)=sum inom{m+1}{i+1}(e^x-1)^i)
带入二项展开
(displaystyle F(x)=frac{e^{(m+1)x}-1}{e^x-1})
停停停
这个东西不是直接根据([x^n]e^{ax}=cfrac{a^n}{n!})
就会发现是(displaystyle sum_{i=0}^m e^{ix}=frac{e^{(m+1)x}-1}{e^x-1})吗
线性解法
待补。。。