题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=2065
汗，这题没想到，看了网上的解答。。。直接COPY过来把。
问题分析 Problem Analyse 递推题
Algorithm Analyse 比起以前做过的递推题，这一题算比较麻烦的了(当然，原因是我没有想到好的方法，如果你有更方便的方法，欢迎提供大家一起学习)。 如果没有任何条件限制，A、B、C、D组成长度为n的字符串，其个数应该为:4n。
因为有了A、C需要出现偶数次的要求，就出现合法和不合法的不同分组。 在不合法的组里，又有 1.A出现奇数次、C出现偶数次； 2.C出现奇数次、A出现偶数次； 3.A出现奇数次、C出现奇数次； 三种情况。
我们用数组 f[n][0]保存长度为n，合法的字符串的个数。 f[n][1]保存长度为n，仅A出现奇数次的字符串的个数。 f[n][2]保存长度为n，仅C出现奇数次的字符串的个数。 f[n][3]保存长度为n，A、C出现奇数次的字符串的个数。
f[n][0] 长度为n-1的合法字符串在末尾加上一个B或者D，都可以变成长度为n的合法字符串。 长度为n-1的仅A出现奇数次的字符串再在末尾加上一个A，也可以变成合法字符串。 长度为n-1的仅C出现奇数次的字符串再在末尾加上一个C，也可以变成合法字符串。 所以，f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2];
f[n][1] 长度为n-1的合法字符串在末尾加上A，都可以变成长度为n的仅A出现奇数次的字符串。 长度为n-1的仅A出现奇数次的字符串再在末尾加上一个B或者D，也可以变成仅A出现奇数次的字符串。 长度为n-1的A、C出现奇数次的字符串再在末尾加上一个C，也可以变成仅A出现奇数次的字符串。 所以，f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3];
f[n][2] 长度为n-1的合法字符串在末尾加上C，都可以变成长度为n的仅C出现奇数次的字符串。 长度为n-1的仅C出现奇数次的字符串再在末尾加上一个B或者D，也可以变成仅C出现奇数次的字符串。 长度为n-1的A、C出现奇数次的字符串再在末尾加上一个A，也可以变成仅C出现奇数次的字符串。 所以，f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3];
f[n][3] 长度为n-1的A、C出现奇数次的字符串在末尾加上一B或者D，都可以变成长度为n的A、C出现奇数次的字符串。 长度为n-1的仅A出现奇数次的字符串再在末尾加上一个C，也可以变成A、C出现奇数次的字符串。 长度为n-1的仅C出现奇数次的字符串再在末尾加上一个A，也可以变成A、C出现奇数次的字符串。 所以，f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2];
综上所述，我们得到: f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2]; ① f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3]; ② f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3]; ③ f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2]; ④
f[1][0] = 2 f[1][1] = 1 f[1][2] = 1 f[1][3] = 0
发现f[1][1]与f[1][2]初始状态相同，而且以后迭代方程也相同，所以f[n][1] = f[n][2] 又有f[n][0] + f[n][3] = f[n][1] + f[n][2] ∵f[n][0] + f[n][1] + f[n][2] + f[n][3] = 4n ∴f[n][0] + f[n][3] = f[n][1] + f[n][2] = 2 × 4n-1 ∴f[n-1][1] + f[n-1][2] = 2 × 4n-2 ∴f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2] = 2 × f[n-1][0] + 2 × 4n-2
我们得到: f[n][0] = 2 × f[n-1][0] + 22n-3 f[n-1][0] = 2 × f[n-2][0] + 22n-5 ┋ f[n-m][0] = 2 × f[n-m-1][0] + 22n-2m-3 ┋ f[2][0] = 2 × f[1][0] + 21 f[1][0] = 2
开始一层层往下迭代: f[n][0] = 2 × f[n-1][0] + 22n-3 = 22 × f[n-2][0] + 22n-4 + 22n-3 ┋ = 2m × f[n-m][0] + 22(n-m)-1+m-1 + ... + 22n-3 = 2n-1 × f[1][0] + 2n-1 + 2n +... + 22n-3 f[1][0] = 2;
∴f[n][0] = 2n + 2n-1 + 2n +... + 22n-3 = 22n-2 + 2n-1
编码建议 Programing 公式得到了:f(n) = 22n-2 + 2n-1 但就这样直接编程那是不可能实现的，因为n的范围1≤N<264 怎么的范围，是不能求出f(n)的。所以还得找其他规律。 因为题目只要求输出最后2位数，我们依次输出2的n的最后两位看看... 20 -> 1 21 -> 2 22 -> 4 23 -> 8 24 -> 16 25 -> 32 26 -> 64 27 -> 28 28 -> 56 29 -> 12 210 -> 24 211 -> 48 212 -> 96 213 -> 92 214 -> 84 215 -> 68 216 -> 36 217 -> 72 218 -> 44 219 -> 88 220 -> 76 221 -> 52 222 -> 4 到了222时，末尾2位又变成4，与22一样，这时候就进入了一个循环了(每20个一次循环)。 所以，结果只能是这22个中的一个。只有n=0 和 n=1是需要特殊考虑的。其他n就等于2(n-2) % 20 + 2的值了。
#include
int main(void)
{
__int64 n;
int c, t;
int d[] = {
4, 8,16,32,64,28,56,12,24,48,
96,92,84,68,36,72,44,88,76,52
};
while (scanf("%d", &t;), t)
{
for (c = 1; c <= t; c++)
{
scanf("%I64d", &n;);
printf("Case %d: %d\n", c, n<3?(n<2?2:6):(d[(2*n-4)%20]+d[(n-3)%20])%100);
}
putchar('\n');
}
return 0;
}