【矩阵乘法+快速取幂模】HDU 1575 Tr A
http://acm.hdu.edu.cn/showproblem.php?pid=1575Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
Input
数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是，表示方阵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 __int64#define inf 0x3fffffffint res, n;void mul (int a[], int b[], int c, int res[]) //矩阵乘法{ int s = {0}, y, i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) for (y = 0; y < n; y++) s = (s + a * b) % c; //乘的同时模 memcpy (res, s, sizeof(s));}void qpow (int a[], int b, int c) //快速取幂模{ while (b) {if (b & 1)mul (res, a, c, res); mul (a, a, c, a);b >>= 1; }}int main(){ int t, k, i, j, a, ans; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &k); for (i = 0; i < n; i++) for (j = 0; j < n; j++) res = (i==j); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf ("%d", a+j); qpow (a, k, 9973); ans = 0; for (i = 0; i < n; i++) ans += res; //主对角线上元素之和 printf ("%d\n", ans%9973); } return 0;}
简化&小技巧 模板：
#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;//结果矩阵int init;//初始矩阵int tp;//中间变量矩阵void matmul (int a[], int b[], int n, int mod){ int i, j, k; FF(i, n) FF(j, n) tp = 0; FF(i, n) FF(k, n) if (a) FF(j, n) if (b) tp = (tp + a * b) % 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); 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+j); qmod (n, k, 9973); sum = 0; for (i = 0; i < n; i++) sum = (sum + ret) % 9973; printf ("%d\n", sum); } return 0;}
页:
[1]