D - A Short problem HDU - 4291——矩阵快速幂

约定不等于承诺〃 2022-06-10 02:14 363阅读 0赞

Think:  
1知识点：矩阵快速幂  
2反思：  
1>内嵌关系取模考虑循环节和矩阵快速幂  
2>矩阵快速幂通过把数放到初始矩阵的不同位置，进而将普通的递推式转换为“矩阵的等比数列”，进而快速幂求解递推式  
3>矩阵快速幂解题步骤:  
第一步列出递推式  
第二步建立矩阵递推式，找到转移矩阵

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod0 = 1000000007;
    const int mod1 = 222222224;
    const int mod2 = 183120;
    const int mod3 = 240;
    
    struct Mat{
        LL rx[4][4];
    };
    
    struct Mat Mul(struct Mat a, struct Mat b, int mod);
    struct Mat pow_mod(struct Mat a, int k, int mod);
    
    /*循环节*/
    /*int main(){
        LL a, b, c;
        a = 0, b = 1;
        for(LL i = 3; ; i++){
            c = (3*b + a)%mod;///通过mod得到mod1进而得到mod2进而得到mod3
            a = b;
            b = c;
            if(a == 0 && b == 1){
                printf("%lld\n", i-2);
                break;
            }
        }
        return 0;
    }*/
    /*mod0 = 1000000007*/
    /*mod1 = 222222224*/
    /*mod2 = 183120*/
    /*mod3 = 240*/
    
    int main(){
        struct Mat tmp;
        tmp.rx[0][0] = 3;
        tmp.rx[0][1] = 1;
        tmp.rx[1][0] = 1;
        tmp.rx[1][1] = 0;
        LL n;
        while(~scanf("%lld", &n)){
            n %= mod3;
    
            if(!n){
                printf("0\n");
                continue;
            }
    
            n = pow_mod(tmp, n-1, mod2).rx[0][0];
    
            n = pow_mod(tmp, n-1, mod1).rx[0][0];
    
            n = pow_mod(tmp, n-1, mod0).rx[0][0];
    
            printf("%lld\n", n);
        }
        return 0;
    }
    struct Mat pow_mod(struct Mat a, int k, int mod){
        struct Mat ans;
        for(int i = 0; i < 2; i++){
            ans.rx[i][i] = 1;
            for(int j = i+1; j < 2; j++){
                ans.rx[i][j] = ans.rx[j][i] = 0;
            }
        }
        while(k){
            if(k & 1)
                ans  = Mul(ans, a, mod);
            a = Mul(a, a, mod);
            k >>= 1;
        }
        return ans;
    }
    struct Mat Mul(struct Mat a, struct Mat b, int mod){
        struct Mat ans;
        memset(ans.rx, 0, sizeof(ans.rx));
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                for(int k = 0; k < 2; k++){
                    ans.rx[i][j] += (a.rx[i][k]*b.rx[k][j])%mod;
                    ans.rx[i][j] %= mod;
                }
            }
        }
        return ans;
    }

[vjudge]: https://vjudge.net/contest/175272#problem/D