吉首大学校赛 A SARS病毒（欧拉降幂）

青旅半醒 2021-12-11 01:03 222阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/925/A][https_ac.nowcoder.com_acm_contest_925_A]  
来源：牛客网

## 题目描述 ##

目前，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 取模的结果即可。

## 输入描述: ##

多组输入（不超过10组）,每行一个整数n:0 < n < 1010510105

## 输出描述: ##

对于输入文件中的每一个 n，输出满足条件的字符串的个数对 10^9 +7 取模的结果。

示例1

## 输入 ##

复制

1
    2
    100

## 输出 ##

复制

2
    6
    113046907
    
    
    
    题意：满足题目的序列个数有多少个
    思路：我们计算以每个字母结尾的个数有多少个，我们可以分两类（（T，G）,(A,C)），T，G字母结尾的我们每一位都会翻两倍，A，C字母每隔俩个翻一倍，但是其实我们A,C结尾的我们可以放T,G，T,G结尾也一样，所以
    假设  AC[]代表 AC结尾      TG[]代表 TG结尾  
    AC[n]  =   AC[n-2]*2 +  TG[n-2]*2;
    TG[n]  = 　AC[n-1]*2 + 　TG[n-1]*2; 
    最后我们可以化简出式子等于  （2^(n-1)）*(2^(n-1)+1)
    因为我们的n特别大，这里我就用上了欧拉降幂
    (a^n)%mod = (a^(b%phi(mod)+mod))%mod

#include<bits/stdc++.h>
    #define maxn 1000005
    #define mod 1000000007
    using namespace std;
    typedef long long ll;
    char str[maxn];
    ll big_number(char s[],ll m){
        ll num=0;
        for(int i=0;s[i]!='\0';i++){
            num=num*10+(s[i]-'0');
            num%=m;
        }
        return num;
    }
    ll quick_pow(ll x,ll y){
        ll ans=1;
        while(y){
            if(y&1) ans=(ans*x)%mod;
            x=(x*x)%mod;
            y=y/2;
        }
        return ans;
    } 
    int main(){
        while(cin>>str)
        {
            int flag=0;
            if((str[strlen(str)-1]-'0')%2) flag=1;
            ll num=big_number(str,mod-1); 
            //cout<<"num:"<<num<<endl;
            ll da=quick_pow(2,num-1+mod-1);
            //if(flag%2) da=(da*2)%mod;
            cout<<(da*(da+1))%mod<<"\n";
        }
    }

转载于:https://www.cnblogs.com/Lis-/p/11072032.html

[https_ac.nowcoder.com_acm_contest_925_A]: https://ac.nowcoder.com/acm/contest/925/A