@参考资料@
@0 - 问题描述@
我们希望找到一个算法求出下面式子的值。
一般来说要求时间复杂度不能与 n 有关。
一个有用的结论 ：(S_{n, k}) 是一个关于 n 的 k + 1 次多项式。
@1 - 递推@
这是一个中学老师（大概）要讲的做法。
推导可以用扰动法，也可以用裂项相消法。
扰动法：记 (S(n)=sum_{k=0}^{n}a_k)，列等式 (S(n)+a_{n+1}=a_0+sum_{k=1}^{n+1}a_k)。此方法可解决等比数列求和等。
我们采用裂项相消法。注意到 ((n+1)^{k+1} = sum_{i=0}^{k+1}{k+1 choose i}n^i = n^{k+1} + sum_{i=0}^{k}{k+1 choose i}n^i)。
即 ((n + 1)^{k+1} - n^{k+1} = sum_{i=0}^{k}{k+1 choose i}n^i)。求和可得：
于是可以得到递推式 (S_{n, k} = frac{(n + 1)^{k+1} - sum_{j=0}^{k-1}{k+1 choose j}S_{n, j}}{k + 1})。
该递推式可以在给出 n 的情况下 (O(k^2)) 求出前 k 项，或者 (O(k^3)) 求出关于 n 的 k + 1 次多项式。
@2 - 伯努利数（生成函数）@
我们设指数型生成函数 (F_n(x) = sum_{i=0}frac{S_{n, i}x^i}{i!})。
作为一名熟练的 OI 选手，你可以将上面的递推式看成生成函数卷积式，快速算出 (F_n(x)) 的表达式。
不过这里直接根据定义推：
注意 (e^x - 1) 没有逆元，不过 (frac{e^x - 1}{x}) 有。所以可以预处理出 (B(x) = frac{x}{e^x - 1})（伯努利数的生成函数）。
所以 (F_n(x) = frac{e^{(n+1)x} - x}{x}B(x))，直接卷积。注意是指数型生成函数所以还原时要乘阶乘。
该方法可以在给出 n 的情况下 (O(klog k)) 求出前 k 项，是求解自然数幂和的主要方法之一。
@3 - 拉格朗日插值法@
前面 (S_{n, k}) 是一个关于 n 的 k + 1 次多项式，因此可以插 k + 2 个点值求 (S_{n, k})。
先列出拉格朗日插值式：
分子可以预处理 ((x - j)) 的前缀积与后缀积实现 (O(k))。
分母是两个阶乘之积 + 可能存在的 (-1)，预处理阶乘的倒数实现 (O(k))。
至于 (S_{i, k})，考虑线性筛，只在素数处用 (O(klog k)) 的快速幂，由素数的分布为 (O(frac{k}{ln k})) 得该算法复杂度依然为 (O(k))。
综上，该方法可以在 (O(k)) 求出某一项 (S_{n, k})，是求解自然数幂和的另一主要方法。
模板题：codeforces - 622F。
@4 - 其他方法@
这些方法并不如上面两种主流方法常用，但是具有一定启发意义。
@4.0 - 引入@
离散的数列求和 对应着 连续的函数积分。
连续的函数微分 对应回来，我们可以定义出 数列的差分运算：(Delta f(x) = f(x + 1) - f(x))。
我们可以对数列进行多次差分，结果可以记作 (Delta^k f(x) = Delta^{k-1}f(x + 1) - Delta^{k-1}f(x))
幂函数 (f(x) = x^m) 求导得 (f'(x) = mx^{m-1})；而下降幂 (f(x) = x^{underline{m}}) 差分得 (Delta f(x) = mx^{underline{m-1}})。
所以我们一般认为，连续的幂函数 (x^m) 对应为 离散的下降幂 (x^{underline{m}})。
以上这些离散微积分的概念，虽然可以被其他概念取代，但可以让你更了解数学之间的关联性。
@4.1 - 斯特林数@
众所周知可以通过斯特林数实现 幂 与 下降幂 之间的转化：
而 离散的下降幂求和 与 连续的幂积分 公式一样，非常好算。
因此，我们借助斯特林数进行计算：
只要预处理出斯特林数就可以 (O(k)) 算。
顺便一提，用第一类斯特林数再把 ((n + 1)^{underline{j + 1}}) 展开，还可以得到 (S_{n, k}) 关于 n + 1 的多项式。
@4.2 - 高阶差分@
一篇关于该方法的介绍：miskcoo。
类比 连续函数的泰勒展开，离散数列也有个牛顿级数：
如果 f(x) 是一个次数为 k 的多项式，经过 k + 1 次差分过后就会变为全 0 的数列了。因此多项式牛顿级数是 (O(k)) 项的。
可以用归纳法证明高维差分 (Delta^n f(x) = sum_{i=0}^{n}(-1)^{n-i}{nchoose i}f(x + i))，这样就与上面的博客中所提到的结果是一致的。
如果把 (S_{n, k} = sum_{i=0}^{n}i^k) 当成关于 n 的多项式，就可以用上面那篇博客提到的方法 (O(k)) 做，不过和拉格朗日插值实在太像了。。。
关于这个方法有一道题（不是自然数幂和）：bzoj - 4126。