题意
f[n]=f[n-1]+2*f[n-2]+n^4; f[1]=a f[2]=b 求第n项
题解
由于n太大，直接递推肯定会超时间，因此用到矩阵快速幂
先推一下
[(n+1)^4=n^4+4n^3+6n^2+4n+1\
(n+1)^3=n^3+3n^2+3n+1\
(n+1)^2=n^2+2n+1]
因此构造矩阵
[egin{bmatrix} 1&2&1&0&0&0&0\1&0&0&0&0&0&0\0&0&1&4&6&4&1\0&0&0&1&3&3&1\0&0&0&0&1&2&1\0&0&0&0&0&1&1\0&0&0&0&0&0&1 end{bmatrix}
]
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 2147493647;
struct node{LL c[7][7];};
node mul(node x,node y)
{
node res;
for(int i=0;i<7;i++)
for(int j=0;j<7;j++)
{
res.c[i][j]=0;
for(int k=0;k<7;k++)
res.c[i][j]=(res.c[i][j]+(x.c[i][k]*y.c[k][j])%mod)%mod;
}
return res;
}
node quickmod(node x,int y)
{
node res;
for(int i=0;i<7;i++)
for(int j=0;j<7;j++)
{
if(i==j)res.c[i][j]=1;
else res.c[i][j]=0;
}
while(y)
{
if(y&1)res=mul(res,x);
y>>=1;
x=mul(x,x);
}
return res;
}
int main()
{
node t;
for(int i=0;i<7;i++)
for(int j=0;j<7;j++)t.c[i][j]=0;
t.c[0][0]=1;t.c[0][1]=2;t.c[0][2]=1;t.c[1][0]=1;
t.c[2][2]=1;t.c[2][3]=4;t.c[2][4]=6;t.c[2][5]=4;t.c[2][6]=1;
t.c[3][3]=1;t.c[3][4]=3;t.c[3][5]=3;t.c[3][6]=1;
t.c[4][4]=1;t.c[4][5]=2;t.c[4][6]=1;
t.c[5][5]=1;t.c[5][6]=1;t.c[6][6]=1;
int T;
cin>>T;
while(T--)
{
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
if(n==1)printf("%d
",a%mod);
else if(n==2)printf("%d
",b%mod);
else
{
node now=quickmod(t,n-2);
node s;
for(int i=0;i<7;i++)
for(int j=0;j<7;j++)s.c[i][j]=0;
s.c[0][0]=b%mod;s.c[1][0]=a%mod;s.c[2][0]=81;s.c[3][0]=27;
s.c[4][0]=9;s.c[5][0]=3;s.c[6][0]=1;
node ans=mul(now,s);
printf("%lld
",ans.c[0][0]);
}
}
return 0;
}