hdoj 4965 Fast Matrix Calculation

题解

---

题面

给定矩阵 $A_{n, k}, B_{k, n}$
定义矩阵 $C = A * B， M = C^{n * n}$
计算 $M$ 的每个元素 %6 以后的和

解

$$M = \underbrace{A_{n, k} * B_{k, n} * A_{n, k} * B_{k, n} * \cdots * A_{n, k} * B_{k, n}}_{n * n 个 A * B}$$

考虑矩阵快速幂
令 $M' = A_{n, k} * B_{k, n}$
那么矩阵 $M'$ 是 $n * n$ 的
每次乘法的时间复杂度为 $O(n ^ 3)$
整个算法的时间复杂度为 $O(log_{n ^ 2} * n ^ 3)$
显然无法接受

继续考虑优化算法
由于满足结合律
令 $M' = B_{k, n} * A_{n, k}$
那么矩阵 $M'$ 是 $k, k$ 的

$$M = A_{n, k} * M'_{k, k} * B_{k, n}$$
在计算 $M'$ 时间复杂度为 $O(log_{n ^ 2} * k ^ 3)$
然后计算 $A * M'$ 时间复杂度为 $O(n * k ^ 2)$
然后计算 $A * M' * B$ 时间复杂度为 $O(n ^ 2 * k)$
整个算法的时间复杂度为 $O(可过)$

Code

写的有点啰嗦

#include <bits/stdc++.h>
const int N = 1e3 + 10;
const int K = 10, Mod = 6;
#define LL long long
LL A[N][K], B[K][N], E[K][K], G[N][K], Answer[N][N], n, k, Pow;
struct Node {
    LL m[10][10];
    Node() {memset(m, 0, sizeof m);}
    void Clear() {for(int i = 1; i <= 7; i ++) m[i][i] = 1;} 
};
Node Use;
void Get_k_k() {
    for(int i = 1; i <= k; i ++)
        for(int j = 1; j <= k; j ++)
            for(int r = 1; r <= n; r ++)
                Use.m[i][j] += B[i][r] * A[r][j];
}
Node operator * (const Node &a, const Node &b) {
    Node ret;
    for(int i = 1; i <= k; i ++)
        for(int j = 1; j <= k; j ++)
            for(int r = 1; r <= k; r ++)
                ret.m[i][j] = (ret.m[i][j] + a.m[i][r] * b.m[r][j]) % Mod;
    return ret;
} 
void Debug(Node a) {
    for(int i = 1; i <= k; i ++) {
        for(int j = 1; j <= k; j ++)
            std:: cout << a.m[i][j] << " ";
        std:: cout << "\n";
    }
    exit(0);
}
Node Ksm(Node a, int pow) {
    Node ret; ret.Clear();
    while(pow) {
        if(pow & 1) ret = ret * a;
        a = a * a;
        pow >>= 1;
    }
    return ret;
}
void Get_E(Node a) {
    for(int i = 1; i <= k; i ++)
        for(int j = 1; j <= k; j ++)
            E[i][j] = a.m[i][j];
}
void Work_nk() {
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= k; j ++)
            for(int r = 1; r <= k; r ++)
                G[i][j] = (G[i][j] + A[i][r] * E[r][j] % Mod) % Mod;
}
void Work_kn() {
    for(int i = 1; i <= n; i ++)    
        for(int j = 1; j <= n; j ++)
            for(int r = 1; r <= k; r ++)
                Answer[i][j] = (Answer[i][j] + G[i][r] * B[r][j] % Mod) % Mod;
}
int Get_Answer() {
    int ret(0);
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) ret += Answer[i][j];
    return ret;
}
int main() {
    while(1) {
        memset(E, 0, sizeof E);
        memset(G, 0, sizeof G);
        memset(Answer, 0, sizeof Answer);
        memset(Use.m, 0, sizeof Use.m);
        std:: cin >> n >> k;
        if(!n && !k) break;
        for(int i = 1; i <= n; i ++) for(int j = 1; j <= k; j ++) std:: cin >> A[i][j];
        for(int i = 1; i <= k; i ++) for(int j = 1; j <= n; j ++) std:: cin >> B[i][j];
        Get_k_k();
        Pow = n * n - 1;
        Node Ans = Ksm(Use, Pow);
        Get_E(Ans);
        Work_nk();
        Work_kn();
        std:: cout << Get_Answer() << "\n";
    }
    return 0;
}