hdu6470 矩阵快速幂+构造矩阵

http://acm.hdu.edu.cn/showproblem.php?pid=6470

题意

\(f[n]=2f[n-2]+f[n-1]+n^3,n \leq 10^{18}\),求f[n]

题解

每一项只能由上一项经线性变换转移过来

代码

#include<bits/stdc++.h>

#define P 123456789

#define ll long long

using namespace std;

struct N{

    ll a[10][10];

};

N mul(N x,N y){

    N z;

    memset(z.a,0,sizeof(z.a));

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

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

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

                z.a[i][j]+=(x.a[i][k]*y.a[k][j])%P;

                z.a[i][j]%=P;

            }

        }

    }

    return z;

}

N pw(N y,ll x){

    N z;memset(z.a,0,sizeof(z.a));

    for(int i=0;i<6;i++)z.a[i][i]=1;

    while(x){

        if(x&1)z=mul(z,y);

        y=mul(y,y);

        x>>=1;

    }

    return z;

}

int T;

ll n,ans,a[]={2,1,8,4,2,1};

int b[][6]={{1,1,0,0,0,0},

            {2,0,0,0,0,0},

            {1,0,1,0,0,0},

            {3,0,3,1,0,0},

            {3,0,3,2,1,0},

            {1,0,1,1,1,1}};

int main(){

    cin>>T;

    while(T--){

        ans=0;

        cin>>n;

        if(n==1)printf("1\n");

        else if(n==2)printf("2\n");

        else{

            N y;memset(y.a,0,sizeof(y.a));

            y.a[0][0]=y.a[0][1]=1;

            y.a[1][0]=2;

            y.a[2][0]=y.a[2][2]=1;

            y.a[3][0]=y.a[3][2]=3;y.a[3][3]=1;

            y.a[4][0]=y.a[4][2]=3;y.a[4][3]=2;y.a[4][4]=1;

            y.a[5][0]=y.a[5][2]=y.a[5][3]=y.a[5][4]=y.a[5][5]=1;

            y=pw(y,n-2);

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

                ans+=a[i]*y.a[i][0]%P;

                ans%=P;

            }

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

        }

    }

}

巴特西

hdu6470 矩阵快速幂+构造矩阵

题意

题解

代码

最新文章

热门文章