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

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))$的时间内解决这题。

/**************************************************************
    Problem: 3157
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:1232 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
#define p 1000000007
#define N 210
ll c[N][N],n,m,i,j,x,g[50][N],tot,mn,pn[N];
ll power(ll t,ll k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
void solve(int n,int tot){
    if(n==1){
        for(int i=0;i<=m;i++)g[tot][i]=m;
    }
    else if(n&1){
        solve(n-1,tot+1);
        for(int i=0;i<=m;i++){
            g[tot][i]=1;
            for(int k=0;k<=i;k++)g[tot][i]=(g[tot][i]+c[i][k]*g[tot+1][k])%p;
            g[tot][i]=g[tot][i]*m%p;
        }
    }
    else{
        solve(n>>=1,tot+1);mn=power(m,n);
        for(int i=1;i<=m;i++)pn[i]=pn[i-1]*n%p;
        for(int i=0;i<=m;i++){
            for(int k=0;k<=i;k++)g[tot][i]=(g[tot][i]+pn[i-k]*c[i][k]%p*g[tot+1][k])%p;
            g[tot][i]=(g[tot+1][i]+mn*g[tot][i])%p;
        }n<<=1;
    }
}
int main(){
    scanf("%lld%lld",&n,&m);pn[0]=1;
    if(m==1)return printf("%lld\n",(n*(n+1)/2)%p);
    for(c[0][0]=1,i=1;i<=m+1;i++)
    for(c[i][0]=1,j=1;j<=i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1],c[i][j]>=p?c[i][j]-=p:1;
    solve(n,1);
    printf("%lld\n",g[1][m]);
}

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)$转移。

/**************************************************************
    Problem: 3516
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:160 ms
    Memory:4796 kb
****************************************************************/
 
#include<cstdio>
#define N 1010
typedef long long ll;
int n,m,c[N][N],s[N],inv,mn,k,j;ll nk;
#define p 1000000007
int power(ll t,int k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
int main(){
    scanf("%d%d",&n,&m);
    if(m==1)return printf("%lld\n",(1LL*n*(n+1)/2)%p),0;
    mn=power(m,n+1),inv=power(m-1,p-2);
    s[0]=(1LL*(mn-1)*inv-1)%p;c[0][0]=1;
    for(nk=k=1;k<=m;k++){
        for(c[k][0]=j=1;j<=k;j++)c[k][j]=(c[k-1][j]+c[k-1][j-1])%p;
        for(j=0;j<k;j++)s[k]=(s[k]+1LL*c[k][j]*((k^j)&1?-1:1)*s[j])%p;
        nk=nk*n%p;s[k]=(nk*mn+s[k])%p*inv%p;
    }
    printf("%d\n",s[m]);
}

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)$

/**************************************************************
    Problem: 4126
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4232 ms
    Memory:18388 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
#define N 500010
#define p 1000000007
int n,m,im,fac[N],i,j,inv[N],a[N],b[N],fa,fb,f0,pr[N],pt,pwm[N],vis[N],flag,tmp,ans,pre[N],suc[N];
int power(int t,int k){
    int f=1;
    for(;k;k>>=1,t=1LL*t*t%p)if(k&1)f=1LL*f*t%p;
    return f;
}
#define C(n,k) (1LL*fac[n]*inv[k]%p*inv[n-k]%p)
int main(){
    scanf("%d%d",&n,&m);n++;
    if(m==1)return printf("%lld\n",(1LL*n*(n-1)/2)%p),0;
    for(pwm[1]=inv[1]=1,i=2;i<=m+1;i++){
        if(!vis[i])pr[++pt]=i,pwm[i]=power(i,m),inv[i]=power(i,p-2);
        for(j=1;j<=pt&&1LL*i*pr[j]<=m+1;j++){
            vis[i*pr[j]]=1,
            pwm[i*pr[j]]=1LL*pwm[i]*pwm[pr[j]]%p,
            inv[i*pr[j]]=1LL*inv[i]*inv[pr[j]]%p;
            if(i%pr[j]==0)break;
        }
    }
    for(fac[0]=inv[0]=i=1;i<=m+1;i++)fac[i]=1LL*fac[i-1]*i%p,inv[i]=1LL*inv[i-1]*inv[i]%p;
    for(im=power(m,p-2),a[i=0]=1;i<=m;i++)a[i+1]=1LL*a[i]*im%p,b[i+1]=1LL*(pwm[i]+b[i])*im%p;
    for(flag=1,i=0;i<=m+1;i++,flag=-flag){
        tmp=C(m+1,i)*flag;if(tmp<0)tmp+=p;
        fa=(fa+1LL*tmp*a[i])%p,
        fb=(fb+1LL*tmp*b[i])%p;
    }
    f0=(p-1LL*fb*power(fa,p-2)%p)%p;
    if(n<=m){
        ans=(1LL*power(m,n)*(1LL*a[n]*f0%p+b[n])%p-f0+p)%p;
        printf("%d\n",ans);
    }
    else{
        pre[0]=pre[m+2]=1,suc[0]=suc[m+2]=1;
        for(i=0;i<=m;i++)pre[i+1]=1LL*pre[i]*(n-m+i)%p;
        for(i=m;i>=0;i--)suc[i+1]=1LL*suc[i+2]*(n-m+i)%p;
        for(flag=1,i=m;i>=0;i--,flag=-flag){
            tmp=(1LL*a[i]*f0+b[i])%p*inv[i]%p*inv[m-i]%p*pre[m-i]%p*suc[m-i+2]%p;
            if(flag<0)tmp=p-tmp;ans=(ans+tmp)%p;
        }
        ans=(1LL*power(m,n)*ans%p-f0+p)%p;
        printf("%d\n",ans);
    }
}