1 struct Matrix 2  { 3     long long mat[N][N]; 4     Matrix operator*(const Matrix m)const//定义矩阵乘法的运算符* 5     { 6         Matrix tmp; 7         for(int i = 0;i < n;i++) 8         { 9             for(int j = 0;j < n;j++)10             {11                 tmp.mat[i][j] = 0;12                 for(int k = 0;k < n;k++)13                 {14                     tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;//这里需要重点掌握15                     tmp.mat[i][j] %= MOD;16                 }17             }18         }19         return tmp;20     }21 };22 long long Pow(Matrix &m,int k)23 {24     Matrix ans;25     memset(ans.mat,0,sizeof(ans.mat));26     for(int i = 0;i < n;i++)27         ans.mat[i][i] = 1;28     while(k)29     {30         if(k&1) ans = ans*m;//这里是以二进制形式转化的，需要细细体会31         k >>= 1;32         m = m*m;33     }34     long long sum = 0;35     for(int i = 0;i < n;i++)36     {37         sum += ans.mat[i][i]%MOD;//这里需要注意，这里和先把所有数据加起来再取模是等价的。38         sum %= MOD;39     }40     return sum;41 }