【矩阵幂的和+矩阵快速幂】Power of Matrix UVA - 11149

本是古典何须时尚 2022-06-07 06:09 201阅读 0赞

Think:  
1知识点：矩阵幂的和+矩阵快速幂  
2题意：输入矩阵A，求A^1 + A^2 + … + A^(n)  
3题意分析：  
（1）：倍增法求矩阵幂的和，eg:  
求：A^1 + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 + A^8 + A^9 + A^10  
(1):A^1 + A^2 + A^3 + A^4 + A^5 + A^6 + A^7 + A^8 + A^9 + A^10 = (A^1+A^2+A^3+A^4+A^5) + (A^5)\*(A^1+A^2+A^3+A^4+A^5)  
(2):A^1 + A^2 + A^3 + A^4 + A^5 = (A^1+A^2) + (A^2)\*(A^1+A^2) + A^5  
(3):A^1 + A^2 = (A^1) + (A^1)\*(A^1)  
(4):A^1 = A^1  
代码实现如下：

/*倍增法求解A^1 + A^2 + ... + A^n*/
    Matrix pow_sum(const Matrix &a, int n){
        ///递归终点
        if(n == 1) return a;
        ///tmp递归表示A^1 + A^2 + ... + A^(n/2)
        Matrix tmp = pow_sum(a, n/2);
        ///sum表示(A^1+...+A^(n/2)) + (A^1+...+A^(n/2))*(A^(n/2))
        Matrix sum = tmp + tmp*a.pow(n/2);
        ///若n为奇数，n/2 + n/2 = n-1, 因此sum需要加上A^(n)这一项
        if(n & 1) sum = sum + a.pow(n);
        return sum;
    }

4反思：  
（1）：构造函数只声明未定义——error:ld returned 1 exit status  
（2）：删除构造函数2之后，有的函数未补充().v数组初始化

[vjudge题目链接][vjudge]  
[建议参考博客——分析+代码实现][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int mod = 10;
    
    class Matrix{
    public:
        int row, col;
        int v[54][54];
        Matrix(){}
        ~Matrix(){}
        Matrix operator + (const Matrix &sec) const;
        Matrix operator * (const Matrix &sec) const;
        Matrix & operator = (const Matrix &sec);
        Matrix pow(int n) const;
    };
    
    Matrix Matrix::operator + (const Matrix &sec) const{
        Matrix tmp;
        tmp.row = sec.row, tmp.col = sec.col;
        for(int i = 1; i <= tmp.row; i++){
            for(int j = 1; j <= tmp.col; j++){
                tmp.v[i][j] = (v[i][j] + sec.v[i][j]) % mod;
            }
        }
        return tmp;
    }
    Matrix Matrix::operator * (const Matrix &sec) const{
        Matrix tmp;
        tmp.row = row, tmp.col = sec.col;
        memset(tmp.v, 0, sizeof(tmp.v));
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= sec.col; j++){
                for(int k = 1; k <= col; k++){
                    tmp.v[i][j] += (v[i][k]*sec.v[k][j]);
                    tmp.v[i][j] %= mod;
                }
            }
        }
        return tmp;
    }
    Matrix & Matrix::operator = (const Matrix &sec){
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                v[i][j] = sec.v[i][j];
            }
        }
        return *this;
    }
    Matrix Matrix::pow(int n) const{
        Matrix a(*this);
        Matrix ans;
        ans.row = row, ans.col = col;
        memset(ans.v, 0, sizeof(ans.v));
        for(int i = 1; i <= ans.row; i++)
            ans.v[i][i] = 1;
        while(n){
            if(n & 1)
                ans = ans * a;
            a = a * a;
            n >>= 1;
        }
        return ans;
    }
    
    Matrix pow_sum(const Matrix &a, int n);/*倍增法求解A^1 + A^2 + ... + A^n*/
    
    int main(){
        int n, r, i, j;
        while(~scanf("%d %d", &n, &r) && n){
            Matrix test;
            test.row = n, test.col = n;
            for(i = 1; i <= test.row; i++){
                for(j = 1; j <= test.col; j++){
                    scanf("%d", &test.v[i][j]);
                    test.v[i][j] %= 10;
                }
            }
            Matrix ans = pow_sum(test, r);
            for(i = 1; i <= ans.row; i++){
                for(j = 1; j <= ans.col; j++){
                    printf("%d%c", ans.v[i][j], j == ans.col? '\n': ' ');
                }
            }
            printf("\n");
        }
        return 0;
    }
    /*倍增法求解A^1 + A^2 + ... + A^n*/
    Matrix pow_sum(const Matrix &a, int n){
        ///递归终点
        if(n == 1) return a;
        ///tmp递归表示A^1 + A^2 + ... + A^(n/2)
        Matrix tmp = pow_sum(a, n/2);
        ///sum表示(A^1+...+A^(n/2)) + (A^1+...+A^(n/2))*(A^(n/2))
        Matrix sum = tmp + tmp*a.pow(n/2);
        ///若n为奇数，n/2 + n/2 = n-1, 因此sum需要加上A^(n)这一项
        if(n & 1) sum = sum + a.pow(n);
        return sum;
    }

[vjudge]: https://vjudge.net/problem/UVA-11149
[Link 1]: http://blog.csdn.net/luomingjun12315/article/details/50824552