洛谷P3390 【模板】矩阵快速幂

注意点：1.矩阵运算规则：题解里讲的很详细。

2.这个题只能用while型的快速幂，不能用递归型的，会TLE。

3.极其坑爹的一点：常量定义居然不能用define，只能用const？？判定非常迷，卡了我3个小时！

上AC代码

 1 #include<bits/stdc++.h>
 2 //#define mod 100000007     //这个不行，会MLE！！用下面的常量定义 
 3 using namespace std;
 4 const int mod=1000000007;
 5 
 6 struct matrix{
 7     long long m[105][105];
 8 }A;
 9 
10 long long n,k;
11 
12 matrix operator *(const matrix &a,const matrix &b){
13     matrix z;
14     for(int i=1;i<=n;i++)     
15         for(int j=1;j<=n;j++)
16           z.m[i][j]=0;
17     for(int i=1;i<=n;i++){
18         for(int j=1;j<=n;j++){
19             for(int k=1;k<=n;k++){
20                 z.m[i][j]+=(a.m[i][k]*b.m[k][j]%mod);
21                 z.m[i][j]%=mod;
22             }
23         }
24     }
25     return z;
26 }
27 
28 int main(){
29     cin>>n>>k;
30     for(int i=1;i<=n;i++){
31         for(int j=1;j<=n;j++){
32             cin>>A.m[i][j];
33         }
34     }
35     matrix ans;
36     for(int i=1;i<=n;i++) ans.m[i][i]=1;
37     while(k>0){
38         if(k%2==1) ans=ans*A;
39         A=A*A;
40         k/=2;
41     }
42     for(int i=1;i<=n;i++){
43         for(int j=1;j<=n;j++) cout<<ans.m[i][j]<<' ';
44         cout<<endl;
45     }
46     return 0;
47 }