解题思路:令x=x-1代入原等式得到新的等式,两式相加,将sin()部分抵消掉,得到只含有f(x)的状态转移方程f(x+1)=f(x)+f(x-2)+f(x-3),然后用矩阵快速幂即可
#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=1e9+;
long long f[];
int temp[]={,,,-};
struct Mat
{
ll mat[][];
}res; Mat Mult(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
return c;
}
Mat QMult(Mat a,ll b)
{
Mat t;
for(int i=;i<;i++){
for(int j=;j<;j++){
t.mat[i][j]=i==j;
}
}
while(b){
if(b&)
t=Mult(t,a);//注意方向,t在前,a在后
a=Mult(a,a);
b>>=;
}
return t;
} int main()
{
int a,b,n;
while(scanf("%d%d%d",&a,&b,&n)!=EOF){
f[]=a,f[]=b;
for(int i=;i<=;i++)
f[i]=f[i-]+f[i-]+temp[(i-)%];
if(n<=){
printf("%d\n",f[n]);
continue;
}
res.mat[][]=res.mat[][]=res.mat[][]=;
res.mat[][]=res.mat[][]=res.mat[][]=;
Mat ans=QMult(res,n-);
int anss=(ans.mat[][]*f[]%mod)+(ans.mat[][]*f[]%mod);
anss=anss+(ans.mat[][]*f[]%mod)+(ans.mat[][]*f[]%mod);
printf("%d\n",anss%mod);
}
}
#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=1e9+;
long long f[];
int temp[]={,,,-};
struct Mat
{
ll mat[][];
}res; Mat Mult(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
return c;
}
Mat QMult(Mat a,ll b)
{
Mat t;
memset(t.mat,,sizeof(t.mat));
t.mat[][]=t.mat[][]=t.mat[][]=;
t.mat[][]=t.mat[][]=t.mat[][]=;
while(b){
if(b&)
a=Mult(t,a);
t=Mult(t,t);
b>>=;
}
return a;
} int main()
{
int a,b,n;
while(scanf("%d%d%d",&a,&b,&n)!=EOF){
f[]=a,f[]=b;
for(int i=;i<=;i++)
f[i]=f[i-]+f[i-]+temp[(i-)%];
if(n<=){
printf("%d\n",f[n]);
continue;
}
res.mat[][]=f[],res.mat[][]=f[];
res.mat[][]=f[],res.mat[][]=f[];
Mat ans=QMult(res,n-);
printf("%d\n",ans.mat[][]%mod);
}
}