传送门：>Here<
题意：现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
解题思路
先解普通递推，然后矩阵乘法优化即可。一维好像没有什么好的解法……
$f[i][0]$表示长度为$i$的合法字符串的数量，$f[i][1]$表示仅A的个数为奇数的字符串数量，$f[i][2]$表示仅C的个数为奇数的字符串数量，$f[i][3]$表示A, C个数都为奇数的字符串数量
因此可得递推方程$$f[i][0] = f[i-1][0]*2 + f[i-1][1] + f[i-1][2]$$
这个方程的意义在于：考虑第$i$位相比已知的前$i-1$位加入什么。如果加入B或D，那么前面的必须合法。如果加入A或C，那么相应的前面的A或C的数量应当为奇数
问题一：为什么只考虑最后一位，当前这一位理论上不是插入前面的i-1个位置都可以吗？然而在这里是要考虑重复的，例如串$\{ AAB\}$，在最后一位或是倒数第二位插入B都将会得到$\{ AABB \}$。那前面的几位呢？如果在第二位插入，就变成了$\{ ABAB \}$，而这等同于在$\{ ABA \}$的后面插入了$B$，将归属于另一种情况。如果讨论了它，就会与别的情况有重复。总结起来，最后得到的串是不分插入位置的，不同的插入顺序得到的是同一个串。换句话说也就是所有B都是一样的。
问题二：为什么转移$f[i][0]$时不加上$f[i-2][3]$呢？试想倘若$f[i-2][3]$的末尾加上一个A，那么就会变成$f[i-1][2]$；加上C就会变成$f[i-1][1]$。而这两类都讨论过了，再讨论就重复了。
其他的几个的转移方法类似，最后我们得到转移方程组：$$\left\{\begin{matrix}f[i][0] = f[i-1][0]*2+f[i-1][1]+f[i-1][2]\\ f[i][1] = f[i-1][1]*2+f[i-1][0]+f[i-1][3]\\ f[i][2] = f[i-1][2]*2+f[i-1][0]+f[i-1][3]\\ f[i][3] = f[i-1][3]*2+f[i-1][1]+f[i-1][2]\\ \end{matrix}\right.$$
因此可以推得矩阵$$ \begin{bmatrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 1 & 1 & 2\end{bmatrix} $$
Code
不知道为什么反正要开longlong
/*By DennyQi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
#define int long long
const int MAXN = ;
const int MAXM = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) + (x << ) + c - '', c = getchar(); return x * w;
}
int T,N;
int a[][],b[][],ans[][];
inline void Matrix_KSM(int y){
while(y > ){
if(y & ){
for(int i = ; i <= ; ++i){
for(int j = ; j <= ; ++j){
b[i][j] = ;
for(int k = ; k <= ; ++k){
b[i][j] = (b[i][j] + ans[i][k] * a[k][j]) % ;
}
}
}
for(int i = ; i <= ; ++i){
for(int j = ; j <= ; ++j){
ans[i][j] = b[i][j];
}
}
}
for(int i = ; i <= ; ++i){
for(int j = ; j <= ; ++j){
b[i][j] = ;
for(int k = ; k <= ; ++k){
b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % ;
}
}
}
for(int i = ; i <= ; ++i){
for(int j = ; j <= ; ++j){
a[i][j] = b[i][j];
}
}
y /= ;
}
}
inline void Solve(){
memset(ans,,sizeof(ans));
memset(a,,sizeof(a));
for(int i = ; i <= ; ++i) ans[i][i] = ;
a[][] = , a[][] = , a[][] = , a[][] = ;
a[][] = , a[][] = , a[][] = , a[][] = ;
a[][] = , a[][] = , a[][] = , a[][] = ;
a[][] = , a[][] = , a[][] = , a[][] = ;
Matrix_KSM(N-);
printf("%lld\n", (*ans[][]% + ans[][]% + ans[][]) % );
}
#undef int
int main(){
#define int long long
for(;;){
T = r;
if(!T) break;
for(int i = ; i <= T; ++i){
N = r;
printf("Case %lld: ",i);
Solve();
}
puts("");
}
return ;
}