AtCoder Beginner Contest 122 D

D - We Like AGC
Time Limit: 2 sec/Memory Limit: 1024 MB
Score : 400400 points

Problem Statement

You are given an integer NN. Find the number of strings of length NN that satisfy the following conditions, modulo 109+7109+7:

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 TT is a string obtained by removing zero or more characters from the beginning and the end of TT.
For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and

 (the empty string), but not AC .  
       
     
     Constraints 
      
       $3\leqN\leq1003\leqN\leq100$  
      
     
     
     
      
      Input 
      Input is given from Standard Input in the following format: 
        $NN$ 
  
      
      
      Output 
      Print the number of strings of length  $NN$  that satisfy the following conditions, modulo  ${109+7109+7}^{9+7109+7}$ . 
      
     
     
     
     Sample Input 1 Copy 
      
      Copy 
      
      3
  
     
     
     Sample Output 1 Copy 
      
      Copy 
      
      61
  
     There are  ${43=6443=64}^{3=6443=64}$  strings of length  $33$  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 64−3=6164−3=61. 
Sample Input 2 Copy
  
Copy 4
  
Sample Output 2 Copy
  
Copy 230
  
Sample Input 3 Copy
  
Copy 100
  
Sample Output 3 Copy
  
Copy 388130742
  
Be sure to print the number of strings modulo 109+7109+7. 
  
제목:
숫자 하나 드릴게요. N의 범위는 3~100입니다.
이 네 가지 문자만 포함할 수 있는 가능한 문자열을 구해 보세요. A, C, G and T.
또한 문자열에는 "AGC"라는 하위 문자열이 없으며 인접한 문자를 한 번만 교환해도 "AGC"라는 하위 문자열이 없습니다.
  
아이디어:
우리는 첫 번째 견본에 근거하여 N=3의 모든 상황을 볼 수 있다.
우리가 생각하는 것은 DP의 문법이기 때문에 상태를 어떻게 정의하는지 먼저 생각하고
우리가 N=3에서 N=4로 넘어갈 때 전체 문자열의 뒷부분 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 
우리는 이동할 때 이 다섯 가지 조건에 부합되지 않는 문자열을 삭제할 수 있다. (즉 계수를 계산하지 않는다)
순조롭게 답을 내놓을 수 있을 거예요.
  
구체적인 이동의 세부 사항은 코드를 보십시오:#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d
",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair
#define pll pair
#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<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<//             cout<//         }
    //     }
    // }
    // 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
",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<endl;
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    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';
        }
    }
}
  
   
    
     
     :https://www.cnblogs.com/qieqiemin/p/10692577.html

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

AtCoder Beginner Contest 122 D - We Like AGC (DP)

Problem Statement

Notes

Constraints

Input

Output

Sample Input 1 Copy

Sample Output 1 Copy

Sample Input 2 Copy

Sample Output 2 Copy

Sample Input 3 Copy

Sample Output 3 Copy

좋은 웹페이지 즐겨찾기