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

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

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题目链接
建议参考博客——分析+代码实现

以下为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;
}