NUIST-oj/p1156.cpp at master · EvenTiming/NUIST-oj · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>


using namespace std;

const int N = 11;

int n;

struct Mat {
   int  mat[N][N];
};


Mat operator * (Mat a, Mat b) {
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(i = 0; i < n; ++i) {
        for(j = 0; j < n; ++j) {
            for(k = 0; k < n; ++k) {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }

            c.mat[i][j] %= 9973;
        }
    }
    return c;
}


Mat operator ^ (Mat a, int k) {
    Mat c;
    int i, j;
    for(i = 0; i < n; ++i){
        for(j = 0; j < n; ++j){
            c.mat[i][j] = (i == j);
        }
    }


    for(; k; k >>= 1) {
        if(k&1){
        	c = c*a;
        }
        a = a*a;
    }
    return c;
}


int getTr(Mat a,int n){
	int i;
	int sum = 0;
	for(i = 0 ; i < n ; ++i){
		sum += a.mat[i][i];
		sum %= 9973;
	}

	return sum;
}


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int k;
		scanf("%d%d",&n,&k);

		Mat m;

		int i;
		int j;
		for(i = 0 ; i < n ; ++i){
			for(j = 0 ; j  < n ; ++j){
				scanf("%d",&m.mat[i][j]);
			}
		}

		m = m^k;
		printf("%d\n",getTr(m,n));
	}

	return 0;
}