HDU 5950——Recursive sequence

深碍√TFBOYSˉ_ 2022-07-15 04:56 114阅读 0赞

*  Recursive sequence

题意：给定起始的两个数a,b，求第n个数%mod

思路：  
第一眼看出来是矩阵快速幂，不过当时没推出来（其实推了一半把自己给否定了）  
正解是，根据二项式定理，对于f(n)=f(n-1)+2f(n-2)+n^4可以转换为  
f(n)=f(n-1)+2f(n-2)+c(4,0)(n-1)^4+c(4,1)(n-1)^3+c(4,2)(n-1)^2+c(4,3)(n-1)+c(4,4) (\#1)

那么，对于下一项:  
f(n+1)=f(n)+2f(n-1)+c(4,0)(n)^4+c(4,1)(n)^3+c(4,2)(n)^2+c(4,3)(n)+c(4,4) (\#2)

可以发现\#2的f(n),f(n-1),n^4,n^3,n^2,n,1都可以通过\#1构造出来，那么根据倍数关系构造相关的矩阵即可。

code:

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const ll mod = 2147493647ll;
    
    struct Matirx{
        int r, c;
        ll mat[10][10];
    };
    
    Matirx Mul(Matirx a, Matirx b){
        Matirx ret;
        ret.r = a.r;
        ret.c = b.c;
        for(int i = 0; i < ret.r; i++){ 
            for(int j = 0; j < ret.c; j++){ 
                ret.mat[i][j] = 0;
                for(int k = 0; k < a.c; k++){ 
                    ret.mat[i][j] += a.mat[i][k]*b.mat[k][j];
                    ret.mat[i][j] %= mod;
                }
            }
        }
        return ret;
    }
    
    Matirx Quick_pow(Matirx a, ll n){
        Matirx ret;
        ret.r = ret.c = 7;
        memset(ret.mat, 0, sizeof(ret.mat));
        for(int i = 0; i < 7; i++) ret.mat[i][i] = 1;
        while(n){
            if(n&1) ret = Mul(ret, a);
            a = Mul(a, a);
            n >>= 1;
        }
        return ret;
    }
    
    void build(Matirx& t){
        t.r = t.c = 7;
        t.mat[0][0] = 1, t.mat[0][1] = 4, t.mat[0][2] = 6, t.mat[0][3] = 4, t.mat[0][4] = 1, t.mat[0][5] = 0, t.mat[0][6] = 0;//1
        t.mat[1][0] = 0, t.mat[1][1] = 1, t.mat[1][2] = 3, t.mat[1][3] = 3, t.mat[1][4] = 1, t.mat[1][5] = 0, t.mat[1][6] = 0;//2
        t.mat[2][0] = 0, t.mat[2][1] = 0, t.mat[2][2] = 1, t.mat[2][3] = 2, t.mat[2][4] = 1, t.mat[2][5] = 0, t.mat[2][6] = 0;//2
        t.mat[3][0] = 0, t.mat[3][1] = 0, t.mat[3][2] = 0, t.mat[3][3] = 1, t.mat[3][4] = 1, t.mat[3][5] = 0, t.mat[3][6] = 0;//4
        t.mat[4][0] = 0, t.mat[4][1] = 0, t.mat[4][2] = 0, t.mat[4][3] = 0, t.mat[4][4] = 1, t.mat[4][5] = 0, t.mat[4][6] = 0;//5
        t.mat[5][0] = 0, t.mat[5][1] = 0, t.mat[5][2] = 0, t.mat[5][3] = 0, t.mat[5][4] = 0, t.mat[5][5] = 0, t.mat[5][6] = 1;//6
        t.mat[6][0] = 1, t.mat[6][1] = 4, t.mat[6][2] = 6, t.mat[6][3] = 4, t.mat[6][4] = 1, t.mat[6][5] = 2, t.mat[6][6] = 1;//7
    }
    
    int main(){
        int T;
        scanf("%d", &T);
        ll N, a, b;
        while(T--){
            scanf("%I64d%I64d%I64d", &N, &a, &b);
            if(N == 1) printf("%I64d\n", a%mod);
            else if(N == 2) printf("%I64d\n", b%mod);
            else{
                Matirx temp;
                build(temp);
                Matirx ret = Quick_pow(temp, N-2);
                temp.r = 7;
                temp.c = 1;
                temp.mat[0][0] = 16,temp.mat[1][0] = 8,temp.mat[2][0] = 4,temp.mat[3][0] = 2,temp.mat[4][0] = 1,temp.mat[5][0] = a%mod, temp.mat[6][0] = b%mod;
                ret = Mul(ret, temp);
                printf("%I64d\n", ret.mat[6][0]);
            }
        }
        return 0;
    }