1.一部分需要求类似于\(\sum ans(x)^k\)，k不大，\(ans(x)\)贡献每次多\(1\)。
解：这种题感觉突然很常见还比较套路，在联赛出现也不是不可能/kk
直接二项式定理可以做到\(O(k^2)\)更新贡献，但是并不优秀。
考虑斯特林数展开，\(x^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\begin{pmatrix}x\\i\end{pmatrix}\)。
如何理解？考虑组合意义，\(x^k\)为\(x\)个集合放\(k\)个数的方案数（集合可以为空），那么可以枚举非空集，\(\begin{Bmatrix}k\\i\end{Bmatrix}\)是\(i\)个集合放\(k\)个数（集合不可以为空），盒子不一样所以乘\(i!\)，\(\begin{pmatrix}x\\i\end{pmatrix}\)是从\(x\)个集合选\(i\)个非空集。
于是这个式子变为\(\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\sum\begin{pmatrix}ans(x)\\i\end{pmatrix}\)。
发现每次贡献更新只会跟\(\begin{pmatrix}ans(x)\\i\end{pmatrix}\)有关，而贡献多\(1\)后，\(\begin{pmatrix}ans(x)+1\\i\end{pmatrix}=\begin{pmatrix}ans(x)\\i\end{pmatrix} + \begin{pmatrix}ans(x)\\i-1\end{pmatrix}\)，于是我们维护\(\begin{pmatrix}ans(x)\\i\end{pmatrix},0\le i\le k\)，每次更新贡献可以\(O(k)\)完成。
原文：https://www.cnblogs.com/sdlang/p/13810676.html