HDU 5950 Recursive sequence（矩阵快速幂）题解

思路：一开始不会n^4的推导，原来是要找n和n-1的关系，这道题的MOD是long long 的，矩阵具体如下所示

最近自己总是很坑啊，代码都瞎吉坝写，一个long long的输入写成%d一直判我TLE，一度怀疑矩阵快速幂地复杂度orz

代码：

#include<set>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define ll long long

const int maxn = 7;

const ll MOD = 2147493647;

const int INF = 0x3f3f3f3f;

using namespace std;

struct Mat{

    ll s[maxn][maxn];

};

Mat mul(Mat a,Mat b){

    Mat t;

    memset(t.s,0,sizeof(t));

    for(int i = 0;i < maxn;i++){

        for(int j = 0;j < maxn;j++){

            for(int k = 0;k < maxn;k++){

                t.s[i][j] = (t.s[i][j] + a.s[i][k]*b.s[k][j])%MOD;

            }

        }

    }

    return t;

}

Mat pow_mat(Mat p,int n){

    Mat ret;

    memset(ret.s,0,sizeof(ret.s));

    for(int i = 0;i < maxn;i++)

        ret.s[i][i] = 1;

    while(n){

        if(n & 1) ret = mul(ret,p);

        p = mul(p,p);

        n >>= 1;

    }

    return ret;

}

int main(){

    ll T,a,b,n;

    Mat A,B,C;

    memset(A.s,0,sizeof(A.s));

    A.s[0][0] = A.s[0][2] = A.s[1][0] = A.s[2][2] = A.s[3][3] = A.s[4][4] = A.s[5][5] = 1;

    for(int i = 0;i < 7;i++)

        A.s[i][6] = 1;

    A.s[1][6] = 0;

    A.s[0][1] = A.s[4][5] = 2;

    A.s[3][4] = A.s[3][5] = 3;

    A.s[0][3] = A.s[0][5] = A.s[2][3] = A.s[2][5] = 4;

    A.s[0][4] = A.s[2][4] = 6;

    /*for(int i = 0;i < 7;i++){

        for(int j = 0;j < 7;j++){

            printf("%d ",A.s[i][j]);

        }

        printf("\n");

    }*/

    scanf("%lld",&T);

    while(T--){

        scanf("%lld%lld%lld",&n,&a,&b);

        if(n == 1){

            printf("%lld\n",a);

        }

        else if(n == 2){

            printf("%lld\n",b);

        }

        else{

            C = pow_mat(A,n - 2);

            ll ans = 0;

            ans = (C.s[0][0]*b%MOD + C.s[0][1]*a%MOD + C.s[0][2]*16%MOD +

                   C.s[0][3]*8%MOD + C.s[0][4]*4%MOD + C.s[0][5]*2%MOD + C.s[0][6])%MOD;

            printf("%lld\n",ans);

        }

    }

    return 0;

}

巴特西

HDU 5950 Recursive sequence（矩阵快速幂）题解

最新文章

热门文章