链接：https://ac.nowcoder.com/acm/problem/50035
来源：牛客网

题目：

目前，SARS 病毒的研究在世界范围内进行，经科学家研究发现，该病毒及其变种的 DNA 的一条单链中，胞嘧啶、腺嘧啶均是成对出现的。这虽然是一个重大发现，但还不是该病毒的最主要特征，因为这个特征实在太弱了。

为了进一步搞清楚该病毒的特征，CN 疾病控制中心和阿里巴巴集团合作，用科技的力量和程序的思维来解决这个难题。现阿里巴巴特委派你成为 CN 疾病控制中心的 SARS 高级研究员，去研究在这个特征下，可能成为 SARS 病毒的 DNA 序列的个数。更精确地说，你需要统计所有满足下列条件的长度为 n 的字符串的个数:

1、字符串仅由 A、T、C、G 组成
2、A 出现偶数次(也可以不出现)
3、C 出现偶数次(也可以不出现)
当 n=2 时，所有满足条件的字符串有如下 6个:

TT，TG，GT，GG，AA，CC。

注： 有多组测试数据，由于这个数可能非常庞大，你只需给出对 10^9+7 取模的结果即可。

分析：

看他给的数据每个数据最多可以到264，而且还有多组数据，说明log(n)的算法肯定是不行了，也就是说不能从1扫描到n，所以考虑直接通过n求出最后的答案。
同样的，我们尝试找一下规律，
当n = 1时，有两种情况，B 和 D
当n = 2时，有六种情况，BB , BD , DB , DD , AA 和 CC
实际上这里发现B和D应该是同一种东西(但AA和CC不应该视作同一种东西，它能够出现BDBD的情况，也能出现ACAC的情况)，
有n个位置能放的话，那么就没有A和C的情况下，就有2n个方案，因为A和C的总和必须是偶数，然后我想到的是从n中拿出偶数个放上A和C，剩下的放上B和D。我尝试写出写出了以下式子，
当n = 4时，ans = 24 + C42 * 2 * 22 + C44 * 23 * 20
在n = 4 的情况下，我就把情况分成了三种，

没有A和C的情况，只有B和D，那么就应该是24种
有两个A和C，那么只能是AA或CC两种，剩下的两个也有22种排列，所以那就是C42 * 2 * 22种情况
都是A和C，那么就可以组合出AACC , ACAC , CACA, CCAA，AAAA , CCCC , ACCA , CAAC八种情况，实际上就是2n-1种情况（这里分析见文末）
再把上述几种情况加起来就得到了 ans = 72 的结论，发现和题目给的是一样的，然后我又算了一个当n = 6的情况，同样和题目给的条件符合。抽象出公式，
ans = 2n + Cn2 * 21 * 2n-2 + Cn4 * 23 * 2n-4 + … + Cnn * 2n-1 * 2n-n
然后发现算式能够化简成为，
ans = 2n + 2n-1 * (Cn2 + Cn4 + … + Cnn-2 + Cnn)
后面的组合数还能够再次化简，
ans = 2n + 2n-1 * (2n-1 - 1)
所以，
ans = 2n + 22n-2 - 2n-1
ans = 4n-1 + 2n-1
最后计算出ans对1e9+7取模运算即可
————————————————
原文链接：https://blog.csdn.net/qq_44754132/article/details/104453349

AC代码：