【题目太长 直接压缩了下】

当n>=3时有，F[n] = 2f[n - 1] + 3f[n - 2] + 3*n^5
输入Ｔ表示测试案例的组数(1e3)

接下来Ｔ行，每行三个数字n, a, b　(1 <= n,a,b <= 2^31 )

表示数列第一项是a, 第二项是b

Output
对于每组数据你需要输出一行，代表计算数列的第n项模2147493647 的结果。

SampleInput
2
3 1 1
3 1 2
SampleOutput
734
736

显然on直接TLE 所以需要降复杂度 看到了递推式 显然矩阵快速幂 那么唯一的难点就是构造矩阵了
这里的矩阵构造主要难在了 n^5的处理 怎么把n跟(n-1)扯上关系 这里就用到了二项展开式了

这个推出来后 这题简直是轻松+easy啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2147493647;
struct node///结构体存矩阵
{
    ll sb[9][9];
} hsy,sum;
ll biao[9][9]=  ///构造的矩阵
{
    0,0,0,0,0,0,0,0,0,
    0,2,1,0,0,0,0,0,0,
    0,3,0,0,0,0,0,0,0,
    0,3,0,1,0,0,0,0,0,
    0,15,0,5,1,0,0,0,0,
    0,30,0,10,4,1,0,0,0,
    0,30,0,10,6,3,1,0,0,
    0,15,0,5,4,3,2,1,0,
    0,3,0,1,1,1,1,1,1,
};
node juzhen(ll a[][9],ll b[][9])///矩阵相乘
{

    node shit;
    memset(shit.sb,0,sizeof shit.sb);
    for(int i=1; i<=8; i++)
    {
        for(int j=1; j<=8; j++)
        {
            for(int k=1; k<=8; k++)
            {
                shit.sb[i][j]=(shit.sb[i][j]%mod+((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;

            }
        }
    }


    return shit;


}
ll qsm(ll a,ll b,ll n)   ///快速幂
{


    memset(sum.sb,0,sizeof sum.sb);
    memcpy(hsy.sb, biao, 81*sizeof(ll));
    sum.sb[1][1]=b,sum.sb[1][2]=a,sum.sb[1][8]=1;
    ll s=1;
    for(ll i=1; i<=5; i++)
    {
        s*=2;
        sum.sb[1][8-i]=s;
    }
    while(n)
    {

        if(n&1)
            sum=juzhen(sum.sb,hsy.sb);

        hsy=juzhen(hsy.sb,hsy.sb);
        n/=2;
    }
    cout<<sum.sb[1][1]%mod<<endl;

}
int main()
{
    int t;
    ll a,b,n;
    cin>>t;
    while(t--)
    {

        scanf("%lld%lld%lld",&n,&a,&b);
        if(n>=3)
            qsm(a%mod,b%mod,n-2);
        else if(n==1)
            cout<<a%mod<<endl;
        else
            cout<<b%mod<<endl;
    }
}