HDU 5950 - 2016ACM/ICPC亚洲区沈阳站 - C.Recursive sequence - （矩阵快速幂）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5950

题意：有序列F(n)=F(n-1)+2*F(n-2)+n^4；题目输入N,F(1),F(2)让输出F(N)。N,F(1),F(2) < 2^31

解析：人尽皆知矩阵快速幂，推出以下转移矩阵即可：

代码(9ms)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2147493647;
const int M=7;

ll N,a,b;

struct Matrix
{
    Matrix(){memset(a,0,sizeof(a));}
    ll a[M][M];
    void init()
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<M;i++)
            a[i][i]=1;
    }
}A;

Matrix mul(Matrix a,Matrix b)
{
    Matrix ans;
    int i,j,k;
    for(i=0;i<M;i++)
        for(j=0;j<M;j++)
    {
        for(k=0;k<M;k++)
        {
            ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
        }
        //ans.a[i][j]%=mod;
    }
    return ans;
}

Matrix pow(Matrix a,ll n)
{
    Matrix ans;
    ans.init();
    while(n)
    {
        if(n&1)
            ans=mul(ans,a);
        n>>=1;
        a=mul(a,a);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&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{
            A.a[0][0]=1; A.a[0][1]=2; A.a[0][2]=1; A.a[0][3]=0; A.a[0][4]=0; A.a[0][5]=0; A.a[0][6]=0;
            A.a[1][0]=1; A.a[1][1]=0; A.a[1][2]=0; A.a[1][3]=0; A.a[1][4]=0; A.a[1][5]=0; A.a[1][6]=0;
            A.a[2][0]=0; A.a[2][1]=0; A.a[2][2]=1; A.a[2][3]=4; A.a[2][4]=6; A.a[2][5]=4; A.a[2][6]=1;
            A.a[3][0]=0; A.a[3][1]=0; A.a[3][2]=0; A.a[3][3]=1; A.a[3][4]=3; A.a[3][5]=3; A.a[3][6]=1;
            A.a[4][0]=0; A.a[4][1]=0; A.a[4][2]=0; A.a[4][3]=0; A.a[4][4]=1; A.a[4][5]=2; A.a[4][6]=1;
            A.a[5][0]=0; A.a[5][1]=0; A.a[5][2]=0; A.a[5][3]=0; A.a[5][4]=0; A.a[5][5]=1; A.a[5][6]=1;
            A.a[6][0]=0; A.a[6][1]=0; A.a[6][2]=0; A.a[6][3]=0; A.a[6][4]=0; A.a[6][5]=0; A.a[6][6]=1;

            A=pow(A,N-2);
            ll ans=A.a[0][0]*b%mod+A.a[0][1]*a%mod+A.a[0][2]*81%mod+A.a[0][3]*27%mod+A.a[0][4]*9%mod+A.a[0][5]*3%mod+A.a[0][6];
            printf("%lld\n",ans%mod);
        }
    }
    return 0;
}