P4838 P哥破解密码
矩乘优化递推 (hint:N<=10e9,线性的都没法了)
f[i][j](i ∈[ 1,n], j ∈ [0,2])，表示 n==i 时，一个数末尾有j个A的方案数。
由于末尾有A的可能性只与上一状态中一个状态有关（1个A与0个A有关，2个A与1个A有关）。
而末尾有0个AA的情况，只要塞一个B就行了。所以是上一状态中所有状态方案数之和。
初始化：
f[1][0]=1,f[1][1]=1,f[1][2]=0;
转移方程：
f[i][0] = f[i - 1][2] + f[i - 1][1] + f[i - 1][0]
f[i][1] = f[i - 1][0]
f[i][2] = f[i - 1][1]
下文中坐标+了1
//1 1 0
/*
1 1 0
1 0 1
1 0 0
*/
#define mod 19260817
struct Matrix{
int m[4][4];
Matrix(){mem(m,0);}
friend Matrix operator *(Matrix a,Matrix b){
Matrix c;
rep(i,1,3)
rep(j,1,3)
rep(k,1,3)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return c;
}
friend Matrix operator ^(Matrix a,int k){
Matrix res;
rep(i,1,3)res.m[i][i]=1;
for(;k;k>>=1){
if(k&1)res=res*a;
a=a*a;
}
return res;
}
};
int T;rd(T);
while(T--){
int n;rd(n);
Matrix A;
A.m[1][1]=1;A.m[1][2]=1;
Matrix base;
base.m[1][1]=1,base.m[1][2]=1,base.m[1][3]=0;
base.m[2][1]=1,base.m[2][2]=0,base.m[2][3]=1;
base.m[3][1]=1,base.m[3][2]=0,base.m[3][3]=0;
base=base^(n-1);
A=A*base;
printf("%lld
",(A.m[1][1]+A.m[1][2]+A.m[1][3])%mod);
}