【HDOJ】2065 “红色病毒”问题

全栈程序员-用户IM • 2021年8月29日上午7:00 • 未分类

刚开始看这道题目的时候，完全没看出来是递推。看了网上大牛的分析。立刻就明白了。
其实无论字符串长度为多少，都可以将该长度下的组合分成四种情况S1（A偶数C偶数）、S2（A偶数C奇数）、S3（A奇数C偶数）、S4（A奇数C奇数）。因此，可以由n-1长度情况下的各种情况数目推导出n长度下的数目。
f_n(S1) = 2*f_n-1(S1) + f_n-1(S2) + f_n-1(S3)，同理可推导其它状态的数目
f_n(S2) = 2*f_n-1(S2) + f_n-1(S1) + f_n-1(S4)
f_n(S3) = 2*f_n-1(S3) + f_n-1(S1) + f_n-1(S4)
f_n(S4) = 2*f_n-1(S4) + f_n-1(S2) + f_n-1(S3)
由以上公式可以推导出 f_n(S1) + f_n(S4) = f_n(S2) + f_n(S3) = 4^n / 2 = 2*4^(n-1)
又因为f₀(S1) = 2, f₀(S2) = 1, f₀(S3) = 1, f₀(S4) = 0
f₀(S2) = f₀(S3)，并且两式的推导公式相同，因此有f_n(S2) = f_n(S3) = 4^(n-1) = 2^(2n-2)
将其代入S1的推导式，并且递推可得f_n(S1) = 2^(n-1) + 2^(2n-2)
下面就是推导规律，发现2的幂%100的周期为1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,
然后注意讨论长度为1、2的情况，可求解。

 1 #include <stdio.h>
 2 
 3 #define PAT2NUM 20
 4 #define PAT4NUM 10
 5 
 6 int pattern[] = {
   1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52};
 7 
 8 void find(int base) {
 9     int i, j, flg, n;
10 
11     pattern[0] = 1;
12     printf("1 ");
13     n = 1;
14     for (i=1; i<50; ++i) {
15         pattern[i] = pattern[i-1]*base%100;
16         flg = 0;
17         for (j=0; j<i; ++j)
18             if (pattern[i] == pattern[j]) {
19                 flg = 1;
20                 break;
21             }
22         if (flg)
23             break;
24         ++n;
25         printf("%d ", pattern[i]);
26     }
27 }
28 
29 int main() {
30     int case_n;
31     __int64 n;
32     int i, a, b;
33 
34     while (scanf("%d", &case_n)!=EOF && case_n) {
35         for (i=1; i<=case_n; ++i) {
36             scanf("%I64d", &n);
37             printf("Case %d: ", i);
38             if (n == 1) {
39                 printf("2\n");
40                 continue;
41             }
42             if (n == 2) {
43                 printf("6\n");
44                 continue;
45             }
46             a = pattern[(n-1-2)%PAT2NUM+2];
47             b = pattern[(2*n-2-2)%PAT2NUM+2];
48             printf("%d\n", (a+b)%100);
49         }
50         printf("\n");
51     }
52 
53     return 0;
54 }