题意：求 \(\sum_{i=1}^n i^k\)
Part 1
通过伯努利数可以证明答案是一个 \(k+1\) 项的多项式。
然后就可以用拉格朗日插值来做，具体套模板，不多谈
Part 2
发现这个东西好像可以斯特林数搞一搞的样子。先推一波式子
\[\sum_{i=0}^ni^k\\sum_{i=1}^n\sum_{j=0}^kj! \left\{ \begin{matrix} k \\ j \end{matrix} \right\} \binom i j\\sum_{j=0}^kj! \left\{ \begin{matrix} k \\ j \end{matrix} \right\} \sum_{i=1}^n\binom i j\\
\sum_{j=0}^kj! \left\{ \begin{matrix} k \\ j \end{matrix} \right\} \binom{n+1}{j+1}
\]
其中
\[\left\{ \begin{matrix} k \\ j \end{matrix} \right\}\\
\]
可以用 \(\operatorname{NTT}\) 去做。
发现模数是 \(10^9+7\) ，相当僵硬，直接用任意模数 \(\operatorname{NTT}\) 搞一波就行了
以上内容纯属口胡，没有打过代码，只是看网上没有第二类斯特林数做法就来补充一下（
CF622F The Sum of the k-th Powers 题解（拉格朗日插值 or 斯特林数）
原文：https://www.cnblogs.com/limit-ak-ioi/p/13209951.html
