快速冪模板（整數+矩陣）

[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