矩阵快速幂

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define N 2//N*N的矩阵
const int MOD=1e9+7;//

struct Matrix{
    int mat[N][N];
};

Matrix mul(Matrix a,Matrix b){
    Matrix ret;
    int i,j,k;
    for(i=0;i<N;++i){
        for(j=0;j<N;++j){
            ret.mat[i][j]=0;
            for(k=0;k<N;++k){
                ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
                ret.mat[i][j]%=MOD;
            }
        }
    }
    return ret;
}

Matrix pow_matrix(Matrix a,int n){
    Matrix ret;
    memset(ret.mat,0,sizeof(ret.mat));
    int i;
    for(i=0;i<N;++i){
        ret.mat[i][i]=1;
    }
    Matrix temp=a;
    while(n){
        if(n&1){
            ret=mul(ret,temp);
        }
        temp=mul(temp,temp);
        n>>=1;
    }
    return ret;
}

int main(){
    
    Matrix a;
    a.mat[0][0]=1,a.mat[0][1]=2;
    a.mat[1][0]=3,a.mat[1][1]=4;
    
    Matrix b;
    b=pow_matrix(a,2);
    
    printf("%d %d\n",b.mat[0][0],b.mat[0][1]);
    printf("%d %d\n",b.mat[1][0],b.mat[1][1]);
    
    return 0;
}