题目背景
P哥是一个经常丢密码条的男孩子。
在ION 8102赛场上,P哥又弄丢了密码条,笔试满分的他当然知道这可是要扣5分作为惩罚的,于是他开始破解ION Xunil系统的密码。
题目描述
定义一个串合法，当且仅当串只由A和B构成，且没有连续的3个A。P哥知道，密码就是长度为N的合法字符串数量对19260817取模的结果。但是P哥不会算，所以他只能把N告诉你，让你来算
至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P哥也不记得了
然而他忘记字符串长度N应该是多少了，于是他准备试M组数据。
题目解析
WA了两次。
递推题，在长度为n-1的合法串中有这几种：末尾有连续2个A，末尾有1个A，末尾不是A。
然后稍加思考就可以发现在长度为n的串中末尾连续2个A的可以由长度为n-1的合法串中末尾是1个A的得到。
类似的，末尾一个A的可以由末尾没有A的得到，末尾是B的能由所有状态得到。
所以我们构造出下面的矩阵三行分别表示末尾是B，末尾1个A，末尾2个A。
1，1，1
1，0，0
0，1，0
矩阵快速幂+取模即可。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const long long p = ; struct Matrix {
long long m[][];
long long sizx,sizy;
void reset() {
for(int i = ;i <= sizx;i++) {
for(int j = ;j <=sizy;j++) {
if(i == j) m[i][j] = ;
else m[i][j] = ;
}
}
return;
}
void clean() {
memset(m,,sizeof(m));
return;
}
} pro; int T;
long long n,ans;
/*
1,1,1
1,0,0
0,1,0
*/
inline void init() {
pro.sizx = , pro.sizy = ;
pro.clean();
pro.m[][] = pro.m[][] = pro.m[][] = pro.m[][] = pro.m[][] = ;
return;
} inline Matrix mul(Matrix x,Matrix y) {
Matrix res;
res.clean();
res.sizx = x.sizx, res.sizy = y.sizy;
for(register int i = ;i <= x.sizx;i++) {
for(register int j = ;j <= y.sizy;j++) {
for(register int k = ;k <= x.sizy;k++) {
res.m[i][j] += x.m[i][k] * y.m[k][j] % p;
res.m[i][j] %= p;
}
}
}
return res;
} inline Matrix quick_pow(Matrix x,long long y) {
Matrix res;
res.sizx = x.sizx; res.sizy = x.sizy;
res.reset();
while(y) {
if(y & ) res = mul(res,x);
x = mul(x,x);
y >>= ;
}
return res;
} int main() {
scanf("%d",&T);
while(T--) {
scanf("%lld",&n);
if(n == ) {puts("");continue;}
else if(n == ) {puts("");continue;}
else if(n == ) {puts("");continue;}
init();
Matrix final = quick_pow(pro,n);
printf("%lld\n",(final.m[][]+final.m[][])%p);
}
return ;
}