一个常见式子较劣的一些解法

题意

求(sumlimits_{i=1}^n i^m m^i)

做法一

保留(m)，将(n=4)带入：(1^mm+2^mm^2+3^mm^3+4^mm^4)
用秦九韶算法整理：(m(1^m+m(2^m+m(3^m+4^mm))))
从括号里面向外算，(n^r)可以利用(n^k(kin[0,r]))的系数转移到((n-1)^r)，所以仅需要存(n^r(rin [0,m]))即可(O(m^2))的维护(i^m)
将其写成矩阵形式然后快速幂，(O(m^3logn))

做法二

令(f(n,r)=sumlimits_{i=1}^n i^r m^i)
然后利用二项式定理很容易得到

[f(2n,r)=f(n,r)+m^n sumlimits_{j=0}^r {rchoose j}n^{r-j}f(n,j) ]

直接用列向量快速幂，(O(m^2logn))