题目

目前，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的最后两位，我们知道ab末尾两位是循环的，这里列出循环节，2n = [1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,4,8,16,32,64,28,56,12]，后面都是循环前面的内容，因此2n-1末尾两个数字可以在O(1)的时间求得。同理，4n = [1,4,16,64,56,24,96,84,36,44,76,4,16,64,56,24]，4n的数值也可以在O(1)求得。
所以在这里，能够直接通过题目给的数字n求得答案，时空复杂度都是O(1)。我当时怎么就没想到快速幂，快速幂似乎也挺方便的喂
————————————————
原文链接：https://blog.csdn.net/qq_44754132/article/details/104453349

AC代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int MOD=1e9+7;
const int MOD1=1e9+6;

char s[100005];

ll quick(ll a,ll b){
    a%=MOD;
    ll ans=1;
    while(b){
        if(b&1) //判断指数二进制位的每一位，如果是1就参与运算
            ans=(ans*a)%MOD;
        b>>=1; //右移一位，相当于每次除2
        a=(a*a)%MOD; //不断加倍
    }
    return ans;
}

int main(){
    while(~scanf("%s",s)){
        ll tmp=0;
        for(int i=0;i<strlen(s);++i)
            tmp=(tmp*10+s[i]-'0')%MOD1; //不知道为什么非得模1e9+6,否则会出错
#if 0
        if(tmp>0) --tmp;
        else tmp=MOD-1;
        tmp=quick(2,tmp);
        printf("%lld\n",tmp*(tmp+1)%MOD);
#endif
        ll temp1=quick(2,tmp-1);
        ll temp2=quick(4,tmp-1);
        printf("%lld\n",(temp1+temp2)%MOD);
    }
    return 0;
}