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:
# -*- coding: utf-8 -*-

N = int(input())
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)) % (10 ** 9 + 7)
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

N=input()

if N==3:
	print 61
	quit()

dp=defaultdict(lambda: 0)	#dp[ (n,i,j,k,l) ]
a=0;g=1;c=2;t=3

n=4
for i,j,k,l in itertools.product( range(4), repeat=4 ):
	if l==c and j==g and i==a: continue
	elif l==c and k==g and i==a: continue
	elif l==c and k==g and j==a: continue
	elif k==c and j==g and i==a: continue
	elif l==c and k==a and j==g: continue
	elif k==c and j==a and i==g: continue
	elif l==g and k==c and j==a: continue
	elif k==g and j==c and i==a: continue
	dp[ (n,i,j,k,l) ]=1



for n in range(5,N+1):
	for i,j,k,l in itertools.product( range(4), repeat=4 ):
		if l==c and j==g and i==a: continue
		elif l==c and k==g and i==a: continue
		elif l==c and k==g and j==a: continue
		elif k==c and j==g and i==a: continue
		elif l==c and k==a and j==g: continue
		elif k==c and j==a and i==g: continue
		elif l==g and k==c and j==a: continue
		elif k==g and j==c and i==a: continue
	
		for m in range(4):
			dp[ (n,i,j,k,l) ]+=dp[ (n-1,j,k,l,m) ]


ans=0
for x,val in dp.items():
	n=x[0]
	if n==N:
		ans+=val

print ans%(10**9+7)

Submission status: Accepted

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

def ppp(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(c,l):
    if l in memo[c]:
        return memo[c][l]
    if c == n:
        return 1
    ret = 0
    for b in "AGCT":
        if ppp(l+b):
            ret = (ret + dfs(c + 1,l[1:] + b)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

N = int(input())

chs = ['A', 'C', 'G', 'T']
ngs = ['AGC', 'ACG', 'GAC']

memo = defaultdict(int)
for s in list(set(map(''.join, itertools.product(chs, repeat=3))) - set(ngs)):
    memo[s] += 1

# NG: AGC, ACG, GAC, AG*C. A*GC
for i in range(3, N):
    m = defaultdict(int)
    for key in memo.keys():
        m['C'+key[:2]] += memo[key]
        m['T'+key[:2]] += memo[key]
        if key[:2] != 'AC':
            m['G'+key[:2]] += memo[key]
        if key[:2] != 'CG' and key[:2] != 'GC' and key[0]+key[2] != 'GC' and key[1]+key[2] != 'GC':
            m['A'+key[:2]] += memo[key]
    memo = m
print(sum(memo.values()) % (10**9+7))

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, 'TTT'))

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
memo = [{} for _ in range(N)]
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 'AGC' in ''.join(t):
            return False
    return True
def dfs(cur, last3):
    if cur == N:
        return 1
    elif last3 in memo[cur]:
        return memo[cur][last3]
    else:
        ret = 0
        for c in 'ACGT':
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
        ret = ret % MOD
        memo[cur][last3] = ret
        return ret
print(dfs(0, '   '))

Submission status: Accepted

Solution code:
N,m=int(input()),10**9+7

from collections import defaultdict

memo=[defaultdict(int) for i in range(N+1)]

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

memo[0]['TTT']=1
for i in range(1,N+1):
    for last3 in memo[i-1].keys():
        v = memo[i-1][last3]%m
        tmp=0
        for c in ['A','G','T','C']:
            if ok(last3+c):
                memo[i][last3[1:]+c]+=v

print(sum(memo[N].values())%m)

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!=3:
      t[i],t[i+1]=t[i+1],t[i]
    if "".join(t).count("AGC")>=1:
      return False
  return True

def solve(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=(solve(cur+1,last3[1:]+c)+ret)%MOD
  memo[cur][last3]=ret
  return ret

print(solve(0,"TTT"))

Submission status: Accepted

Solution code:
#貰うDP
import itertools
N, MOD = int(input()), 10**9+7

memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 4)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 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]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(N + 3, 'TTT'))

Submission status: Accepted

Solution code:
#貰うDP
import itertools
N, MOD = int(input()), 10**9+7
memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 1)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 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]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

def answer(n):
    ans = 0
    clist = list('ACGT')
    for c in itertools.product(clist, clist, clist):
        ch = ''.join(c)
        ans += dfs(n, ch)
    return ans % MOD

print(answer(N))

Submission status: Accepted

Solution code:
n=int(input())
mod = 10**9+7
memo=[{} for i in range(n)]
#indexに文字列がそのまま使える
def chk_agc(char):
    l=len(char)
    #print(char)
    result=True
    if l>2:
        last3=char[l-3:l]
        if last3=="AGC" or last3=="ACG" or last3=="GAC":
            result=False
    if l>3:
        if char[l-4]=="A" and char[l-1]=="C":
            if char[l-3]=="G" or char[l-2]=="G":
                result=False
    return result
def count_agc(i,n,last4):
    if i==n:
        return 1
    if last4 in memo[i]:
        return memo[i][last4]
    ret=0
    if i>3:
        last3=last4[1:4]
    else:
        last3=last4
    for char in ["A","G","C","T"]:
        next_last4 = last3+char
        if chk_agc(next_last4):
            ret += count_agc(i+1,n,next_last4)
    if i>2:
        memo[i][last4]=ret
    return ret
print(count_agc(0,n,"")%mod)

Submission status: Accepted

Solution code:
import pprint

N = int(input())

MOD = pow(10, 9) + 7

# length 
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1) ]

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


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

                # 新しく追加する文字
                for n in range(4):
                    if n == 2 and c1 == 1 and c2 == 0:
                        continue
                    if n == 2 and c1 == 0 and c2 == 1:
                        continue
                    if n == 1 and c1 == 2 and c2 == 0:
                        continue
                    if n == 2 and c1 == 1 and c3 == 0:
                        continue
                    if n == 2 and c2 == 1 and c3 == 0:
                        continue

                    dp[index + 1][n][c1][c2] += dp[index][c1][c2][c3]
                    dp[index + 1][n][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

 
print(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の初期化
        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):
    # 深いところから戻っていく過程で
    # 今までの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):
            # ok の場合count を増やす
            # 1個ずらして curを増やす
            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())
P = 10**9 + 7
memo = [{} for i in range(n + 1)]
def ok(last4):
    if last4.count('AGC') >= 1:return False
    for i in range(3):
        t = list(last4)
        t[i], t[i+1] = t[i+1] , t[i]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if cur == n:
        return 1
    if last3 in memo[cur]:
        return memo[cur][last3]
    ret = 0
    for c in 'AGCT':
        if(ok(last3+c)):
            ret = (ret + dfs(cur + 1, last3[1:]+c))%P
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
n = int(input())
mem = [{} for i in range(n + 1)]

first3s = []
for c in 'ACGT':
	for c2 in 'ACGT':
		for c3 in 'ACGT':
			first3s.append(c + c2 + c3)

ans = 0
for three in first3s:
  mem[3][three] = 0 if three in ['AGC', 'ACG', 'GAC'] else 1
  ans += mem[3][three]

def check4(four):
  if 'AGC' in four:
    return False
  for i in range(3):
    if 'AGC' in four[:i] + four[i+1] + four[i] + four[i+2:]:
      return False
  return True

if n > 3:
  for i in range(4, n + 1):
    ans = 0
    for three in first3s:
      for c in 'ACGT':
        four = c + three
        if check4(four):
          ans = (ans + mem[i - 1][three]) % (10**9 + 7)
          mem[i][(c + three)[:3]] = (mem[i].get((c + three)[:3], 0) + mem[i - 1][three]) % (10**9 + 7)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
MOD = 10 ** 9 + 7

dpm = {
    ''.join(k):1
    for k in product('ACGT', repeat = 3)
}

for k in ('AGC', 'ACG', 'GAC'):
    dpm[k] = 0

def ok4(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

i = 3
ans = 61

while i < N:
    ndpm = {k:0 for k in dpm}
    for k in dpm:
        for c in 'AGCT':
            ns = k + c
            if ok4(ns):
                ndpm[ns[-3:]] += dpm[k]
    dpm = ndpm
    i += 1                

print(sum(dpm.values()) % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

# A C G T を
# 0 1 2 3 と置く

dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(101)]
dp[0][3][3][3] = 1

mod = 10**9+7

#文字列の文字数
for len in range(N):
    #最後から1文字目の文字
    for c1 in range(4):
        #最後から2文字目の文字
        for c2 in range(4):
            #最後から3文字目の文字
            for c3 in range(4):
                #新しく追加する文字
                for a in range(4):
                    if c2 == 0 and c1 == 1 and a == 2 :
                        continue #012
                    if c2 == 1 and c1 == 0 and a == 2 :
                        continue #102
                    if c2 == 0 and c1 == 2 and a == 1 :
                        continue #021
                    if c3 == 0 and c1 == 1 and a == 2 :
                        continue #0?12
                    if c3 == 0 and c2 == 1 and a == 2 :
                        continue #01?2
                    
                    dp[len + 1][c2][c1][a] += dp[len][c3][c2][c1]
                    #dp[len + 1][c2][c1][a] %= mod
        
ans = 0

#最後から1文字目の文字
for c1 in range(4):
    #最後から2文字目の文字
    for c2 in range(4):
        #最後から3文字目の文字
        for c3 in range(4): 
            ans += dp[N][c3][c2][c1]

print(ans % mod)

Submission status: Accepted

Solution code:
import functools
import re

MOD = 10 ** 9 + 7
ACGT = 'ACGT'
GOOD = 'TTT'
BAD = re.compile(r'AGC|GAC|ACG|A.GC|AG.C')


@functools.lru_cache(maxsize=None)
def dfs(n, i, last3):
    if i == n:
        return 1
    else:
        return sum(
            dfs(n, i + 1, last3[1:] + c)
            for c in ACGT
            if not re.search(BAD, last3 + c)) % MOD


N = int(input())
print(dfs(N, 0, GOOD))

Submission status: Accepted

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

dp = [[[[0] * 4 for ___ in range(4)]for __ in range(4)]for _ in range(N + 1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[0][i][j][k] = 0
            dp[1][i][j][k] = 1
            dp[2][i][j][k] = 1
            if i == 2 and j == 1 and k == 0:
                continue
            elif i == 1 and j == 2 and k == 0:
                continue
            elif i == 2 and j == 0 and k == 1:
                continue
            dp[3][i][j][k] = 1


for n in range(3, N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for c in range(4):
                    if c == 1 and i == 2 and j == 0:
                        continue
                    elif c == 2 and i == 1 and j == 0:
                        continue
                    elif c == 2 and i == 0 and j == 1:
                        continue
                    elif c == 2 and i == 1 and k == 0:
                        continue
                    elif c == 2 and j == 1 and k == 0:
                        continue
                    dp[n + 1][c][i][j] += dp[n][i][j][k]
                    dp[n + 1][c][i][j] %= MOD

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans % MOD)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())

#dp=np.zeros(N+1,4,4,4)
dp=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(N+1)]

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

for len in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if(dp[len][c1][c2][c3]==0):
                    continue
                for a in range(4):
                    if(a==2 and c1==1 and c2==0):
                        continue
                    if(a==2 and c1==0 and c2==1):
                        continue
                    if(a==1 and c1==2 and c2==0):
                        continue
                    if(a==2 and c1==1 and c3==0):
                        continue
                    if(a==2 and c2==1 and c3==0):
                        continue
                    dp[len+1][a][c1][c2]+=dp[len][c1][c2][c3]
                    dp[len+1][a][c1][c2]%=10**9+7

                    

ans=0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans+=dp[N][c1][c2][c3]
            ans%=10**9+7
print(ans)

Submission status: Accepted

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

    # 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)]
    # 文字の制約にTは関係ないので、調べる文字列は 'TTT' + S だとしていい。
    dp[0][3][3][3] = 1

    for k in range(N):
        for c0, c1, c2, c3 in product(range(4), repeat=4):
            # 数字列c0c1c2c3をACGT文字列に変換したときに許されない文字列をはじく
            strings = ''.join(map(lambda x: 'ACGT'[x], (c0, c1, c2, c3)))
            for s in (strings[:i] + '*' + strings[i + 1:] for i in range(3)):
                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
    return sum([dp[N][c0][c1][c2] for c0, c1, c2 in product(range(4), repeat=3)]) % MOD

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

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for x in range(N + 1)]
def ok(sec4):
  for i in range(4):
    tem = list(sec4)
    if i >= 1:
      tem[i - 1], tem[i] = tem[i], tem[i - 1]
    tem2 = "".join(tem)  
    if tem2[:3] == "AGC" or tem2[1:] == "AGC":
      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 s in "AGCT":
    if ok(last3 + s):
      ret = ret + dfs(cur + 1, last3[1:] + s)
  memo[cur][last3] = ret
  return ret
print(dfs(0, "TTT") % MOD)

Submission status: Accepted

Solution code:
def dfs(index, last, string, memo):
    mod = 10 ** 9 + 7
    if string in memo[index]:
        return memo[index][string]
    if index == last:
        return 1

    ret = 0
    for s in "ACGT":
        if check(string + s):
            ret = (ret + dfs(index + 1, last, string[1:] + s, memo)) % mod
    memo[index][string] = ret
    return ret


def check(string):
    for i in range(4):
        s_list = list(string)
        if i >= 1:
            s_list[i-1], s_list[i] = s_list[i], s_list[i-1]
        if "".join(s_list).count("AGC") >= 1:
            return False
    return True


def main():
    n = int(input())
    memo = [{} for _ in range(n+1)]

    ans = dfs(0, n, "TTT", memo)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10**9 + 7
memo = [{} for x 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, 'TTT'))

Submission status: Accepted

Solution code:
from sys import exit

N = int(input())

# 動的計画法
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for length in range(N + 1)]

# A = 0, C = 1, G = 2, T = 3
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][i][j][k] = 1

# AGC, GAC, ACGは禁止
dp[3][0][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

for length in range(4, N + 1):
    # 最後から3ばんめ
    for c1 in range(4):
        # 最後から2ばんめ
        for c2 in range(4):
            # 最後から1ばんめ
            for c3 in range(4):
                # 追加する文字
                for s in range(4):
                    if [c2, c3, s] not in ([0, 2, 1], [2, 0, 1], [0, 1, 2]):
                        if [c1, c3, s] != [0, 2, 1] and [c1, c2, s] != [0, 2, 1]:
                            dp[length][c2][c3][s] += dp[length - 1][c1][c2][c3]

ans = 0

for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from sys import exit

N = int(input())

# 動的計画法
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for length in range(N + 1)]

# A = 0, C = 1, G = 2, T = 3
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][i][j][k] = 1

# AGC, GAC, ACGは禁止
dp[3][0][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

for length in range(4, N + 1):
    # 最後から3ばんめ
    for c1 in range(4):
        # 最後から2ばんめ
        for c2 in range(4):
            # 最後から1ばんめ
            for c3 in range(4):
                if dp[length - 1][c1][c2][c3] == 0:
                    continue
                # 追加する文字
                for s in range(4):
                    if [c2, c3, s] not in ([0, 2, 1], [2, 0, 1], [0, 1, 2]):
                        if [c1, c3, s] != [0, 2, 1] and [c1, c2, s] != [0, 2, 1]:
                            dp[length][c2][c3][s] += dp[length - 1][c1][c2][c3]

ans = 0

for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
memo = [{} for _ in range(n+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i],t[i-1] = t[i-1],t[i]
        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 i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

Submission status: Accepted

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

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

def isAGC(char4):
    for i in range(4):
        tmp = list(char4)
        if i != 3:
            tmp[i], tmp[i + 1] = tmp[i + 1], tmp[i]
        if ''.join(tmp).count('AGC') >= 1:
            return True
    return False

def dfs(cur, char3):
    if char3 in memo[cur]:
        return memo[cur][char3]
    if cur == N:
        return 1
    
    ret = 0
    for c in ['A', 'C', 'G', 'T']:
        if not isAGC(char3 + c):
            ret = (ret + dfs(cur + 1, char3[1:] + c)) % MOD

    memo[cur][char3] = ret
    return ret

print(dfs(0, 'XXX'))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[[[0 for i in range(4)] for i in range(4)] for i in range(4)] for i in range(n+1)]

#A=0, C=1, G=2, T=3
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][i][j][k] = 1

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

for i in range(4, n+1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    if [b,c,d] not in ([0,2,1],[2,0,1],[0,1,2]):
                        if [a,c,d] != [0,2,1] and [a,b,d] != [0,2,1]:
                                dp[i][b][c][d] += dp[i-1][a][b][c]
                                
count = 0
for i in range(4):
    for j in range(4):
            count = (count + sum(dp[n][i][j])) % (10**9+7)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
memo = [{} for _ in range(n+1)]


def AGCin(s):
    for i in range(len(s) - 2):
        if s[i] == 'A' and s[i+1] == 'G' and s[i+2] == 'C':
            return True
    return False


def isok(last4):
    if AGCin(last4):
        return False
    for i in range(3):
        last4_ = [c for c in last4]
        tmp = last4_[i]
        last4_[i] = last4_[i+1]
        last4_[i+1] = tmp
        if AGCin(''.join(last4_)):
            return False
    return True


def dfs(i, last3):
    if i == n:
        return 1
    if last3 in memo[i]:
        return memo[i][last3]
    ret = 0
    for c in 'AGCT':
        last4 = last3 + c
        if isok(last4):
            new_last3 = last4[1:]
            delta = dfs(i+1, new_last3)
            memo[i+1][new_last3] = delta
            ret = (ret + delta) % mod
    return ret


print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
# coding:utf-8


DNA = ["A","C","G","T"]
ng3 = ["AGC","ACG","GAC"]
ng4 = ["ACGC","AGGC","ATGC", "AGAC","AGTC"]
MOD = 10**9 +7

def main():
    N = int(input())
    memo = [{} for i in range(N+1)]
    # ACGTからなる
    # 部分文字列AGCを持たない
        # AGC
    # 隣接する2文字の入れかえを1回することでうえの条件に違反しない
        # ACG
        # GAC
        # A-GC
        # AG-C

    # 4^N個の通り

    # 動的計画法
        # 違反があったやつの打ち切り
        # すでに組み合わせの通りが分かっているやつの省略
    # 再帰
    # count = pow(4,N)
    ans = string_check("",0,N,memo)
    # print(memo)
    print(ans%MOD)

    # print(memo2)
    #print(len(memo))


def string_check(nowstr,i,N,memo):
    # print(nowstr)
    slen = len(nowstr)
    if slen == 3:
        if nowstr in ng3:
            return 0
    if slen == 4:
        if nowstr[-3:] in ng3:
            return 0
        elif nowstr in ng4:
            return 0
    elif slen > 4:
        if nowstr[-3:] in ng3:
            return 0
        elif nowstr[-4:] in ng4:
            return 0
    if nowstr[-3:] in memo[i]:
        return memo[i][nowstr[-3:]]
    elif slen == N:
        return 1
    else:
        count = 0
        for s in DNA:
            count += string_check(nowstr+s,i+1,N,memo)
        if slen >= 4:
            memo[i][nowstr[-3:]] = count
        return count
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
MOD = 10**9 + 7

# agc, acg, gac, agxc, axgc
def ok(last4):
    if last4.count("AGC")>0:
        return False
    if last4.count("ACG")>0:
        return False
    if last4.count("GAC")>0:
        return False
    if last4[:2]=="AG" and last4[3]=="C":
        return False
    if last4[0]=="A" and last4[2:]=="GC":
        return False
    return True

memo = [{} for _ in range(n+1)]
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1

    res = 0
    for c in "AGCT":
        if ok(last3+c):
            res = (res + dfs(cur+1, last3[1:]+c))%MOD
    memo[cur][last3] = res
    return res

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
#   A C G T
# A
# C
# G
# T

import numpy as np

N = int(input())
x = 10 ** 9 + 7

S = np.ones([4, 4, 4], dtype=np.int64)
S[0, 1, 2] = 0
S[0, 2, 1] = 0
S[2, 0, 1] = 0
for _ in range(3, N):
    St = np.zeros([4, 4, 4], dtype=np.int64)
    for i in range(4):
        for j in range(4):
            if i == 0 and j == 2:
                St[j, :, 0] += S[i, j, :]
                St[j, :, 2] += S[i, j, :]
                St[j, :, 3] += S[i, j, :]
            else:
                for k in range(4):
                    St[j, k, 0] += S[i, j, k]
                    St[j, k, 3] += S[i, j, k]
                    if j == 0 and k == 1:
                        St[j, k, 1] += S[i, j, k]
                    elif (j == 0 and k == 2) or (j == 2 and k == 0):
                        St[j, k, 2] += S[i, j, k]
                    elif i == 0 and k == 2:
                        St[j, k, 2] += S[i, j, k]
                    else:
                        St[j, k, 1] += S[i, j, k]
                        St[j, k, 2] += S[i, j, k]
    S = St % x
print(np.sum(S) % x)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
memo = [{} for i in range(N+1)] #0段目からN段目までを覚えるため

### 条件判定部分
def judge(last4):
    ret = True
    if any([last4[1:] == s for s in ["AGC","ACG","GAC"]]):
        ret = False
    elif last4[0]+last4[2:] == "AGC":
        ret = False
    elif last4[:2]+last4[3] == "AGC":
        ret = False
    return ret

def dfs(cur, last3):
    if last3 in memo[cur]: 
        ret = memo[cur][last3]
    elif cur == N: 
        ret = 1
    else:
        ret = 0
        for c in "ACGT":
            if judge(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, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ 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 x in 'ATGC':
        if ok(last3 + x):
            ret = (ret + dfs(cur + 1, last3[1:] + x)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
def ok(last4):
	for i in range(4):
		t = list(last4)
		if i >= 1:
			t[i], t[i - 1] = t[i - 1], t[i]
		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


n = int(input())
mod = 10 ** 9 + 7
memo = [{} for i in range(n + 1)]

print(dfs(0, 'TTT'))

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, 'TTT'))