【矩阵快速幂+矩阵运算性质】Fast Matrix Calculation HDU - 4965

╰半夏微凉° 2022-06-07 05:24 197阅读 0赞

Think:  
1知识点：矩阵快速幂+矩阵运算性质  
2题意：多组测试数据，每组测试数据先输入n, m,然后分别输入一个n\*m的矩阵A和一个m\*n的矩阵B，运算步骤如下：  
（1）：先计算C = A\*B;  
（2）：在计算M = C^(n\*n);  
（3）：M(i, j) = M(i, j) % 6;  
（4）：sum += M(i, j);  
注：  
（1）：n:\[4, 1000\],m:\[2,6\];  
（2）：A(i, j):\[0, 5\], B(i, j):\[0, 5\];  
3题意分析：  
（1）：直接用矩阵快速幂求解(A\*B)^(n\*n)会超时，且无法直接在函数间传递——编译窗口会显示：Segmentation fault (core dumped)  
（2）：将(A\*B)^(n\*n)转化为A\*(B\*A)^(n-1)\*A，进而通过矩阵快速幂求解  
注：  
（1）：A\*B:n\*n【1000\*1000】  
（2）：B\*A:m\*m【6\*6】  
4反思：  
（1）：数组越界

[vjudge题目链接][vjudge]

以下为Runtime Error(ACCESS\_VIOLATION)代码——数组越界

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int mod = 6;
    
    struct Matrix{
        int v[14][14];
    };
    
    Matrix multiply(Matrix a, Matrix b, int Matrix_len);
    Matrix matrix_pow(Matrix x, int k, int Matrix_len);
    
    int rec1[1004][14], rec2[14][1004];
    
    int main(){
        int n, m, i, j, k;
        while(~scanf("%d %d", &n, &m) && (n || m)){
            for(i = 1; i <= n; i++){
                for(j = 1; j <= m; j++){
                    scanf("%d", &rec1[i][j]);
                }
            }
            for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                    scanf("%d", &rec2[i][j]);
                }
            }
            Matrix ba;
            memset(ba.v, 0, sizeof(ba.v));
            for(i = 1; i <= m; i++){
                for(j = 1; j <= m; j++){
                    for(k = 1; k <= n; k++){
                        ba.v[i][j] += (rec2[i][k]*rec1[k][j]);
                        ba.v[i][j] %= mod;
                    }
                }
            }
            Matrix y = matrix_pow(ba, n*n-1, m);
            Matrix t1, t2;
            memset(t1.v, 0, sizeof(t1.v));
            memset(t2.v, 0, sizeof(t2.v));
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    for(int k = 1; k <= m; k++){
                        t1.v[i][j] += (rec1[i][k]*y.v[k][j]);
                        t1.v[i][j] %= mod;
                    }
                }
            }
            int sum = 0;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    for(int k = 1; k <= m; k++){
                        t2.v[i][j] += (t1.v[i][k]*rec2[k][j]);
                        t2.v[i][j] %= mod;
                    }
                    sum += t2.v[i][j];
                }
            }
            printf("%d\n", sum);
        }
        return 0;
    }
    Matrix multiply(Matrix a, Matrix b, int Matrix_len){
        Matrix c;
        memset(c.v, 0, sizeof(c.v));
        for(int i = 1; i <= Matrix_len; i++){
            for(int j = 1; j <= Matrix_len; j++){
                for(int k = 1; k <= Matrix_len; k++){
                    c.v[i][j] += (a.v[i][k]*b.v[k][j]);
                    c.v[i][j] %= mod;
                }
            }
        }
        return c;
    }
    Matrix matrix_pow(Matrix x, int k, int Matrix_len){
        Matrix ans;
        memset(ans.v, 0, sizeof(ans.v));
        for(int i = 1; i <= Matrix_len; i++)
            ans.v[i][i] = 1;
        while(k){
            if(k & 1)
                ans = multiply(ans, x, Matrix_len);
            x = multiply(x, x, Matrix_len);
            k >>= 1;
        }
        return ans;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int mod = 6;
    
    struct Matrix{
        int v[14][14];
    };
    
    Matrix multiply(Matrix a, Matrix b, int Matrix_len);
    Matrix matrix_pow(Matrix x, int k, int Matrix_len);
    
    int rec1[1004][14], rec2[14][1004], ans1[1004][1004], ans2[1004][1004];
    
    int main(){
        int n, m, i, j, k;
        while(~scanf("%d %d", &n, &m) && (n || m)){
            for(i = 1; i <= n; i++){
                for(j = 1; j <= m; j++){
                    scanf("%d", &rec1[i][j]);
                }
            }
            for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                    scanf("%d", &rec2[i][j]);
                }
            }
            Matrix ba;
            memset(ba.v, 0, sizeof(ba.v));
            for(i = 1; i <= m; i++){
                for(j = 1; j <= m; j++){
                    for(k = 1; k <= n; k++){
                        ba.v[i][j] += (rec2[i][k]*rec1[k][j]);
                        ba.v[i][j] %= mod;
                    }
                }
            }
            Matrix y = matrix_pow(ba, n*n-1, m);
    
            memset(ans1, 0, sizeof(ans1));
            memset(ans2, 0, sizeof(ans2));
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    for(int k = 1; k <= m; k++){
                        ans1[i][j] += (rec1[i][k]*y.v[k][j]);
                        ans1[i][j] %= mod;
                    }
                }
            }
            int sum = 0;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    for(int k = 1; k <= m; k++){
                        ans2[i][j] += (ans1[i][k]*rec2[k][j]);
                        ans2[i][j] %= mod;
                    }
                    sum += ans2[i][j];
                }
            }
            printf("%d\n", sum);
        }
        return 0;
    }
    Matrix multiply(Matrix a, Matrix b, int Matrix_len){
        Matrix c;
        memset(c.v, 0, sizeof(c.v));
        for(int i = 1; i <= Matrix_len; i++){
            for(int j = 1; j <= Matrix_len; j++){
                for(int k = 1; k <= Matrix_len; k++){
                    c.v[i][j] += (a.v[i][k]*b.v[k][j]);
                    c.v[i][j] %= mod;
                }
            }
        }
        return c;
    }
    Matrix matrix_pow(Matrix x, int k, int Matrix_len){
        Matrix ans;
        memset(ans.v, 0, sizeof(ans.v));
        for(int i = 1; i <= Matrix_len; i++)
            ans.v[i][i] = 1;
        while(k){
            if(k & 1)
                ans = multiply(ans, x, Matrix_len);
            x = multiply(x, x, Matrix_len);
            k >>= 1;
        }
        return ans;
    }

[vjudge]: https://vjudge.net/problem/HDU-4965