题目链接。hdu 4965 Fast Matrix Calculation

题目大意：给定两个矩阵A，B，分别为N*K和K*N。

1. 矩阵C = A*B
2. 矩阵M=CN∗N
3. 将矩阵M中的全部元素取模6，得到新矩阵M‘
4. 计算矩阵M’中全部元素的和

解题思路：由于矩阵C为N*N的矩阵，N最大为1000。就算用高速幂也超时，可是由于C = A*B, 所以CN∗N=ABAB…AB=AC′N∗N−1B，C‘
= B*A, 为K*K的矩阵，K最大为6。全然能够接受。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1005;

const int MOD = 6;

typedef int Mat[maxn][maxn];

int N, K;

Mat A, B, X, Y, tmp;

void put (Mat x, int r, int c) {

    for (int i = 0; i < K; i++) {

        for (int j = 0;  j < K; j++)

            printf("%d ", x[i][j]);

        printf("\n");

    }

}

void mul_mat (Mat ret, Mat a, Mat b, int r, int t, int c) {

    memset(tmp, 0, sizeof(tmp));

    for (int k = 0; k < t; k++) {

        for (int i = 0; i < r; i++)

            for (int j = 0; j < c; j++)

                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;

    }

    memcpy(ret, tmp, sizeof(tmp));

}

void pow_mat (Mat ret, Mat x, int n) {

    memset(Y, 0, sizeof(Y));

    for (int i = 0; i < K; i++)

        Y[i][i] = 1;

    while (n) {

        if (n&1)

            mul_mat(Y, Y, x, K, K, K);

        mul_mat(x, x, x, K, K, K);

        n >>= 1;

    }

    memcpy(ret, Y, sizeof(Y));

}

void init () {

    for (int i = 0; i < N; i++)

        for (int j = 0; j < K; j++)

            scanf("%d", &A[i][j]);

    for (int i = 0; i < K; i++)

        for (int j = 0; j < N; j++)

            scanf("%d", &B[i][j]);

}

int main () {

    while (scanf("%d%d", &N, &K) == 2 && N + K) {

        init();

        mul_mat(X, B, A, K, N, K);

        pow_mat(X, X, N*N-1);

        mul_mat(X, A, X, N, K, K);

        mul_mat(X, X, B, N, K, N);

        int ans = 0;

        for (int i = 0; i < N; i++)

            for (int j = 0; j < N; j++)

                ans += X[i][j];

        printf("%d\n", ans);

    }

    return 0;

}