【矩阵快速幂+二分】Matrix Power Series POJ - 3233

╰半夏微凉° 2022-06-10 10:23 169阅读 0赞

Think:  
1知识点：矩阵快速幂+二分求解等比矩阵前n项和  
2题意：输入一个矩阵，求解矩阵前n项和(S = A^1 + A^2 + A^3 + … + A^k.)，模mod

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 40;
    
    typedef struct Matrax{
        int m[N][N];
    }matrax;
    
    matrax e, per;
    int n, m, mod;
    
    void read();/*读取矩阵+初始化单位矩阵*/
    matrax Add(matrax a, matrax b);/*矩阵加法*/
    matrax multi(matrax a, matrax b);/*矩阵乘法*/
    matrax power(int k);/*矩阵快速幂*/
    matrax matrax_sum(int k);/*等比矩阵前n项和*/
    void Pri(matrax ans);/*输出矩阵*/
    
    int main(){
        while(~scanf("%d %d %d", &n, &m, &mod)){
            read();
            matrax ans = matrax_sum(m);
            Pri(ans);
        }
        return 0;
    }
    void read(){
       /*读取矩阵+初始化单位矩阵*/
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                scanf("%d", &e.m[i][j]);
                e.m[i][j] %= mod;
                per.m[i][j] = (i == j);
            }
        }
    }
    matrax Add(matrax a, matrax b){
       /*矩阵加法*/
        matrax c;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                c.m[i][j] = (a.m[i][j] + b.m[i][j])%mod;
            }
        }
        return c;
    }
    matrax multi(matrax a, matrax b){
       /*矩阵乘法*/
        matrax c;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                c.m[i][j] = 0;
                for(int k = 0; k < n; k++){
                    c.m[i][j] += (a.m[i][k] * b.m[k][j])%mod;
                }
                c.m[i][j] %= mod;
            }
        }
        return c;
    }
    matrax power(int k){
       /*矩阵快速幂*/
        matrax p, ans = per;
        p = e;
        while(k){
            if(k & 1)
                ans = multi(ans, p);
            p = multi(p, p);
            k >>= 1;
        }
        return ans;
    }
    matrax matrax_sum(int k){
       /*等比矩阵前n项和*/
        if(k == 1)
            return e;
        matrax tmp, b;
        tmp = matrax_sum(k>>1);
        if(k & 1){
            b = power((k>>1)+1);
            tmp = Add(tmp, multi(b, tmp));
            tmp = Add(tmp, b);
        }
        else {
            b = power(k>>1);
            tmp = Add(tmp, multi(b, tmp));
        }
        return tmp;
    }
    void Pri(matrax ans){
       /*输出矩阵*/
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                printf("%d%c", ans.m[i][j], j == n-1? '\n': ' ');
            }
        }
    }

[vjudge]: https://vjudge.net/problem/POJ-3233