学步园

       矩阵快速幂好题。题意：给一个N×K的矩阵A和K×N的矩阵B（4 <= N <= 1000，2 <= K <= 6），算出N×N的矩阵C=A×B，再算出N×N的矩阵M = C^(n×n)，最后输出矩阵M每一个元素模6的和。

       我的解题思路：矩阵C是N×N的矩阵，而N的值高达1000，因此暴力计算会超时。根据C=A×B，所以C^(n×n) = (A×B)^(n×n)。矩阵乘法满足乘法分配律，所以(A×B)^(n×n) = A×(B×A)^(n×n-1)×B，其中B×A是一个M×M的矩阵，M最多为6，这样就可以避免超时了。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <climits>
#include <algorithm>

using namespace std;

const int N = 1000;
const int M = 6;
const int MOD = 6;

struct matrix
{
    int n, m;
    int mat[M][M];
    matrix(): n(0), m(0) {}
    matrix(int nn, int mm): n(nn), m(mm) {}
    void Unit(int unit)
    {
        n = m = unit;
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j)
                mat[i][j] = i == j ? 1 : 0;
    }
};

int a[N][M], b[M][N], res[N][N];
int n, m;

void InitRead();

void DataProcess();

matrix MatrixMul(matrix a, matrix b, int mod);

matrix FastPow(matrix base, int n, int mod);

int main()
{
    while (~scanf("%d %d", &n, &m) && n && m)
    {
        InitRead();
        DataProcess();
    }
    return 0;
}

void InitRead()
{
    for (int i=0; i<n; ++i)
        for (int j=0; j<m; ++j)
            scanf("%d", &a[i][j]);
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            scanf("%d", &b[i][j]);
    return;
}

void DataProcess()
{
    matrix tmp(m, m);
    for (int i=0; i<m; ++i)     //计算B×A
    {
        for (int j=0; j<m; ++j)
        {
            tmp.mat[i][j] = 0;
            for (int k=0; k<n; ++k)
            {
                tmp.mat[i][j] += b[i][k] * a[k][j];
            }
            tmp.mat[i][j] %= MOD;
        }
    }
    tmp = FastPow(tmp, n * n - 1, MOD);     //计算(B×A)^(n×n-1)
    int temp[N][M];
    for (int i=0; i<n; ++i)         //计算A×(B×A)^(n×n-1)
    {
        for (int j=0; j<m; ++j)
        {
            temp[i][j] = 0;
            for (int k=0; k<m; ++k)
            {
                temp[i][j] += a[i][k] * tmp.mat[k][j];
            }
            temp[i][j] %= MOD;
        }
    }
    int sum = 0;
    for (int i=0; i<n; ++i)         //计算M
    {
        for (int j=0; j<n; ++j)
        {
            res[i][j] = 0;
            for (int k=0; k<m; ++k)
            {
                res[i][j] += temp[i][k] * b[k][j];
            }
            res[i][j] %= MOD;
            sum += res[i][j];
        }
    }
    printf("%d\n", sum);
    return;
}

matrix MatrixMul(matrix a, matrix b, int mod)
{
    matrix ans(a.n, b.m);
    for (int i=0; i<a.n; ++i)
    {
        for (int j=0; j<b.m; ++j)
        {
            ans.mat[i][j] = 0;
            for (int k=0; k<a.m; ++k)
            {
                ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
            ans.mat[i][j] %= mod;
        }
    }
    return ans;
}

matrix FastPow(matrix base, int n, int mod)
{
    matrix ans;
    ans.Unit(base.n);
    while (n)
    {
        if (n & 1) ans = MatrixMul(ans, base, mod);
        base = MatrixMul(base, base, mod);
        n >>= 1;
    }
    return ans;
}