快速幂模板（整数+矩阵）

1//整数的快速幂 m^n  % k 的快速幂：long long  quickpow(long long   m , long long   n , long long   k){    long long   ans = 1;    while(n){        if(n&1)//如果n是奇数            ans = (ans * m) % k;        n = n >> 1;//位运算“右移1类似除2”        m = (m * m) % k;    }    return ans;}2矩阵快速幂：定义一个矩阵类，例如求（A^n）%modclass Matrix {public:     long long m[MAXN][MAXN];//二维数组存放矩阵    Matrix(){}    //对数组的初始化    void init(long long  num[MAXN][MAXN]){        for(int i = 0 ; i < MAXN ; i++){            for(int j = 0 ; j < MAXN ; j++){                m[i][j] = num[i][j];           }       }    }    //重载矩阵的乘法运算    friend Matrix operator*(Matrix &m1 ,Matrix &m2) {        int i, j, k;        Matrix temp;        for (i = 0; i < MAXN; i++) {            for (j = 0; j < MAXN; j++) {                temp.m[i][j] = 0;                for(k = 0 ; k < MAXN ; k++)                   temp.m[i][j] += (m1.m[i][k] * m2.m[k][j])%mod                temp.m[i][j] %= mod;//注意每一步都进行取模           }        }        return temp;    }    //矩阵的快速幂    friend Matrix quickpow(Matrix &M , long long n){        Matrix tempans;//初始化为单位矩阵        //初始化        for(int i = 0 ; i < MAXN ; i++){            for(int j = 0 ; j < MAXN ; j++){                if(i == j)                    tempans.m[i][j] = 1;                else                    tempans.m[i][j] = 0;            }        }        //快速幂（类似整数）        while(n){            if(n & 1)                tempans = tempans * M;//已经重载了*            n = n >> 1;            M = M * M;        }       return tempans;    }};int main() {    Matrix A , ans;    long long T , n , k , sum;//数据类型为long long    long long num[MAXN][MAXN];//输入的数据存入数组    scanf("%lld" , &T);    while(T--){        scanf("%lld%lld\n", &n , &k);        memset(num , 0 , sizeof(num));        for(int i = 0 ; i < n ; i++){            for(int j = 0 ; j < n ; j++)                scanf("%lld" , &num[i][j]);        }        A.init(num);//初始化A矩阵        ans = quickpow(A , k);//求出矩阵的快速幂    }}