•　　矩阵乘法

设A为  的矩阵，B为  的矩阵，那么称  的矩阵C为矩阵A与B的乘积，

其中矩阵C中的第  行第 列元素可以表示为：

　　

///适用于行列相通的两个矩阵#include
       
        using namespace std;const int maxn=110;int M[maxn][maxn],N[maxn][maxn],A[maxn][maxn];int main(){    int n;cin>>n;    for(int i=0;i
        
         >M[i][j];    for(int i=0;i
         
          >N[i][j];        for(int i=0;i
         
        
       

 

•　　快速幂

 

///求 n^n次方 最后一位数 #include
     
      using namespace std;int main(){    int n,ans;    while(cin>>n){        ans=1;        int x=n,base=n;        while(x){            if(x&1)                ans=ans*base%10;            base=base%10*(base%10);            x>>=1;        }        cout<
      
       <
      
     

 

•　　矩阵快速幂

#include 
     
      #include 
      
       using namespace std;const int mod = 1000000009;struct matrix {   long long a[2][2];};struct matrix mul(struct matrix a,struct matrix b) {    struct matrix ans;    memset(ans.a,0,sizeof(ans.a));    for(int i = 0; i < 2; i++) {        for(int j = 0; j < 2; j++) {            for(int k = 0; k < 2; k++) {                ans.a[i][j] = (ans.a[i][j] + ((a.a[i][k] * b.a[j][k]) % mod)) % mod;            }        }    }    return ans;}struct matrix mmul(struct matrix a,long long b){  struct matrix ans;  memset(ans.a,0,sizeof(ans.a));  ans.a[0][0] = 1;  ans.a[1][1] = 1;  while(b){    if(b & 1){       ans = mul(ans,a);    }     a = mul(a,a);     b >>= 1;  }  return ans;}int main() {        long long n;     struct matrix b,a;    b.a[0][0] = b.a[0][1] = b.a[1][0] = 1;    b.a[1][1] = 0;    memset(a.a,0,sizeof(a.a));    a.a[0][0] = 2;    a.a[0][1] = 1;    while(~scanf("%lld",&n)){            if(n == -1) break;            if(n == 0) {                printf("0\n");continue;            }      printf("%d\n",mmul(b,n - 1).a[0][0]);    }    return 0;}
      
     

 •  重载

#include 
     
      #include
      
       using namespace std;typedef long long ll;const int maxn=40;int n,k;typedef struct mtx {    ll mt[maxn][maxn];    friend mtx operator *(mtx a,mtx b) {        mtx c;        fill(c.mt[0],c.mt[0]+maxn*maxn,0);        for(int k=1; k<=n; k++) {            for(int i=1; i<=n; i++) {                for(int j=1; j<=n; j++)                    c.mt[i][j]+=a.mt[i][k]*b.mt[k][j];            }        }        return c;    }    friend mtx operator ^(mtx a,int k){        mtx p;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                p.mt[i][j]=i==j;        while(k){            if(k&1)                p=p*a;            a=a*a;            k>>=1;        }        return p;    }};int main() {    int k;    scanf("%d%d",&n,&k);    mtx x,y;    for(int i=1; i<=n; i++)        for(int j=1; j<=n; j++) {            scanf("%lld",&x.mt[i][j]);            y.mt[i][j]=x.mt[i][j];        }    mtx ans=x^k;    printf("%lld\n",ans.mt[1][n]);    return 0;}