【板子】矩阵快速幂

例题：https://www.luogu.org/problemnew/show/P3390
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define ll long long
 6 const int maxn = 105;
 7 const ll mod = 1e9+7;
 8 
 9 ll n,p;
10 
11 //矩阵结构体 
12 struct Matrix{
13     ll a[maxn][maxn];
14     void init(){    //初始化为单位矩阵 
15         memset(a, 0, sizeof(a));
16         for(int i = 1; i <= n;++i){
17             a[i][i] = 1;
18         }
19     }
20 };
21 
22 //矩阵乘法 
23 Matrix mul(Matrix a, Matrix b){
24     Matrix ans;
25     for(int i = 1;i <= n;++i){
26         for(int j = 1;j <= n;++j){
27             ans.a[i][j] = 0;
28             for(int k = 1;k <= n;++k){
29                 ans.a[i][j] = ans.a[i][j] % mod + a.a[i][k] * b.a[k][j] % mod;
30             }
31         }
32     } 
33     return ans;
34 }
35 
36 //矩阵快速幂 
37 Matrix qpow(Matrix a,ll b){
38     Matrix ans;
39     ans.init();
40     while(b){
41         if(b & 1)
42             ans = mul(ans,a);
43         a = mul(a,a);
44         b >>= 1;
45     }
46     return ans;
47 }
48 
49 void print(Matrix a){
50     for(int i = 1; i <= n;++i){
51         for(int j = 1;j <= n;++j){
52             cout << a.a[i][j]%mod<< " ";
53         }
54         cout << endl;
55     }
56 }
57 
58 int main(){
59     Matrix base;
60     cin>>n>>p;
61     for(int i = 1; i <= n ;i++){
62         for(int j = 1; j <= n ;j++){
63             cin>>base.a[i][j];
64         }
65     }
66     print(qpow(base,p));
67 
68     return 0;
69 }