矩阵快速幂

矩阵乘法

设 C(x×z)=A(x×y)×B(y×z) ，则 Ci,j=∑yk=1Ai,k×Bk,j

代码如下：

long long c[N][N]; void times(long long a[N][N],long long b[N][N])//A*=B { fr(i,1,n) fr(j,1,n) c[i][j]=0; fr(i,1,n) fr(j,1,n) fr(k,1,n) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; fr(i,1,n) fr(j,1,n) a[i][j]=c[i][j]; }

矩阵快速幂

只有行列相等的矩阵才能快速幂。

矩阵乘法有结合律，所以可以得：

Ak={(Ak2)2(Ak−12)2)×A2|k2/|k

练手题

代码如下：

#define mod 1000000007 #define N 210 long long n,ans[N][N],g[N][N],c[N][N]; long long k; void times(long long a[N][N],long long b[N][N]) { fr(i,1,n) fr(j,1,n) c[i][j]=0; fr(i,1,n) fr(j,1,n) fr(k,1,n) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; fr(i,1,n) fr(j,1,n) a[i][j]=c[i][j]; } int main() { scanf("%lld%lld",&n,&k); k--; fr(i,1,n) fr(j,1,n) { scanf("%lld",&g[i][j]); ans[i][j]=g[i][j]; } while(k) { if(k&1ll) times(ans,g); k>>=1ll; times(g,g); } fr(i,1,n) fr(j,1,n) printf("%lld%c",ans[i][j],j==n?'\n':' '); return 0; }