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

[cpp] 
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类似除1” 
        m = (m * m) % k; 
    } 
    return ans; 
} 
 
 
2矩阵快速幂： 
定义一个矩阵类，例如求（A^n）%mod 
class 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)    www.2cto.com
                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);//求出矩阵的快速幂 
    } 
} 
作者：cgl1079743846