Featured image of post 矩阵快速幂(模板)

矩阵快速幂(模板)

封面来源

Pixiv frontierC-76377786

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
// const int Mod = 1e9+7;
int n,m;
inline int read(){
register int f=1,k=0;
register char c=getchar();
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
if(c=='-') f=-1,c=getchar();
while(c>='0'&&c<='9') k=(k<<3)+(k<<1)+(c^48),c=getchar();
return f*k;
}
struct matrix{
    int m[31][31];
    matrix operator * (const matrix & b){
        matrix res;
        memset(res.m,0,sizeof(res.m));
        for(register int i=1;i<=n;i++){
            for(register int j=1;j<=n;j++){
                for(register int k=1;k<=n;k++){
                    res.m[i][j]+=(m[i][k])*(b.m[k][j]);
                    // res.m[i][j]%=Mod;
                }
            }
        }
        return res;
    }
    matrix(){memset(m,0,sizeof(m));}
matrix operator ^ (int p){
matrix ans;
for(int i=1;i<=n;i++){
ans.m[i][i]=1;
}
while(p){
if(p&1){
ans=ans*(*this);
}
(*this)=(*this)*(*this);
p>>=1;
}
return ans;
}
}Ans,base;
int main(){
n=read();
m=read();
// init();
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
Ans.m[i][j]=base.m[i][j]=read();
}
}
Ans = base^(m);
for(register int i=1;i<=n;i++){
for(register int j=1;j<=n;j++){
printf("%d ",Ans.m[i][j]);
}
puts("");
}
    return 0;
}
所念皆星河
Built with Hugo
主题 StackJimmy 设计