本题按时间复杂度的不同共有三种解法。

Sol-1 $O(m^2log(n))$

令 $f(n,k)=\sum_{i=1}^n i^k \cdot m^i$

\begin{eqnarray} f(n+1,k)&=&\sum_{i=1}^{n+1} i^k \cdot m^i\\ &=&m+\sum_{i=2}^{n+1} i^k\cdot m^i \\ &=&m+m\sum_{i=1}^n (i+1)^k\cdot m^i \\ &=&m+m\sum_{i=1}^n \sum_{j=0}^k C_k^j\cdot i^j\cdot m^i \\ &=&m+m\sum_{j=0}^k C_k^j\cdot\sum_{i=1}^n i^j\cdot m^i \\ &=&m+m\sum_{j=0}^k C_k^j\cdot f(n,j) \\ \end{eqnarray}

\begin{eqnarray} f(2n,k)&=&\sum_{i=1}^{2n} i^k\cdot m^i\\ &=&\sum_{i=1}^n i^k\cdot m^i +\sum_{i=n+1}^{2n} i^k\cdot m^i\\ &=&f(n,k)+\sum_{i=1}^n (i+n)^k\cdot m^{i+n}\\ &=&f(n,k)+m^n\sum_{i=1}^n m^i\cdot\sum_{j=0}^k C_k^j\cdot i^j\cdot n^{k-j} \\ &=&f(n,k)+m^n\sum_{j=0}^k C_k^j\cdot n^{k-j}\cdot\sum_{i=1}^n i^j\cdot m^i\\ &=&f(n,k)+m^n\sum_{j=0}^k C_k^j\cdot n^{k-j}\cdot f(n,j)\\ \end{eqnarray}

所以我们只要花$O(m^2)$的时间就能从$n$转移到$n+1$或者$2n$，类似快速幂的思想就能在$O(m^2log(n))$的时间内解决这题。

Sol-2 $O(m^2)$

好像网络上的题解都是这个复杂度。

令 $f(k)=\sum_{i=1}^n i^k \cdot m^i$

\begin{eqnarray} (m-1)\cdot f(k)&=&\sum_{i=1}^n i^k\cdot m^{i+1}-\sum_{i=1}^n i^k\cdot m^i \\ &=&\sum_{i=2}^{n+1} (i-1)^k\cdot m^i -\sum_{i=1}^n i^k\cdot m^i \\ &=&n^k\cdot m^{n+1}+\sum_{i=1}^n m^i\cdot[(i-1)^k-i^k]\\ &=&n^k\cdot m^{n+1}+\sum_{i=1}^n m^i\cdot\sum_{j=0}^{k-1}C_k^j\cdot i^j\cdot (-1)^{k-j}\\ &=&n^k\cdot m^{n+1}+\sum_{j=0}^{k-1} C_k^j\cdot (-1)^{k-j}\cdot\sum_{i=1}^n i^j\cdot m^i\\ &=&n^k\cdot m^{n+1}+\sum_{j=0}^{k-1} C_k^j\cdot (-1)^{k-j}\cdot f(j)\\ f(k)&=&\frac{n^k\cdot m^{n+1}+\sum_{j=0}^{k-1} C_k^j\cdot (-1)^{k-j}\cdot f(j)}{m-1}\\ \end{eqnarray} 特判$m=1$的情况，当$m\ne 1$时直接用上面的式子$O(m^2)$转移。

Sol-3 $O(m)$

Orz完杜教的ppt才懂

令$G(n)=\sum_{i=0}^{n-1} i^m\cdot m^i$，注意这里只加到$n-1$

然后把$m$很小的时候的公式找出来：

\begin{eqnarray} m=2&\ \ G(n)=&2^n\cdot (n^2-4\cdot n+6)-6\\ m=3&\ \ G(n)=&3^n\cdot (\frac{4\cdot n^3-18\cdot n^2+36\cdot n-33}{8})+\frac{33}{8}\\ m=4&\ \ G(n)=&4^n\cdot (\frac{27\cdot n^4-144\cdot n^3+360\cdot n^2-528\cdot n+380}{81})-\frac{380}{81}\\ m=5&\ \ G(n)=&5^n\cdot (\frac{128\cdot n^5-800\cdot n^4+2400\cdot n^3-4600\cdot n^2+5700\cdot n-3535}{512})+\frac{3535}{512}\\ m=6&\ \ G(n)=&6^n\cdot (\frac{3125\cdot n^6-22500\cdot n^5+78750\cdot n^4-183000\cdot n^3+305550\cdot n^2-340020\cdot n+189714}{10625})-\frac{189714}{15625}\\ \end{eqnarray}

//公式最后一项的有理数还是一个神奇的数列

根据上面这些公式，不难得出答案的式子一定是长这样的：

$$G(n)=m^n\cdot F_m(n) - F_m(0)$$

其中$F_m(n)$是一个m次多项式(代入$n$后的值)，形如$c_0\cdot n^m + c_1\cdot n^{m-1} + ... + c_{m-1}\cdot n+c_m$

归纳法证一下发现结论是对的。

所以

$$G(n+1)-G(n)=n^m\cdot m^n =m^{n+1}\cdot F_m(n+1)-m^n \cdot F_m(n)$$ $$n^m=m\cdot F_m(n+1)-F_m(n)$$ $$F_m(n+1)=\frac{n^m+F_m(n)}{m}$$

设$F_m(0)=x$，则$F_m(1)$~$F_m(m+1)$都能通过上面的递推式变成形如$Ax+B$的形式。

由于$F_m(n)$是一个次数为$m$的多项式(代入$n$后的值)，所以有下面这个式子：

$$\sum_{i=0}^{m+1} (-1)^i \cdot C_{m+1}^i F_m(i) =0$$

为什么呢？

首先，$F_m(i)$是可以线性表示成若干个组合数之和，于是我们只要证明

$$\forall k\le m, \sum_{i=0}^{m+1} (-1)^i \cdot C_{m+1}^i C_i^k =0$$

注意到$i$的范围只能是$[k,m+1]$，否则后面那坨东西直接变成0。

\begin{eqnarray} &&\sum_{i=k}^{m+1} (-1)^i \cdot C_{m+1}^i \cdot C_i^k\\ &=&\sum_{i=k}^{m+1} (-1)^i \cdot \frac{(m+1)!}{i!\cdot (m+1-i)!}\cdot\frac{i!}{k!\cdot (i-k)!}\\ &=&\frac{(m+1)!}{(m+1-k)!\cdot k!}\sum_{i=k}^{m+1} (-1)^i \cdot \frac{(m+1-k)!}{(m+1-i)!\cdot (i-k)!}\\ &=&C_{m+1}^k \sum_{i=k}^{m+1} (-1)^i \cdot C_{m+1-k}^{i-k}\\ &=&C_{m+1}^k \sum_{i=0}^{m+1-k} (-1)^{i-k}\cdot C_{m+1-k}^i\\ &=&(-1)^k\cdot C_{m+1}^k \cdot (1-1)^{m+1-k}=0\\ \end{eqnarray}

于是这个鬼畜的结论就证完啦~对任意$m$次多项式都能用~

然后就能根据这个式子列方程，就能把$F_m(0)$给解出来。

然而题目不是叫你求$F_m(0)$，而是求$m^n\cdot F_m(n)-F_m(0)$

当$n\le m$的时候，好办，把之前用到的$F_m(n)=A(n)\cdot F_m(0) + B(n)$直接算一下，然后就能得到答案了。

当$n\gt m$的时候，？

假设我们已经求出了$F_m(0),F_m(1),...,F_m(m)$

令$$F_m(n)=\sum_{k=0}^m C_n^k a_k$$

经过二项式反演可得$$a_k=\sum_{j=0}^k (-1)^{k-j}\cdot C_k^j \cdot F_m(j)$$

\begin{eqnarray} F_m(n)&=&\sum_{k=0}^m C_n^k \sum_{j=0}^k (-1)^{k-j}\cdot C_k^j \cdot F_m(j)\\ &=&\sum_{j=0}^m F_m(j)\cdot \sum_{k=j}^m (-1)^{k-j}\cdot C_n^k\cdot C_k^j\\ &=&\sum_{j=0}^m F_m(j)\cdot \sum_{k=j}^m (-1)^{k-j}\cdot \frac{n!\cdot k!}{k!\cdot (n-k)!\cdot j!\cdot (k-j)!}\\ &=&\sum_{j=0}^m F_m(j)\cdot \sum_{k=j}^m (-1)^{k-j}\cdot \frac{n!\cdot (n-j)!}{(n-k)!\cdot j!\cdot (k-j)!\cdot (n-j)!}\\ &=&\sum_{j=0}^m F_m(j)\cdot \sum_{k=j}^m (-1)^{k-j}\cdot C_n^j\cdot C_{n-j}^{k-j}\\ &=&\sum_{j=0}^m F_m(j)\cdot C_n^j \cdot \sum_{k=0}^{m-j} (-1)^k\cdot C_{n-j}^k\\ &=&\sum_{j=0}^m F_m(j)\cdot C_n^j \cdot (-1)^{m-j}\cdot C_{n-j-1}^{m-j}\\ &=&\sum_{j=0}^m F_m(j)\cdot (-1)^{m-j} \cdot \frac{n!\cdot (n-j-1)!}{j!\cdot (n-j)!\cdot (m-j)!\cdot (n-m-1)!}\\ &=&\frac{n!}{(n-m-1)!}\sum_{j=0}^m F_m(j)\cdot (-1)^{m-j}\cdot \frac{1}{j!\cdot (m-j)!\cdot (n-j)}\\ &=&\sum_{j=0}^m F_m(j)\cdot (-1)^{m-j} \cdot \frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{j!\cdot (m-j)!\cdot (n-j)}\\ \end{eqnarray}

$\frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{n-j}$可以用一个前缀乘积和一个后缀乘积优化成$O(m)$的预处理复杂度。

所以只要花$O(m)$的时间就好了。

上面有一步用到了这个式子(第六行到第七行)： \begin{eqnarray} \sum_{i=0}^k (-1)^i \cdot C_n^i &=& C_n^0-C_n^1+...\\ &=&C_{n-1}^0-C_n^1+...\\ &=&-C_{n-1}^1+C_n^2-...\\ &=&C_{n-1}^2-C_n^3+...\\ &=&(-1)^k\cdot C_{n-1}^k\\ \end{eqnarray}

复杂度分析：求$1$~$m+1$的所有阶乘、逆元、阶乘逆元以及$i^m$都能做到$O(m)$的时间复杂度。

求$\forall i \in [1,m] F_m(i)$也只要用线性复杂度。

当$n\le m$的时候，只要用$O(1)$的时间得到答案。

当$n\gt m$的时候，照着最后一个式子求。前面的乘数花$O(m)$的时间算，后面的$\frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{n-j}$,$\frac{1}{j!}$和$\frac{1}{(m-j)!}$直接$O(1)$

打了一个下午题解终于把这个坑给填了233

其实我已经在这篇blog里面贴了代码，然而只有神犇才能看得见。