摘要：
"红色病毒"问题 整数N（1<；=N<；c；16MAT（）17{18r=c=0；sizeof（d））；26ans.r=m1。r27安。c=m2.c；j++）31{32if（m1。d[i][j]）33｛34对于（intk＝0；intmod）45｛46MATans＝MAT（）；47对于（int i＝0；53而（n）54｛55if（n&；＝EOF&；=T；
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4742 Accepted Submission(s): 1985
Problem Description
医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
Input
每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.
Output
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.
Sample Input
4 1 4 20 11 3 14 24 6 0
Sample Output
Case 1: 2 Case 2: 72 Case 3: 32 Case 4: 0 Case 1: 56 Case 2: 72 Case 3: 56
Author
Rabbit
转移方程：
f[i][1] = 2 * f[i-1][1] + f[i-1][2] + f[i-1][3];
f[i][2] = f[i-1][1] + 2 * f[i-1][2] + f[i-1][4];
f[i][3] = f[i-1][1] + 2 * f[i-1][3] + f[i-1][4];
f[i][4] = f[i-1][2] + f[i-1][3] + 2 * f[i-1][4];
用矩阵快速幂优化的DP，关系矩阵：
2 1 1 0
1 2 0 1
1 0 2 1
0 1 1 2
代码：
![[HDOJ2065]"红色病毒"问题第1张](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![[HDOJ2065]"红色病毒"问题第2张](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <cstdio> 5 #include <cmath> 6 7 using namespace std; 8 9 #define MOD 100 10 #define MAXN 5 11 12 typedef struct MAT 13 { 14 __int64 d[MAXN][MAXN]; 15 int r, c; 16 MAT() 17 { 18 r = c = 0; 19 memset(d, 0, sizeof(d)); 20 } 21 }MAT; 22 23 MAT mul(MAT m1, MAT m2, int mod) 24 { 25 MAT ans = MAT(); 26 ans.r = m1.r; 27 ans.c = m2.c; 28 for(int i = 0; i < m1.r; i++) 29 { 30 for(int j = 0; j < m2.r; j++) 31 { 32 if(m1.d[i][j]) 33 { 34 for(int k = 0; k < m2.c; k++) 35 { 36 ans.d[i][k] = (ans.d[i][k] + m1.d[i][j] * m2.d[j][k]) % mod; 37 } 38 } 39 } 40 } 41 return ans; 42 } 43 44 MAT quickmul(MAT m, __int64 n, int mod) 45 { 46 MAT ans = MAT(); 47 for(int i = 0; i < m.r; i++) 48 { 49 ans.d[i][i] = 1; 50 } 51 ans.r = m.r; 52 ans.c = m.c; 53 while(n) 54 { 55 if(n & 1) 56 { 57 ans = mul(m, ans, mod); 58 } 59 m = mul(m, m, mod); 60 n >>= 1; 61 } 62 return ans; 63 } 64 65 int main() { 66 int T; 67 while(scanf("%d", &T) != EOF && T) { 68 __int64 n; 69 for(int i = 1; i <= T; i++) { 70 scanf("%I64d", &n); 71 MAT A = MAT(); 72 A.r = 4, A.c = 4; 73 A.d[0][0] = 2; A.d[0][1] = 1; A.d[0][2] = 1; A.d[0][3] = 0; 74 A.d[1][0] = 1; A.d[1][1] = 2; A.d[1][2] = 0; A.d[1][3] = 1; 75 A.d[2][0] = 1; A.d[2][1] = 0; A.d[2][2] = 2; A.d[2][3] = 1; 76 A.d[3][0] = 0; A.d[3][1] = 1; A.d[3][2] = 1; A.d[3][3] = 2; 77 A = quickmul(A, n, MOD); 78 printf("Case %d: %d ", i, A.d[0][0]); 79 } 80 printf(" "); 81 } 82 }