题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=2065
递推类题目， 可以考虑用数学方法来做， 但是明显也可以有递推思维来理解。
递推的话基本就是状态转移了， 如何找状态是递推的关键。
我们把这个分为四个状态
A 出现次数的奇偶和B出现状态的奇偶，我们可以构造出四个状态:
A B
第一个状态 ： 偶 偶 0
第二个状态 ： 偶 奇 1
第三个状态 ： 奇 偶 2
第四个状态 ： 奇 奇 3
我们由这些状态进行转移 设定数组 dp[第k个状态][字符串的长度n]
进行状态转移：
偶偶 <- 偶 奇 + 偶偶 + 奇偶
依次类推........
dp[0][i] = (dp[0][i-1]*2 + dp[1][i-1] + dp[2][i-1]);
dp[1][i] = (dp[1][i-1]*2 + dp[0][i-1] + dp[3][i-1]);
dp[2][i] = (dp[2][i-1]*2 + dp[0][i-1] + dp[3][i-1]) ;
dp[3][i] = (dp[3][i-1]*2 + dp[1][i-1] + dp[2][i-1]) ;
得到四个状态转移方程
dp[0][i-1]*2 是因为 无论是 第i个 字符是A 或者是 B 对下一个状态都 无影响。
他们给我们的数字是非常大的， 因此我们要去找循环节。
循环节是20个数字 一个循环， 但是前两个数字不在循环内部 要特殊处理
下面是代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
using namespace std;
const int maxn = ;
const long long INF = 0xfffffff; int main()
{
int dp[][maxn] ={};
int P[maxn];
dp[][] = ;
for(int i=; i<=; i++)
{
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
dp[][i] = (dp[][i-]* + dp[][i-] + dp[][i-]) % ;
// cout << dp[0][i] << endl;
if(i > )
P[i-] =dp[][i];
}
int T, cas; long long n;
while(cin >> T, T)
{
cas = ;
while(T--)
{
cin >> n;
cout << "Case "<<cas++<<": "; if(n < )
cout<<dp[][n]<<endl;
else
cout<<P[(n-)%]<<endl; if(!T)
cout << endl;
}
}
return ;
}