基础矩阵乘法……
|
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 |
#include <cstdio>#include <iostream>#define rep(i,n) for(int i=0;i<n;i++)using
namespace std;const
int maxn=10;const
int MOD=9973;struct
matrix{ int
v[maxn][maxn]; void
init(){memset(v,0,sizeof
v);}}a;matrix mul(matrix a,matrix b,int
l,int m,int n,int mod){ matrix c; c.init(); rep(i,l)rep(j,m)rep(k,n)c.v[i][j]=(c.v[i][j]+(a.v[i][k]*b.v[k][j])%mod)%mod; return
c;}matrix power(matrix a,int
l,int m,int n,int x,int mod){ if(x==1)return
a; matrix tmp=power(a,l,m,n,x>>1,mod); tmp=mul(tmp,tmp,l,m,n,mod); if(x&1)tmp=mul(tmp,a,l,m,n,mod); return
tmp;}int
main(){ int
T,n,m; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); rep(i,n)rep(j,n)scanf("%d",&a.v[i][j]); a=power(a,n,n,n,m,MOD); int
ans=0; rep(i,n)ans=(ans+a.v[i][i])%MOD; printf("%d\n",ans); } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3676556.html