快速幂

（x*y）mod c=（（x mod c）*（y mod c））mod c
证明：
令x=a*c+k1
  y=b*c+k2
则(x*y)%c=((a*c+k1)*(b*c+k2))%c
               =(a*c*b*c+k2*a*c+k1*b*c+k1*k2)%c
              =(k1*k2)%c
              =((x%c)*(y%c))%c

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)
                    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);//求出矩阵的快速幂 
        } 
    }