原题图:
看到这个题,首先想到的当然是暴力打表找规律了
表:
1 2
2 4
3 7
4 13
5 24
6 44
7 81
8 149
9 274
10 504
11 927
12 1705
13 3136
14 5768
15 10609
发现上下两个数近似于2倍关系,但f[i-1]*2略大于f[i]
用f[i-1]*2-f[i],发现恰好等于f[i-4]
于是就有了递推式:f[i]=f[i-1]*2-f[i-4]
矩阵加速即可
矩阵加速的方法:
我们有一个4*4的矩阵A和一个向量c[13,7,4,2],
我们要让c*A得到向量c1[13*2-2,13,7,4]
于是得到下面的矩阵:
2 1 0 0
0 0 1 0
0 0 0 1
-1 0 0 0
矩阵快速幂即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MOD 19260817
#define int long long
int T,n,ans[]={,,,,};
struct Matrix{
int m[][];
} O,E,A;
inline Matrix Mul(Matrix X,Matrix Y){
Matrix Ans=O;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
Ans.m[i][j]=(Ans.m[i][j]+X.m[i][k]*Y.m[k][j])%MOD;
return Ans;
}
Matrix qpow(Matrix X,int k){
Matrix S=E;
while(k){
if(k&) S=Mul(S,X);
k>>=;
X=Mul(X,X);
}
return S;
}
#undef int
int main()
#define int long long
{
E.m[][]=E.m[][]=E.m[][]=E.m[][]=;
A.m[][]=;
A.m[][]=;
A.m[][]=;
A.m[][]=-;
A.m[][]=;
scanf("%lld",&T);
for(int i=;i<=T;i++){
scanf("%lld",&n);
if(n<=){
printf("%lld\n",ans[n]);
continue;
}
Matrix Ans=qpow(A,n-);
int ans=((Ans.m[][]*+Ans.m[][]*+Ans.m[][]*+Ans.m[][]*)%MOD+MOD)%MOD;
printf("%lld\n",ans);
}
return ;
}