先膜一发Miskcoo，大佬的博客上多项式相关的非常全
原题戳我
题目大意
\[\sum\limits_{i=1}^{n}i^mm^i
\]
题解
设一个函数\(f(i)=\sum\limits_{j=1}^{n}j^im^j\)
然后貌似用一个叫扰动法（感觉就是错位相消法）的东西，算一下
\[(m-1)f(i)=\sum\limits_{j=1}^{n+1}(j-1)^im^j-\sum\limits_{i=1}^{n}j^im^j=n^im^{n+1}-\sum\limits_{j=1}^{n}m^j[(j-1)^i-j^i]
\]
其中，\((j-1)^i-j^i\)可以用一波二项式展开化为\(\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}j^k\)，回带可得
\[(m-1)f(i)=n^im^{n+1}-\sum\limits_{j=1}^{n}m^j\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}j^k$$$$=n^im^{n+1}-\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}\sum\limits_{j=1}^{n}j^km^j$$$$=n^im^{n+1}-\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}f(k)
\]
然后就有了一个\(O(m^2)\)的递推做法，还有一个\(O(m)\)的，但看起来挺麻烦的，咕了
以下是代码，注意初值\(f(0)\)的设置还有\(m=1\)时的特判
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include