2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=1e9+7; struct node { LL a[51][51]; node(){memset(a,0,sizeof a);} }; int n;LL k; node operator*(node A,node B) { node C; for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,LL b) { node C;for(int i=1;i<=n;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { cin>>n>>k; node A; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>A.a[i][j]; A=qpow(A,k); LL ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans=(ans+A.a[i][j])%P; cout<<ans<<endl; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:59:10
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=1e9+7; struct node { LL a[51][51]; node(){memset(a,0,sizeof a);} }; int n;LL k; node operator*(node A,node B) { node C; for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,LL b) { node C;for(int i=1;i<=n;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { cin>>n>>k; node A; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>A.a[i][j]; A=qpow(A,k); LL ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans=(ans+A.a[i][j])%P; cout<<ans<<endl; return 0; }
- 1
