【矩阵乘法+快速取幂模】HDU 1575 Tr A

基德KID.1412

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 __int64#define inf 0x3fffffffint res[15][15], n;void mul (int a[][15], int b[][15], int c, int res[][15])    //矩阵乘法{    int s[15][15] = {0}, y, i, j;    for (i = 0; i < n; i++)        for (j = 0; j < n; j++)            for (y = 0; y < n; y++)                s[j] = (s[j] + a[y] * b[y][j]) % c;    //乘的同时模    memcpy (res, s, sizeof(s));}void qpow (int a[][15], 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[15][15], ans;    scanf ("%d", &t);    while (t--)    {        scanf ("%d%d", &n, &k);        for (i = 0; i < n; i++)            for (j = 0; j < n; j++)                res[j] = (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[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[j] = 0;    FF(i, n) FF(k, n) if (a[k]) FF(j, n) if (b[k][j])        tp[j] = (tp[j] + a[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[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+j);        qmod (n, k, 9973);        sum = 0;        for (i = 0; i < n; i++)            sum = (sum + ret) % 9973;        printf ("%d\n", sum);    }    return 0;}