由于本题原型是HDU2065，解题方法以及思路相同，故以HDU2065为例整理题解。
Problem Description
医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。现在有一长度为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
解题思路1：矩阵快速幂
我们将所有可能的情况按照合法与不合法分为两类：
合法类：即A和C出现偶数次或不出现
非法类：即A和C出现奇数次
我们可以用用数组表示：
F[n][0]表示长度为n的合法字符串的个数。
F[n][1]表示长度为n的，A出现奇数次，C出现偶数次（或不出现）的字符串个数。
F[n][2]表示长度为n的，C出现奇数次，A出现偶数次（或不出现）的字符串个数。
F[n][3]表示长度为n的，A和C都出现奇数次的字符串个数。
可以发现F[n][0]是合法类，剩下三个是非法类。我们划分这四个数组是按照A和C的个数是奇还是偶来划分的，这样划分的好处是便于状态转移。
很显然，合法串是最终所求的答案。而合法串可以由非法串经过转移得到，同理非法串也可以通过合法串状态转移得到，于是我们就可以通过状态转移方程来计算答案。具体的，状态转移方程为：
F[i][0]=2∗F[i−1][0]+F[i−1][1]+F[i−1][2]F[i][0] = 2 * F[i-1][0] + F[i-1][1] + F[i-1][2]F[i][0]=2∗F[i−1][0]+F[i−1][1]+F[i−1][2]
F[i][1]=2∗F[i−1][1]+F[i−1][0]+F[i−1][3]F[i][1] = 2 * F[i-1][1] + F[i-1][0] + F[i-1][3]F[i][1]=2∗F[i−1][1]+F[i−1][0]+F[i−1][3]
F[i][2]=2∗F[i−1][2]+F[i−1][0]+F[i−1][3]F[i][2] = 2 * F[i-1][2] + F[i-1][0] + F[i-1][3]F[i][2]=2∗F[i−1][2]+F[i−1][0]+F[i−1][3]
F[i][3]=2∗F[i−1][3]+F[i−1][1]+F[i−1][2]F[i][3] = 2 * F[i-1][3] + F[i-1][1] + F[i-1][2]F[i][3]=2∗F[i−1][3]+F[i−1][1]+F[i−1][2]
而初始状态：
F[1][0]=2F[1][0] = 2F[1][0]=2
F[1][1]=1F[1][1] = 1F[1][1]=1
F[1][2]=1F[1][2] = 1F[1][2]=1
F[1][3]=0F[1][3] = 0F[1][3]=0
已知初始状态和状态转移方程了，我们有两个选择，一个是用一层循环O(N)解决；另一种是用矩阵快速幂加速链乘，时间复杂度是O(log N)。至于如何构造转移矩阵，以及矩阵如何快速幂请不再讲解。
当然这还可以优化，首先可以发现的是F[n][1]和F[n][2]的初始状态一样，转移方程也一样，因此可以将F[n][1] = F[n][2]合并成一个。然后由于长度为n的字符串一共有4n4^n4n种情况，因此：
F[n][0]+F[n][1]+F[n][2]+F[n][3]=4nF[n][0] + F[n][1] + F[n][2] + F[n][3] = 4^nF[n][0]+F[n][1]+F[n][2]+F[n][3]=4n。
又通过状态转移方程以及F[n][1] = F[n][2]这个关系可得：
F[n][0]+F[n][3]=F[n][1]+F[n][2]F[n][0] + F[n][3] = F[n][1] + F[n][2]F[n][0]+F[n][3]=F[n][1]+F[n][2]
由上述2个式子可得：
F[n][0]+F[n][3]=F[n][1]+F[n][2]=2∗4n−1F[n][0] + F[n][3] = F[n][1] + F[n][2] = 2 * 4^{n-1}F[n][0]+F[n][3]=F[n][1]+F[n][2]=2∗4n−1
于是：
F[n][0]=2∗4n−2+2∗F[n−1][0]F[n][0] = 2 * 4^{n-2} + 2 * F[n-1][0]F[n][0]=2∗4n−2+2∗F[n−1][0]
经过迭代后得：
F[n][0]=4n−1+2n−1F[n][0] = 4^{n-1} + 2^{n-1}F[n][0]=4n−1+2n−1
由于读入的n可能是10后面有100000个0，所以需要用字符串读入，再利用费马小定理：
ap−1=1(modp)a^{p-1} = 1(mod p)ap−1=1(modp)，可以得知，我们可以将ana^nan拆分为若干个ap−1a^{p-1}ap−1以及一个aka^kak相乘的形式，即an=a(p−1)∗m∗aka^n = a^{(p-1)*m} * a^kan=a(p−1)∗m∗ak而ap−1a^{p-1}ap−1无论来几个都是1，就算乘很多个也无所谓，所以可以像代码中给出的方法一样将字符串化为一个int范围的整数。
附录
代码示例1：矩阵快速幂
//此代码为SARS病毒代码#include<cstdio>#include<string>#include<iostream>using namespace std;const int M = 1e9+7;typedef long long ll;ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%M;a = a*a%M;b >>= 1;}return res;}ll solve(string x){//将字符串转化为可计算的int整数ll M1 = M-1;ll k2 = x[0]-'0';ll k1;for(int i = 1;x[i];i++) k2 = (k2*10+x[i]-'0')%M1;k1 = (2*k2%M1-2)%M1;k2 = (k2-1)%M1;long long ans = qpow(2,k1)+qpow(2,k2);return ans%M;}int main(){string n;while(cin >> n && n != "0"){printf("%lld\n",solve(n));}return 0;}
如果觉得《SARS病毒》对你有帮助，请点赞、收藏，并留下你的观点哦！
