看到数据范围，显然可以 $m^3 log n$ 考虑构造矩阵
考虑 $i^m cdot m^i$ 怎么通过矩阵变成 $(i+1)^m cdot m^{i+1}$
首先后面那个 $m^i$ 变成 $m^{i+1}$ 十分显然，现在只要考虑 $i^{m}$ 变成 $(i+1)^m$
把 $(i+1)^m$ 展开，由二项式定理得到 $(i+1)^m=sum_{j=0}^{m}inom{j}{m}i^j$
那么我们首先维护一个这样的矩阵 $A$：
$egin{bmatrix}i^0 & i^1 & ... & i^m & end{bmatrix}$
然后可以构造出转移矩阵 $F$：
$egin{bmatrix}inom{0}{0} & inom{0}{1} & ... & inom{0}{m-1} & inom{0}{m}\ 0 & inom{1}{1} & ... & inom{1}{m-1} & inom{1}{m}\ 0 & 0 & ... & inom{2}{m-1} & inom{2}{m}\ ... & ... & ... & ... & ...\ 0 & 0 & ... & 0 & inom{m}{m}end{bmatrix}$
这样 $A$ 乘上 $F$ 以后就能得到 $(i+1)^m$ 了，因为之前还有个 $m^i$ 到 $m^{i+1}$，所以转移矩阵 $F$ 每一项再乘一个 $m$ 即可
因为答案要记录过程转移中的和，所以矩阵再多一个位置留给 $Ans$ 即可，最终
$A$ 为
$egin{bmatrix}i^0 cdot m^i & i^1 cdot m^i & ... & i^m cdot m^i & sum_{j=0}^{i-1}j^m cdot m^j end{bmatrix}$
$F$ 为
$egin{bmatrix}inom{0}{0}m & inom{0}{1}m & ... & inom{0}{m-1}m & inom{0}{m}m & 0\ 0 & inom{1}{1}m & ... & inom{1}{m-1}m & inom{1}{m}m & 0\ 0 & 0 & ... & inom{2}{m-1}m & inom{2}{m}m & 0\ ... & ... & ... & ... & ... & ...\ 0 & 0 & ... & inom{m-1}{m-1}m & inom{m-1}{m}m & 1\ 0 & 0 & ... & 0 & inom{m}{m}m & 1end{bmatrix}$
然后矩阵快速幂即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=207,mo=1e9+7; inline int fk(int x) { return x>=mo ? x-mo : x; } int n,m,C[N][N],T; struct Matrix { int a[N][N]; Matrix () { memset(a,0,sizeof(a)); } inline Matrix operator * (const Matrix &tmp) const { Matrix res; for(int i=0;i<=T;i++) for(int j=0;j<=T;j++) for(int k=0;k<=T;k++) if(a[i][k]&&tmp.a[k][j]) res.a[i][j]=fk(res.a[i][j]+1ll*a[i][k]*tmp.a[k][j]%mo); return res; } }Ans,F; inline Matrix ksm(Matrix x,int y) { Matrix res; for(int i=0;i<=T;i++) res.a[i][i]=1; while(y) { if(y&1) res=res*x; x=x*x; y>>=1; } return res; } int main() { n=read(),m=read(); T=m+1; for(int i=0;i<=m;i++) { C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=fk(C[i-1][j-1]+C[i-1][j]); } Ans.a[0][0]=1; for(int i=0;i<=m;i++) for(int j=0;j<=i;j++) F.a[j][i]=1ll*m*C[i][j]%mo; F.a[T-1][T]=F.a[T][T]=1; Ans=Ans*ksm(F,n); printf("%d ",fk(Ans.a[0][T]+Ans.a[0][T-1]));//注意此时最后一项还没计入a[0][T] return 0; }
啥？还有 $m^2$ 的做法？那补一个推导过程好了
设 $F_i=sum_{k=1}^{n}k^{i}m^{k}$，首先 $F_{0}$ 可以直接等比数列求和得到
然后
$mF_i=sum_{k=1}^{n}k^{i}m^{k+1}$
$(m-1)F_i=mF_i-F_i=sum_{k=1}^{n}k^{i}m^{k+1}-sum_{k=1}^{n}k^{i}m^{k}$
$=sum_{k=2}^{n+1}(k-1)^{i}m^{k}-sum_{k=1}^{n}k^{i}m^{k}$
因为前面那个式子当 $k=1$ 时没贡献，所以
$=sum_{k=1}^{n}(k-1)^{i}m^{k}+n^{i}m^{n+1}-sum_{k=1}^{n}k^{i}m^{k}$
$=n^{i}m^{n+1}+sum_{k=1}^{n}(k-1)^{i}m^{k}-sum_{k=1}^{n}k^{i}m^{k}$
$=n^{i}m^{n+1}+sum_{k=1}^{n}m^{k}((k-1)^{i}-k^i)$
直接把 $(k-1)^i$ 拆开，$(k-1)^i=sum_{j=0}^{i}(-1)^{i-j}inom{j}{i}k^j$，所以
$=n^{i}m^{n+1}+sum_{k=1}^{n}m^{k}(sum_{j=0}^{i-1}(-1)^{i-j}inom{j}{i}k^j)$
$=n^{i}m^{n+1}+sum_{j=0}^{i-1}(-1)^{i-j}inom{j}{i}sum_{k=1}^{n}m^{k}k^j$
发现后面那一团就是 $F_j$ ?
$=n^{i}m^{n+1}+sum_{j=0}^{i-1}(-1)^{i-j}inom{j}{i}F_j$
所以直接 $m^2$ 递推就完事了
啥？还有 $O(m)$ 的做法？？？？？？根本不会，溜了