【矩阵乘法+快速取幂模】HDU 1575 Tr A
http://acm.hdu.edu.cn/showproblem.php?pid=1575
Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
Input
数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。
Output
对应每组数据，输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define L long long#define inf 0x3fffffff#define FF(i, n) for (i = 0; i < n; i++)#define M 11//阶数int ret[M][M];//结果矩阵int init[M][M];//初始矩阵int tp[M][M];//中间变量矩阵void matmul (int a[][M], int b[][M], int n, int mod){ int i, j, k; FF(i, n) FF(j, n) tp[i][j] = 0; FF(i, n) FF(k, n) if (a[i][k]) FF(j, n) if (b[k][j]) tp[i][j] = (tp[i][j] + a[i][k] * b[k][j]) % mod; memcpy (a, tp, sizeof(tp));}void qmod (int n, int b, int mod){ int i, j; FF(i, n) FF(j, n) ret[i][j] = (i==j); for ( ; b; b >>= 1) { if (b & 1) matmul (ret, init, n, mod); matmul (init, init, n, mod); }}int main(){ int t, n, k, i, j, sum; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &k); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf ("%d", init[i]+j); qmod (n, k, 9973); sum = 0; for (i = 0; i < n; i++) sum = (sum + ret[i][i]) % 9973; printf ("%d\n", sum); } return 0;}