刚开始看这道题目的时候，完全没看出来是递推。看了网上大牛的分析。立刻就明白了。
其实无论字符串长度为多少，都可以将该长度下的组合分成四种情况S1（A偶数C偶数）、S2（A偶数C奇数）、S3（A奇数C偶数）、S4（A奇数C奇数）。因此，可以由n-1长度情况下的各种情况数目推导出n长度下的数目。
fn(S1) = 2*fn-1(S1) + fn-1(S2) + fn-1(S3)，同理可推导其它状态的数目
fn(S2) = 2*fn-1(S2) + fn-1(S1) + fn-1(S4)
fn(S3) = 2*fn-1(S3) + fn-1(S1) + fn-1(S4)
fn(S4) = 2*fn-1(S4) + fn-1(S2) + fn-1(S3)
由以上公式可以推导出 fn(S1) + fn(S4) = fn(S2) + fn(S3) = 4^n / 2 = 2*4^(n-1)
又因为f0(S1) = 2, f0(S2) = 1, f0(S3) = 1, f0(S4) = 0
f0(S2) = f0(S3)，并且两式的推导公式相同，因此有fn(S2) = fn(S3) = 4^(n-1) = 2^(2n-2)
将其代入S1的推导式，并且递推可得fn(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 }
转载于:https://www.cnblogs.com/bombe1013/p/3651062.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109857.html原文链接：https://javaforall.net
