Problem:


Score : 400 points

Problem Statement

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+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 T is a string obtained by removing zero or more characters from the beginning and the end of T.

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

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Sample Input 1

3

Sample Output 1

61

There are 4^3 = 64 strings of length 3 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 = 61.

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

Be sure to print the number of strings modulo 10^9+7.



Sample input:
3


Sample output:
61

Submission status: Accepted

Solution code:
n=int(input())

def swap(a,b):
    c=[i for i in a]
    c[b],c[b+1]=c[b+1],c[b]
    return "".join(c)

def ok(a):
    if "AGC" in swap(a,0) or "AGC" in swap(a,1) or "AGC" in swap(a,2) or "AGC" in a:
        return False
    return True

if n==1:
    print(4)
elif n==2:
    print(16)
else:
    a={}
    for i in "ACGT":
        for j in "ACGT":
            for k in "ACGT":
                if not i+j+k in ["AGC","ACG","GAC"]:
                    a[i+j+k]=1
    for q in range(n-3):
        b={}
        for i in a:
            for j in "ACGT":
                if ok(i+j):
                    w=i[1:]+j
                    if w in b:
                        b[w]+=a[i]
                    else:
                        b[w]=a[i]
        a=dict(b)
    al=0
    for i in a:
        al+=a[i]
    print(al%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
R=range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]+=dp[i-1][j][k][l]
print(sum(c for a in dp[n]for b in a for c in b)%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
M,R=10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Submission status: Accepted

Solution code:
n=int(input())
A,C,G,T,M,R=0,1,2,3,10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Submission status: Accepted

Solution code:
from collections import Counter

mod = 1000000007
ng3 = ("AGC", "ACG", "GAC")
ng4 = ("AAGC", "ACGC", "AGGC", "ATGC", "AGAC", "AGCC", "AGGC", "AGTC")


def isok(s):
    if s[-3:] in ng3:
        return False
    if s[-4:] in ng4:
        return False
    return True


N = int(input())
dp = [Counter() for _ in range(N + 1)]
dp[0] = {"": 1}
for n in range(1, N + 1):
    for s, v in dp[n-1].items():
        for c in "ACGT":
            if isok(s + c):
                dp[n][s[-3:] + c] += v
print(sum(dp[N].values()) % mod)

Submission status: Accepted

Solution code:
print((388130742,597534442,616680192,329869205,170591295,333099663,133009077,738390145,866398347,718889563,252858375,847205021,915711339,123820509,940737264,371653459,323137024,353770801,206282374,847501730,25328739,842176273,569725155,781042769,427196161,570246669,191483611,673385295,324759692,245601370,975058685,406959393,515140586,305799096,981760191,986519078,414054379,149602322,221791721,792638194,696683714,725438992,702530485,51018086,751629411,971550783,664630886,256852905,775465589,799008836,113468411,39816123,501575626,124885216,998121103,181836645,639213333,123883652,785892908,763737161,534833116,978442997,88638656,604356692,409213624,68697295,649970414,855462856,783022045,23314687,531294469,996291083,549054109,639056669,858533109,159693437,604119499,737209731,44657419,51688048,580025381,776803305,261943303,733354121,794717734,478366600,127504505,33985227,9058467,2414454,643550,171531,45719,12185,3247,865,230,61)[2-int(input())])

Submission status: Accepted

Solution code:
N = int(input())

import re
def make_agct(n):        
    agct = ['A', 'G', 'C', 'T']
    accept_list = {}
    
    accept_list[3] = {}
    for s0 in agct:
        for s1 in agct:
            for s2 in agct:
                s = s0 + s1 + s2
                if s == 'AGC':
                    continue
                if s == 'ACG':
                    continue
                if s == 'GAC':
                    continue
                accept_list[3][s] = 1
    
    for i in range(3, n):
        accept_list[i+1] = {}
        for si, v in accept_list[i].items():
            for sn in agct:
                s = si + sn
                last4 = s
                if re.match('.AGC', last4 ):
                    continue
                if re.match('.ACG', last4 ):
                    continue
                if re.match('.GAC', last4 ):
                    continue
                if re.match('AG.C', last4 ):
                    continue
                if re.match('A.GC', last4 ):
                    continue
                last3 = s[1:]
                if last3 in accept_list[i+1]:
                    accept_list[i+1][last3] +=v
                else:
                    accept_list[i+1][last3] = v
    
    ans = 0
    for k, v in accept_list[n].items():
        ans += v
    
    ans = ans % (10 ** 9 + 7)
    print(ans)       
                
make_agct(N)

Submission status: Accepted

Solution code:
def pow_mod(a: int, n: int, mod: int)->int:
    ret = 1
    for _ in range(n):
        ret = (ret * a) % mod
    return ret


def ok(s: str)->bool:
    '''s が条件をみたすかを判定。
    :param s: 判定対象
    :return: 判定結果
    '''
    if 'AGC' == s[-3:]:
        return False
    if 'GAC' == s[-3:]:
        return False
    if 'ACG' == s[-3:]:
        return False
    if 'A' == s[0] and 'GC' == s[-2:]:
        return False
    if 'AG' == s[:2] and 'C' == s[-1]:
        return False
    return True


def we_like_agc(N: int)->int:
    MOD = 10**9 + 7
    AGCT = 'AGCT'

    # dp[i][str] は str の出現回数。
    # また、この dp は前回のメモだけあればいいので 0, 1 にのみ対応。
    dp = [{}, {}]

    # dp の初期化
    # 3 文字で構成される全ての文字列に対して初期化を行う。
    for c1 in AGCT:
        for c2 in AGCT:
            for c3 in AGCT:
                dp[0][c1 + c2 + c3] = 1 if ok(c1 + c2 + c3) else 0
                dp[1][c1 + c2 + c3] = 0

    # i-1 文字の最後の 3 文字を利用して i 文字目のありうる
    # 最後の 3 文字をカウントする。
    turn = 0
    for _ in range(3, N):
        next_turn = 1-turn
        for s, v in dp[turn].items():
            for c in AGCT:
                next_word = s[1:] + c
                if ok(s + c):
                    # i-1 文字の可能な文字列の後ろに c を足した時
                    # それも可能な文字列ならカウントアップ
                    dp[next_turn][next_word] += v
                    dp[next_turn][next_word] %= MOD
            # 次に使えるように初期化
            dp[turn][s] = 0
        # ターンの遷移
        turn = next_turn

    return sum(v for s, v in dp[(N+1) & 1].items() if ok(s)) % MOD


if __name__ == "__main__":
    N = int(input())
    ans = we_like_agc(N)
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A,C,G,T,M,R=0,1,2,3,10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if not(any(t==(k,l,m)for t in((A,G,C),(A,C,G),(G,A,C)))or(j,l,m)==(A,G,C)or(j,k,m)==(A,G,C)):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Submission status: Accepted

Solution code:
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1] # 順序の入れ替え
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
n=int(input())
A,C,G,T,M=0,1,2,3,10**9+7
r=range
dp=[[[[0]*4for k in r(4)]for j in r(4)]for i in r(n+1)]
dp[0][T][T][T]=1
for i in r(1,n+1):
  for j in r(4):
    for k in r(4):
      for l in r(4):
        for m in r(4):
          if any(t==(k,l,m)for t in((A,G,C),(A,C,G),(G,A,C)))or(j,l,m)==(A,G,C)or(j,k,m)==(A,G,C):continue
          dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(dp[n][i][j][k]for i in r(4)for j in r(4)for k in r(4))%M)

Submission status: Accepted

Solution code:
import numpy as np
import sys

MOD = 10**9 + 7
N=int(input())
dp = [{} for i in range(N+1)]
dp[0] = {"XXX":1}

# 終わりではない
def ok(l):
    r = True
    r = r and not "AGC" in l
    r = r and not "AGC" in l[1]+l[0]+l[2]+l[3]
    r = r and not "AGC" in l[0]+l[2]+l[1]+l[3]
    r = r and not "AGC" in l[0]+l[1]+l[3]+l[2]
    return r

# 最後の3つが決まると，わかる
for i in range(N):
    for key in dp[i]:
        for c in "ATCG":
            s = key+c
            if ok(s):
                new_key = s[1:4]
                if not new_key in dp[i+1]:
                    dp[i+1][new_key] = dp[i][key]
                else:
                    dp[i+1][new_key] += dp[i][key]

cnt = 0
for k in dp[N]:
    cnt += dp[N][k]


print(cnt % MOD)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
C = 'ACGT'

dp = [{} for _ in range(N+1)]

def ok(l4):
  if (l4[0:3] in ['AGC', 'GAC', 'ACG'] or
      l4[1:4] in ['AGC', 'GAC', 'ACG'] or
      l4[0:1] + l4[2:4] == 'AGC' or
      l4[0:2] + l4[3:4] == 'AGC'):
    return False
  else:
    return True

for c1 in C:
  for c2 in C:
    for c3 in C:
      l4 = 'X' + c1 + c2 + c3
      if ok(l4):
        dp[3][l4] = 1
      else:
        dp[3][l4] = 0

for i in range(4, N+1):
  for l4 in dp[i-1].keys():
    for c in C:
      next_l4 = l4[1:4] + c
      if next_l4 not in dp[i]:
        dp[i][next_l4] = 0
      if ok(next_l4):
        dp[i][next_l4] = (dp[i][next_l4] + dp[i-1][l4]) % MOD

ans = 0
for count in dp[N].values():
  ans = (ans + count) % MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

dp = [[[[0 for c3 in range(4)] for c2 in range(4)] for c1 in range(4)] for l in range(N + 1)]
dp[0][3][3][3] = 1
for l in range(N):  # len of str
    for c1 in range(4):  # last 1 char
        for c2 in range(4):  # last 2 char
            for c3 in range(4):  #last 3 char
#                print("dp[{}][{}][{}][{}] = {}".format(l, c1, c2, c3, dp[l][c1][c2][c3]))
                if(0 == dp[l][c1][c2][c3]):    continue
                for a in range(4):
                    # A:0, G:1, C:2
                    if((a == 2) & (c1 == 1) & (c2 == 0)):  continue
                    if((a == 2) & (c1 == 0) & (c2 == 1)):  continue
                    if((a == 1) & (c1 == 2) & (c2 == 0)):  continue
                    if((a == 2) & (c1 == 1) & (c3 == 0)):  continue
                    if((a == 2) & (c2 == 1) & (c3 == 0)):  continue

                    dp[l + 1][a][c1][c2] += dp[l][c1][c2][c3]
#                    print("new dp[{}][{}][{}][{}] = {}".format(l + 1, a, c1, c2, dp[l + 1][a][c1][c2]))
                    dp[l][c1][c2][c3] %= 10 ** 9 + 7

ans = 0
for c1 in range(4):  # last 1 char
    for c2 in range(4):  # last 2 char
        for c3 in range(4):  #last 3 char
            ans += dp[N][c1][c2][c3]
            ans %= 10 ** 9 + 7

print(str(ans))

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, '***'))

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    ans = editorial(N)
    ans1 = editorial_dp(N)

    assert ans == ans1
    print(ans)


def editorial(N):
    MOD = 10 ** 9 + 7
    memo = [{} for i in range(N+1)]

    def ok(last4):
        for i in range(4):
            # 文字列ベースなので、隣接文字をswapしやすいように変換
            t = list(last4)
            if i >= 1:
                t[i-1], t[i] = t[i], t[i-1]
            if ''.join(t).count('AGC') >= 1:
                return False

        return True

    def dfs(cur, last3):
        if last3 in memo[cur]:
            return memo[cur][last3]

        # 問題なし
        if cur == N:
            return 1

        # 文字追加
        ret = 0
        for c in 'ACGT':
            # 機械的にswap全部試すチェック
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
                ret %= MOD
        memo[cur][last3] = ret

        return ret

    # TTT: editorial_dp と同様に無害な組合せ
    ans = dfs(0, 'TTT')
    return ans


def editorial_dp(N):
    """
    AGC
    ACG
    GAC
    ----
    追加+swap
    AG.C
    A.GC
    """
    import numpy as np
    from itertools import product

    T, A, G, C = range(4)
    MOD = 10 ** 9 + 7
    dp = np.zeros((N+1, 4, 4, 4), dtype=int)
    # AGCに関係ないTを初期状態とすればなんの影響もない
    dp[0, 0, 0, 0] = 1
    ng_pattern = (A, G, C)

    for i in range(N):
        for c1, c2, c3 in product(range(4), repeat=3):
            if dp[i, c1, c2, c3] == 0:
                continue

            for c4 in range(4):
                patterns = [
                    # 4文字目追加 3文字
                    (c2, c3, c4),
                    (c2, c4, c3),
                    (c3, c2, c4),
                    # 4文字目追加 4文字
                    (c1, c2, c4),
                    (c1, c3, c4),
                ]
                ng = any(ng_pattern == p for p in patterns)
                if ng:
                    continue

                dp[i+1, c2, c3, c4] += dp[i, c1, c2, c3]
                dp[i+1, c2, c3, c4] %= MOD

    ans = 0
    for c1, c2, c3 in product(range(4), repeat=3):
        ans += dp[N, c1, c2, c3]
        ans %= MOD

    return ans


def WA(N):
    """
    3 <= N <= 100
    4種類の文字: ACGT
    4^N 通りの文字列が存在する
    隣接文字2つを1回入れかることができる
    違反: AGC
    違反: 入力例1より
        ACG
        GAC

    2文字までは違反なし
    3文字では3つ違反, 上記の通り
        64-3 = 61
    4文字
        4文字目追加なので61 * 4
        3文字目の時点で3つで終わるパターンがある
        次に 下記パターンの文字が追加されるとNG
            AG C
            AC G
            GA C

        3文字のときに終わるパターンの構成
            AG: [.]AG NGなし    ACGT 4
            AC: [G]AC NGより    AC T 3
            GA: [.]GA NGなし    ACGT 4

        AG: 構成4 * OK:4-1
        AC: 構成3 * OK:4-1
        GA: 構成4 * OK:4-1
            61 + (61 * 4 - [4+3+4] * 1)

        pattern に周期がありそう
        全パターンから引くので、逆元を使いそう
    """
    ans = 61
    ag_ac_ga = [4, 3, 4]
    if N == 3:
        return ans

    MOD = 10 ** 9 + 7
    for i in range(4, N+1):
        ag_ac_ga = [x * 3 for x in ag_ac_ga]
        print(ans + ans * i)
        print(sum(ag_ac_ga))
        ans += ans * i - sum(ag_ac_ga) * 3
        # ans = ans * i - sum(ag_ac_ga)

    ans %= MOD

    aaa()
    return ans


def aaa():
    ans = []
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    x = "".join(map(str, [i, j, k, l]))
                    # ACGT: 0123
                    # AGC, ACG, GAC
                    y = any(z in x for z in ("021", "012", "201"))
                    ans.append((x, y))

    print(*ans, sep="\n")
    print(sum(x[1] for x in ans))
    print(len(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())

mod = 10 ** 9 + 7

dp = [[[[0 for i in range(0,4)] for j in range(0,4)] for k in range(0, 4)] for n in range(0, N + 1)]

dp[0][3][3][3] = 1

# A -> 0
# C -> 1
# G -> 2
# T -> 3

# invalids
# AGC -> 021
# GAC -> 201
# ACG -> 012
# A?GC -> 0?21
# AG?C -> 02?1

for len in range(0,N):
    for c1 in range(0,4):
        for c2 in range(0,4):
            for c3 in range(0,4):
                if dp[len][c1][c2][c3] == 0:
                    continue

                for a in range(0,4):
                    if (c2 == 0 and c3 == 2 and a == 1) or \
                      (c2 == 2 and c3 == 0 and a == 1) or \
                      (c2 == 0 and c3 == 1 and a == 2) or \
                      (c1 == 0 and c3 == 2 and a == 1) or \
                      (c1 == 0 and c2 == 2 and a == 1):
                        continue

                    dp[len + 1][c2][c3][a] += dp[len][c1][c2][c3]


res = 0
for c1 in range(0,4):
    for c2 in range(0,4):
        for c3 in range(0,4):
            res += dp[N][c1][c2][c3] % mod

print(res % mod)

Submission status: Accepted

Solution code:
import itertools
def memo_rec(N):
    if N == 3:
        return 61
    if N == 4:
        return 230
    L = "ATGC"
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(s, k):
        if s.count("AGC"):
            return 0
        for i in range(3):
            t1, t2 = s[i], s[i + 1]
            if (s[:i] + t2 + t1 + s[i+2:]).count("AGC"):
                return 0
        if k == 0:
            return 1
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(str(x + s[:3]), k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 4):
        t = ''
        for x in s:
            t += x
        ret = (ret + rec(t, N - 4)) % MOD
    return ret

N = int(input())
print(memo_rec(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from math import factorial
import numpy as np
from itertools import product

def check(last):
  for i in range(4):
    t = list(last)
    if i > 0:
      t[i-1], t[i] = t[i], t[i-1]
    if 'AGC' in ''.join(t):
      return False
  return True


def main():
  N = int(input())
  M = 10**9 + 7
  DP = np.ones((4, 4, 4), dtype=np.int)
  g2i = {g:i for i,g in enumerate(list('ATGC'))}
  DP[tuple([g2i[g] for g in 'AGC'])] = 0
  DP[tuple([g2i[g] for g in 'GAC'])] = 0
  DP[tuple([g2i[g] for g in 'ACG'])] = 0
  for i in range(N-3):
    _DP = np.zeros((4, 4, 4), dtype=np.int)
    for last3 in [''.join(x) for x in product(*(['ATGC']*3))]:
      for c in 'ATGC':
        if check(last3+c):
          # print(last3+c)
          _DP[tuple([g2i[g] for g in last3[1:]+c])] += DP[tuple([g2i[g] for g in last3])]
          _DP[tuple([g2i[g] for g in last3[1:]+c])] %= M
    DP = _DP
  # print(DP)
  print(np.sum(DP) % M)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def ok(s):
    for i in range(len(s)):
        s_list = list(s)
        if i < len(s)-1:
            s_list[i], s_list[i+1] = s_list[i+1], s_list[i]
        if ''.join(s_list).find("AGC") != -1:
            return False
    return True


n = int(input())
table = [{} for i in range(n+1)]
table[0][''] = 1

for i in range(n):
    for s in table[i]:
        for c in 'ATGC':
            if ok(s[-3:] + c):
                if s[-2:]+c in table[i+1]:
                    table[i+1][s[-2:]+c] += table[i][s]
                else:
                    table[i+1][s[-2:]+c] = table[i][s]

print(sum(table[n].values()) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
def d_we_like_agc(N):
    from itertools import product
    MOD = 10 ** 9 + 7

    # dp[i][j][k][l]: Sの先頭i文字目を見ているとき、i-3, i-2, i-1番目の文字が
    # j, k, lだとして、そのような文字列が何通り存在するか
    # ACGTはそれぞれ0123と対応付けされる
    dp = [[[[0 for k in range(4)] for k in range(4)] for j in range(4)] for i in range(N + 1)]
    # 文字の制約はAGCに関するものであり、Tは関係ない。
    # よって、調べる文字列が 'TTT' + S だとしていい。
    dp[0][3][3][3] = 1

    def digit2acgt(a, b, c, d):
        # 4つの数字abcdを対応するACGTに変換する
        a, b, c, d = map(lambda x: 'ACGT'[x], (a, b, c, d))
        return ('*' + b + c + d, a + '*' + c + d, a + b + '*' + d)

    for k in range(N):
        for c0, c1, c2, c3 in product(range(4), repeat=4):
            for s in digit2acgt(c0, c1, c2, c3):
                # これらの文字列は許されない
                if s in ('*AGC', '*GAC', '*ACG', 'A*GC', 'AG*C'):
                    break
            else:
                # 文字列 TTT...c0c1c2(TTTを除く長さk) の末尾にc3を加えることが許される
                # 次回は新しい文字列 TTT...c1c2c3(長さk+1)に対して同じことを行う
                dp[k + 1][c1][c2][c3] += dp[k][c0][c1][c2]
                dp[k + 1][c1][c2][c3] %= MOD

    ans = 0
    for c0, c1, c2 in product(range(4), repeat=3):
        ans += dp[N][c0][c1][c2]
        ans %= MOD
    return ans

N = int(input())
print(d_we_like_agc(N))

Submission status: Accepted

Solution code:
n = int(input())
mod = 1000000007

dp = [[[[0]*4 for i in range(4)] for i in range(4)] for i in range(101)]

# 0,1,2,3 ="AGCT"
for num in range(1):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for add in range(4):
          if c2 == 0 and c1 == 1 and add ==2:
            continue
          if c2 == 0 and c1 == 2 and add ==1:
            continue
          if c2 == 1 and c1 == 0 and add ==2:
            continue  
          if c3 == 0 and c2 == 1 and add ==2:
            continue
          if c3 == 0 and c1 == 1 and add ==2:
            continue
          dp[3][add][c1][c2] = 1

for num in range(1,n):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for add in range(4):
          if c2 == 0 and c1 == 1 and add ==2:
            continue
          if c2 == 0 and c1 == 2 and add ==1:
            continue
          if c2 == 1 and c1 == 0 and add ==2:
            continue  
          if c3 == 0 and c2 == 1 and add ==2:
            continue
          if c3 == 0 and c1 == 1 and add ==2:
            continue
          dp[num+1][add][c1][c2] += dp[num][c1][c2][c3]
          dp[num+1][add][c1][c2] %= mod

ans = 0

for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      ans += dp[n][c1][c2][c3]
      ans %= mod
if n ==1:
  print(4)
elif n ==2:
  print(16)
else:
  print(ans)

Submission status: Accepted

Solution code:
import re
N = int(input())
memo_dict = [{} for i in range(N+1)]
def ok(last4):
    if re.match(r".*AGC|.*ACG|A.GC|AG.C|.*GAC", last4):
        return True
    else:
        return False

def dfs(ind, last3):
    if last3 in memo_dict[ind]:
        return memo_dict[ind][last3]
    if ind == N:
        return 1
    cnt = 0
    for c in "ATGC":
        if not ok(last3 + c):
            cnt += dfs(ind + 1, last3[1:] + c)
            cnt %= (1e9+7)
    memo_dict[ind][last3] = cnt
    return cnt
print(int(dfs(0,"TTT")))

Submission status: Accepted

Solution code:
def compute():
  from sys import stdin
  N = int(stdin.readline().strip())
  MOD = int(1e9)+7

  dp = {}
  prohibited = ('AGC', 'ACG', 'GAC')

  def flt(a,b,c,d):
    if (b is None) or (c is None) or (d is None):
      return True
    if (b+c+d) in prohibited:
      return False
    if (a is not None) and (((a+c+d)=='AGC') or ((a+b+d)=='AGC')):
      return False
    return True

  def f(prev3, prev2, prev1, n):
    if n==0:
      return 1

    k = (prev3, prev2, prev1, n)
    if k in dp:
      return dp[k]

    nexlis = ('A', 'C', 'G', 'T')
    ret = sum(map(
      lambda nex: f(prev2, prev1, nex, n-1),
      filter(
        lambda nex: flt(prev3, prev2, prev1, nex),
        nexlis
      )
    )) % MOD

    dp[k] = ret
    return ret

  print( f(None, None, None, N) )


if __name__ == "__main__":
  compute()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from itertools import product

def main():
    N = II()
    dp = Counter()
    dp['TTT'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for p1, p2, p3, cur in product('ACGT', repeat=4):
            if p2 + p1 + cur in ['AGC', 'GAC', 'ACG']:
                continue
            if p3 + p1 + cur == 'AGC':
                continue
            if p3 + p2 + cur == 'AGC':
                continue
            new = p2 + p1 + cur
            old = p3 + p2 + p1
            dp[new] = (dp[new] + pre[old]) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
from sys import stdin

# 各文字を分かりやすいようにintで
A = 0
G = 1
C = 2
T = 3

# mod定義
mod = 10**9 + 7

# 3 <= N <= 100
N = int(stdin.readline().rstrip())

# dp[101][4][4][4]の初期化
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(101)]


"""
# ダメな条件
AGC(012)
GAC(102)
ACG(021)
A?GC(0?12)
AG?C(01?2)

# 変数の定義
c1: 後ろから3番目の文字
c2: 後ろから2番目の文字
c3: 後ろから1番目の文字
a: 追加する文字列
"""

dp[0][T][T][T] = 1

for i in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    # ダメな条件の時は処理しない
                    if c2 == A and c3 == G and a == C: continue # AGC
                    if c2 == G and c3 == A and a == C: continue # GAC
                    if c2 == A and c3 == C and a == G: continue # ACG
                    if c1 == A and c3 == G and a == C: continue # A?GC
                    if c1 == A and c2 == G and a == C: continue # AG?C
                    
                    # 足し込む
                    # 例えば ?TAC の4文字の数は ATA, GTA, CTA, TTA の3文字の集合の総数
                    # ただ、上でダメな条件はcontinueしてるので含まれない
                    dp[i+1][c2][c3][a] += dp[i][c1][c2][c3]
                    dp[i+1][c2][c3][a] %= mod

ans = 0

for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[N][c1][c2][c3]
            ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
import re

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    dp = [[[[0L for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N + 1)]
    dp[0][3][3][3] = 1
    for i in range(N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    for x in range(4):
                        if x == 2 and c2 == 1 and c3 == 0:
                            continue
                        if x == 2 and c1 == 1 and c3 == 0:
                            continue
                        if x == 2 and c2 == 0 and c1 == 1:
                            continue
                        if x == 2 and c2 == 1 and c1 == 0:
                            continue
                        if x == 1 and c2 == 0 and c1 == 2:
                            continue
                        dp[i + 1][c2][c1][x] = (dp[i + 1][c2][c1][x] + dp[i][c3][c2][c1] ) % 1000000007L
    count = 0L
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                    count = (count + dp[N][c1][c2][c3]) % 1000000007L

    print count

##    if N == 3:
##        print 61
##        return
##
##
##    X = N - 3
##    ans = 1L
##    for i in range(N):
##        ans = (ans * 4L) % 1000000007L
##    sub = 26L
##    for i in range(X -1):
##        sub = (sub * 4L) % 1000000007L
##
##    print (ans - sub) % 1000000007L


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip())
MOD =10**9+7
MEMO = [{} for _ in range(N+1)]
ACGT = "ACGT"
ACG = ["ACG","AGC","CAG","ATCG","ACTG","ACCG"]

def acg_check(last4):
  for acg in ACG:
    if acg in last4:
      return False
  return True

def func(length, last3):
  if last3 in MEMO[length]:
    return MEMO[length][last3]
  if length == N:
    return 1

  ans = 0
  for c in ACGT:
    if len(last3)==3:
      if acg_check(last3+c):
        ans += func(length+1,last3[1:]+c)%MOD
    else:
      if acg_check(last3+c):
        ans += func(length+1,last3+c)%MOD
  MEMO[length][last3] = ans
  return ans

print(func(0,"")%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product

def main():
    N = II()
    A, G, C, T = range(4)
    def code(c0, c1, c2):
        return c0 + 4 * c1 + 16 * c2
    dp = [0] * 64
    dp[code(T, T, T)] = 1
    for _ in range(N):
        pre = dp
        dp = [0] * 64
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) in [(A, G, C), (A, C, G), (G, A, C)]:
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[code(cur, p1, p2)] += pre[code(p1, p2, p3)]
                dp[code(cur, p1, p2)] %= MOD
    ans = sum(dp)

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
N = int(input())
MOD = 1000000007
chars = ['A', 'C', 'G', 'T']

def seq_gen():
    return ((c1, c2, c3) for c3 in chars for c2 in chars for c1 in chars)

tbl = {}
for i in range(N+1):
    for c1, c2, c3 in seq_gen():
        tbl[(i, c1, c2, c3)] = 0

tbl[(0,'T','T','T')] = 1

for i in range(N):
    for c1, c2, c3 in seq_gen():
        if tbl[(i, c1, c2, c3)] == 0:
            continue
        for a in chars:
            ng_cond =   (a + c1 + c2 == 'AGC' or
                        a + c1 + c2 == 'ACG' or
                        a + c1 + c2 == 'GAC' or
                        a + c2 + c3 == 'AGC' or
                        a + c1 + c3 == 'AGC')
            if not ng_cond:
                tbl[(i+1, a, c1, c2)] += tbl[(i, c1, c2, c3)]
                tbl[(i+1, a, c1, c2)] %= MOD

ans = 0
for c1, c2, c3 in seq_gen():
    ans += tbl[(N, c1, c2, c3)]
    ans %= MOD

print(ans)