HDU5950【矩阵快速幂】

主要还是i^4化成一个(i+1)^4没遇到过，还是很基础的一题矩阵快速幂；
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod=2147493647;

const int N=1e5+10;

struct asd{

    LL num[8][8];

};

asd mul(asd a,asd b)

{

    asd ans;

    memset(ans.num,0,sizeof(ans.num));

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

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

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

                ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;

    return ans;

}

asd quickmul(LL g,asd x)

{

    asd ans;

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

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

        {

            if(i==j)

                ans.num[i][j]=1;

            else

                ans.num[i][j]=0;

        }

    while(g)

    {

        if(g%2)

            ans=mul(ans,x);

        x=mul(x,x);

        g>>=1;

    }

    return ans;

}

int main()

{

    int T;

    LL n,A,B;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld%lld",&n,&A,&B);

        if(n==1)

        {

            printf("%lld\n",A%mod);

        }

        else if(n==2)

            printf("%lld\n",B%mod);

        else

        {

            asd tmp;

            tmp.num[0][0]=1;tmp.num[0][1]=2;tmp.num[0][2]=1;tmp.num[0][3]=4;tmp.num[0][4]=6;tmp.num[0][5]=4;tmp.num[0][6]=1;

            tmp.num[1][0]=1;tmp.num[1][1]=0;tmp.num[1][2]=0;tmp.num[1][3]=0;tmp.num[1][4]=0;tmp.num[1][5]=0;tmp.num[1][6]=0;

            tmp.num[2][0]=0;tmp.num[2][1]=0;tmp.num[2][2]=1;tmp.num[2][3]=4;tmp.num[2][4]=6;tmp.num[2][5]=4;tmp.num[2][6]=1;

            tmp.num[3][0]=0;tmp.num[3][1]=0;tmp.num[3][2]=0;tmp.num[3][3]=1;tmp.num[3][4]=3;tmp.num[3][5]=3;tmp.num[3][6]=1;

            tmp.num[4][0]=0;tmp.num[4][1]=0;tmp.num[4][2]=0;tmp.num[4][3]=0;tmp.num[4][4]=1;tmp.num[4][5]=2;tmp.num[4][6]=1;

            tmp.num[5][0]=0;tmp.num[5][1]=0;tmp.num[5][2]=0;tmp.num[5][3]=0;tmp.num[5][4]=0;tmp.num[5][5]=1;tmp.num[5][6]=1;

            tmp.num[6][0]=0;tmp.num[6][1]=0;tmp.num[6][2]=0;tmp.num[6][3]=0;tmp.num[6][4]=0;tmp.num[6][5]=0;tmp.num[6][6]=1;

            asd ans;

            ans=quickmul(n-2,tmp);

            LL res;

//            printf("%lld %lld %lld \n",ans.num[0][0],ans.num[0][1],ans.num[0][2]);

            res=((ans.num[0][0]*B%mod+ans.num[0][1]*A%mod)%mod+ans.num[0][2]*16%mod+ans.num[0][3]*8%mod+ans.num[0][4]*4%mod+ans.num[0][5]*2%mod+ans.num[0][6])%mod;

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

        }

    }

    return 0;

}
巴特西

HDU5950【矩阵快速幂】

最新文章

热门文章
