AtCoder Beginner Contest 122 D - We Like AGC （DP）

D - We Like AGC

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : <var> $400400$ </var> points

Problem Statement

You are given an integer <var> $NN$ </var>. Find the number of strings of length <var> $NN$ </var> that satisfy the following conditions, modulo <var> ${109+7109+7}^{9+7109+7}$ </var>:

The string does not contain characters other than A, C, G and T.
The string does not contain AGC as a substring.
The condition above cannot be violated by swapping two adjacent characters once.

Notes

A substring of a string <var> $TT$ </var> is a string obtained by removing zero or more characters from the beginning and the end of <var> $TT$ </var>.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and (the empty string), but not AC.

Constraints

<var> $3\leqN\leq1003\leqN\leq100$ </var>

Input

Input is given from Standard Input in the following format:

<var> $NN$ </var>

Output

Print the number of strings of length <var> $NN$ </var> that satisfy the following conditions, modulo <var> ${109+7109+7}^{9+7109+7}$ </var>.

Sample Input 1 Copy

Copy

Sample Output 1 Copy

Copy

There are <var> ${43=6443=64}^{3=6443=64}$ </var> strings of length <var> $33$ </var> that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is <var> $64-3=6164-3=61$ </var>.

Sample Input 2 Copy

Copy

Sample Output 2 Copy

Copy

Sample Input 3 Copy

Copy

Sample Output 3 Copy

Copy

388130742

Be sure to print the number of strings modulo <var> ${109+7109+7}^{9+7109+7}$ </var>.

题意：

给你一个数字N，N的范围是3~100

让你求出有多少种可能的字符串，使之只包括这四种字符 A, C, G and T.

并且字符串不含有“AGC”这个子串，并且仅交换一次相邻的字符也不含有“AGC”这个子串。

思路：

我们根据第一个样例就可以看出N=3的所有情况。

因为我们考虑的是DP的写法，先思考如何定义状态，

我们通过思考可以知道我们从N=3转到N=4的状态的时候，我们要考虑整个字符串的后3个字符才可以确定最后一位能不能加上我们在转移的字符，

那么我们不妨在定义状态的时候就把整个字符串的后3位字符都存下来。

所以我们定义状态如下：

DP[ len ][i] [ j ] [ k ] = 长度为len的字符串中，后三位字符串依次是ijk的字符串有多少种。

这里因为只有四种字母，我们不妨给四个字符进行用数码编号表示，以此来简化我们的程序编写；

我们按照字典序把{'A','C','G','T'}; 编为 0 1 2 3.

那么我们现在从N=4开始考虑，

我们知道以下几种情况是不能满足条件的

后三位是我们不能接上

*AG　　C

*AC　　G

*GA　　C

A*G　　C

AG*　　C

我们只需要在转移的时候，把这5种会产生不符合条件的字符串给删除掉（即不计入计数）

就可以顺利的推出答案了。

具体转移的细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
const ll mod = 1e9+7ll;
ll dp[110][5][5][5];
char c[6]={'A','C','G','T'};
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    // gbtb*/
    cin>>n;
    string temp="123";
    int num=0;
    // repd(i,0,3)
    // {
    //     temp[0]=c[i];
    //     repd(j,0,3)
    //     {
    //         temp[1]=c[j];
    //         repd(k,0,3)
    //         {
    //             temp[2]=c[k];
    //             cout<<num++<<" ";
    //             cout<<temp<<endl;
    //         }
    //     }
    // }
    // char c[6]={'A','C','G','T'};
    repd(i,0,3)
    {
        repd(j,0,3)
        {
            repd(k,0,3)
            {
                dp[3][i][j][k]=1;
            }
        }
    }
    dp[3][0][1][2]=0;
    dp[3][0][2][1]=0;
    dp[3][2][0][1]=0;
    ll cnt=0ll;
    repd(len,4,n)
    {
        repd(i,0,3)
        {
            repd(j,0,3)
            {
                repd(k,0,3)
                {
                    cnt=0ll;

                    repd(ii,0,3)
                    {
                        repd(jj,0,3)
                        {
                            repd(kk,0,3)
                            {
                                //{'A','C','G','T'};
                                if(jj==i&&kk==j)
                                {
                                    if(k==1&&kk==2&&jj==0)
                                    {

                                    }else if(k==1&&kk==0&&jj==2)
                                    {

                                    }else if(k==2&&kk==1&&jj==0)
                                    {

                                    }else if(k==1&&kk==2&&ii==0)
                                    {

                                    }else if(k==1&&jj==2&&ii==0)
                                    {

                                    }else
                                    {
                                        cnt+=dp[len-1][ii][jj][kk];
                                        cnt=(cnt+mod)%mod;
                                    }
                                }


                            }
                        }
                    }
                    cnt=(cnt+mod)%mod;
                    dp[len][i][j][k]=cnt;
//                    printf("%d %d %d %lld\n",i,j,k,cnt);
                }
            }
        }
    }
    ll ans=0ll;
    repd(i,0,3)
    {
        repd(j,0,3)
        {
            repd(k,0,3)
            {
                ans+=dp[n][i][j][k];
                ans=(ans+mod)%mod;
            }

        }
    }
    cout<<ans<<endl;
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}