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, 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('ACG') >= 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())
dp = [[0 for i in range(4)] for j in range(N)]
mod = 10**9 + 7

for i in range(N):
    if(i == 0):
        for j in range(4):
            dp[0][j] = 1
    elif(i == 1):
        for j in range(4):
            dp[1][j] = 4
    elif(i == 2):
        base = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
        dp[i][0] += base
        dp[i][1] += base - dp[i-2][2] - dp[i-2][0]
        dp[i][2] += base - dp[i-2][0]
        dp[i][3] += base
        for j in range(4):
            dp[i][j] %= mod
    else:
        base = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
        dp[i][0] += base
        dp[i][1] += base - dp[i-3][0]*3 - dp[i-2][2] - dp[i-2][0]
        dp[i][2] += base - (dp[i-2][0] - dp[i-3][2])
        dp[i][3] += base
        for j in range(4):
            dp[i][j] %= mod
    
print((dp[N-1][0] + dp[N-1][1] + dp[N-1][2] + dp[N-1][3])%mod)

Submission status: Accepted

Solution code:
import copy

MOD = 10 ** 9 + 7

def make_list(*args):
	r = [0] * args[-1]
	for n in args[len(args) - 2::-1]:
		r = [copy.deepcopy(r) for _ in range(n)]
	return r

N = int(input())

dp = make_list(N + 1, 5, 5, 5)
dp[0][0][0][0] = 1

# INIT = 0, A = 1, C = 2, G = 3, T = 4
for n in range(N):
	for i in range(5):
		for j in range(5):
			for k in range(5):
				for l in range(1, 5):
					# AGC
					if j == 1 and k == 3 and l == 2:
						continue
					# GAC
					if j == 3 and k == 1 and l == 2:
						continue
					# ACG
					if j == 1 and k == 2 and l == 3:
						continue
					# A*GC
					if i == 1 and k == 3 and l == 2:
						continue
					# AG*C
					if i == 1 and j == 3 and l == 2:
						continue
					dp[n + 1][j][k][l] += dp[n][i][j][k]
					dp[n + 1][j][k][l] %= MOD

r = 0
for i in range(1, 5):
	for j in range(1, 5):
		for k in range(1, 5):
			r += dp[N][i][j][k]
			r %= MOD

print(r)

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10**9+7
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 i in range(4):
    for j in range(4):
        for k in range(4):
            if k == 2 and j == 1 and i == 0:
                continue
            if k == 1 and j == 2 and i == 0:
                continue
            if k == 2 and j == 0 and i == 1:
                continue
            dp[3][i][j][k] = 1
'''
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[n][i][j][k] == 0:
                    continue
                for new in range(4):
                    if new == 2 and i == 1 and j == 0:
                        continue
                    if new == 1 and i == 2 and j == 0:
                        continue
                    if new == 2 and i == 0 and j == 1:
                        continue
                    if new == 2 and i == 1 and k == 0:
                        continue
                    if new == 2 and j == 1 and k == 0:
                        continue
                    dp[n+1][new][i][j] += dp[n][i][j][k]
                    dp[n+1][new][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]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)] for _ in range(4)]
           for _ in range(4)] for _ in range(101)]
    dp[0][3][3][3] = 1
    mod = 10 ** 9 + 7
    for n in range(100):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    if dp[n][i][j][k] == 0:
                        continue
                    for a in range(4):
                        if (j == 0 and i == 1 and a == 2) or \
                            (j == 0 and i == 2 and a == 1) or \
                            (j == 1 and i == 0 and a == 2) or \
                            (k == 0 and j == 1 and a == 2) or \
                                (k == 0 and i == 1 and a == 2):
                            continue
                        dp[n + 1][a][i][j] += dp[n][i][j][k]
                        dp[n + 1][a][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]
                ans %= mod
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
MOD = 10 ** 9 + 7

s = "ATGC"
t = ["AGC", "ACG", "GAC"]
d = [defaultdict(int), {x+y+z: 1 for x in s for y in s for z in s if x+y+z not in t}]
# d = [{"": 1}, defaultdict(int)]

# print(d[0])
for i in range(4, n+1):
    a = i%2
    b = (i-1)%2

    d[a] = defaultdict(int)
    for k in d[b]:
        for c in s:
            if "AGC" not in [k[1:]+c, k[0]+k[2]+c, k[2]+k[1]+c, k[1]+c+k[2], k[0]+k[1]+c]:
                d[a][k[1:]+c] += d[b][k]
                d[a][k[1:]+c] %= MOD

print(sum(d[n%2].values()) % MOD)

Submission status: Accepted

Solution code:
N = int(input())

MOD = 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())
dp=[[[[0,0,0,0] for _ in range(4)] for _ in range(4)] for _ in range(101)]
mod=10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[3][i][j][k]=1
dp[3][1][2][0]=0
dp[3][2][1][0]=0
dp[3][1][0][2]=0
#a:0,c:1,g:2,t:3
for m in range(4,n+1):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if i==0:
          for l in range(4):
            dp[m][i][j][k]+=dp[m-1][j][k][l]
          dp[m][i][j][k]%=mod
        elif i==1:
          if j==2 and k==0:
            dp[m][i][j][k]=0
          elif j==0 and k==2:
            dp[m][i][j][k]=0
          elif j==2 and k!=0:
            for l in range(4):
              if l==0:
                continue
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
          elif j!=0 and k==2:
            for l in range(4):
              if l==0:
                continue
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
          else:
            for l in range(4):
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
        elif i==2:
          if j==1 and k==0:
            dp[m][i][j][k]=0
          else:
            for l in range(4):
              dp[m][i][j][k]+=dp[m-1][j][k][l]
            dp[m][i][j][k]%=mod
        elif i==3:
          for l in range(4):
            dp[m][i][j][k]+=dp[m-1][j][k][l]
          dp[m][i][j][k]%=mod
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=dp[n][i][j][k]
      ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
dp = [[[[0]*4 for _ in [0]*4] for _ in [0]*4] for _ in [0]*(N+1)]
dp[0][3][3][3] = 1
for i in range(1,N+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for k in range(4):
                    if (c2,c3,k) == (0,1,2) : continue
                    if (c2,c3,k) == (1,0,2) : continue
                    if (c2,c3,k) == (0,2,1) : continue
                    if (c1,c3,k) == (0,1,2) : continue
                    if (c1,c2,k) == (0,1,2) : continue
                    dp[i][c2][c3][k] += dp[i-1][c1][c2][c3]
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[-1][c1][c2][c3]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
INF = 10**9+7
N = int(input())
dp = [[[[0]*4 for k in range(4)] for j in range(4)] for i in range(110)]
# T:0 A:1 G:2 C:3
res = 0
dp[0][0][0][0]=1
for n in range(1,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (i,j,k)==(1,2,3):continue
                    if (i,j,k)==(2,1,3):continue
                    if (i,j,k)==(1,3,2):continue
                    if (j,k,l)==(1,2,3):continue
                    if (j,k,l)==(2,1,3):continue
                    if (j,k,l)==(1,3,2):continue
                    if (i,k,l)==(1,2,3):continue
                    if (i,j,l)==(1,2,3):continue
                    dp[n][j][k][l]+=dp[n-1][i][j][k]
                    dp[n][j][k][l]%=INF
for i in range(4):
    for j in range(4):
        for k in range(4):
            res = (res+dp[N][i][j][k])%INF
print(res)

Submission status: Accepted

Solution code:
N = int(input())
chars = 'AGCT'

dp = {}
for c1 in chars:
    for c2 in chars:
        for c3 in chars:
            dp[c1+c2+c3] = 1
dp['AGC'] = dp['ACG'] = dp['GAC'] = 0

def isValid(s):
    return not (s[1:] == 'AGC' or
                s[1:] == 'ACG' or
                s[1:] == 'GAC' or
                (s[0] == 'A' and s[3] == 'C' and 'G' in s[1:3]) )
	
for i in range(N-3):
    dp_new = {k:0 for k in dp}
    for k in dp:
      	for c in chars:
            if isValid(k+c):
                dp_new[k[1:]+c] += dp[k]
    dp = dp_new

print(sum([v for k,v in dp.items()]) % 1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC122 D
n = int(input())
mod = 10**9+7

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
#長さ0の文字列は1
#0,1,2(A,G,C)に関する制約しかないため
#Sは、TTTSと考えてもよい
dp[0][3][3][3] = 1

#swapしてAGCが発生しない文字列:=AGC,ACG,GAC,A?GC,AG?Cを含まない文字列
#A:=0,G:=1,C:=2,T:=3

#文字列の文字数
for i in range(n):
    #最後から1文字目
    for j in range(4):
        #最後から2文字目
        for k in range(4):
            #条件に当てはまるものがない場合
            if dp[i][j][k] == 0:
                continue
            #最後から3文字目
            for l in range(4):
                #新たに追加する文字
                for a in range(4):
                    #ダメな5条件をカット

                    #AGCの場合
                    if a == 2 and j == 1 and k == 0:continue
                    #GACの場合
                    if a == 2 and j == 0 and k == 1:continue
                    #ACGの場合
                    if a == 1 and j == 2 and k == 0:continue
                    #A?GCの場合
                    if a == 2 and j == 1 and l == 0:continue
                    #AG?Cの場合
                    if a == 2 and k == 1 and l == 0:continue

                    #ダメの条件を抜けると、aを足した文字列が作れる
                    dp[i+1][a][j][k] += dp[i][j][k][l]
                    dp[i+1][a][j][k] %= mod

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            #長さnの全通り回収
            ans += dp[n][j][k][l]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC122 D

#条件を満たさないものは以下の5通りで追加する文字列+3文字を見れば決まる
#ACG,GAC,AGC,A?GC,AG?C
n = int(input())
#メモ化再帰
memo = [{} for i in range(n+1)]
mod = 10**9 + 7

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
    #AGCTを1文字ずつ追加してみる
    for c in 'AGCT':
        #cを追加したときにTrue(不適でない)なら
        if ok(last3 + c):
            #現在位置を1つ進めて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:
mod = 10 ** 9 + 7
n = int(input())

import sys
sys.setrecursionlimit(100000)

memo = {}
def ok(last4):
    if 'AGC' in last4:
        return False
    if last4[:3] == 'ACG' or last4[:3] == 'GAC':
        return False
    if last4[1:] == 'ACG' or last4[1:] == 'GAC':
        return False
    if last4[0] == 'A' and last4[2:] == 'GC':
        return False
    if last4[:2] == 'AG' and last4[3] == 'C':
        return False
    return True

def dfs(h, last3):
    if (h, last3) in memo:
        return memo[h, last3]
    # 停止条件
    if h == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3+c):
            ret = (ret + dfs(h+1, last3[1:]+c)) % mod
    memo[h, last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
N = int(input())

def concat(li):
  return ''.join([str(l) for l in li])

import itertools
def init_dp(n):
  dp = {}
  for s in itertools.product(['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T']):
    st = concat(s)
    if check3(st) == 0:
        dp[st] = n
  return dp

def check3(s):
  s1 = s
  s2 = s[0] + s[2] + s[1]
  s3 = s[1] + s[0] + s[2]
  if 'AGC' in '_'.join([s1, s2, s3]):
  	return 1
  return 0

def check4(s):
  s1 = s
  s2 = s[1] + s[0] + s[2] + s[3]
  s3 = s[0] + s[2] + s[1] + s[3]
  s4 = s[0] + s[1] + s[3] + s[2]
  if 'AGC' in '_'.join([s1, s2, s3, s4]):
  	return 1
  return 0
  
def update_dp(dp, next_dp, k, s):
  next4 = k + s  
  if check4(next4) == 0:
	  next_dp[next4[1:]] += dp[k]
  return next_dp

dp = init_dp(1)
for i in range(3, N):
  next_dp = init_dp(0)
  for k in dp.keys():
    for s in ['A', 'G', 'C', 'T']:
      next_dp = update_dp(dp, next_dp, k, s)
  dp = next_dp.copy()

mx = 10**9 + 7
ans = 0
for k in dp.keys():
  ans += dp[k] 
  ans %= mx
print(ans)

Submission status: Accepted

Solution code:
lo = int(input())
ngl = ["AGC", "ACG", "GAC", "AAGC", "AGGC", "ATGC", "ACGC", "AGAC", "AGGC", "AGTC", "AGCC"]
memo = {}


def ac(s, dep):
    if s == "":
        rv = 0
        for sv in "AGCT":
            rv += ac(s + sv, dep+1)
        return rv % (10 ** 9 + 7)
    else:
        if len(s) == lo:
            if chs(s):
                return 1
            else:
                return 0
        else:
            if len(s) >= 4:
                if chs(s):
                    if (s[-3:] + ":" + str(dep)) in memo:
                        return memo.get(s[-3:] + ":" + str(dep))
                    else:
                        rv = 0
                        for sv in "AGCT":
                            rv += ac(s + sv, dep+1)
                        memo[s[-3:] + ":" + str(dep)] = rv
                        return rv % (10 ** 9 + 7)
                else:
                    return 0
            else:
                rv = 0
                for sv in "AGCT":
                    rv += ac(s + sv, dep+1)
                return rv % (10 ** 9 + 7)


def chs(s):
    for ng in ngl:
        if ng in s:
            return False
    return True


print(ac("", 0))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

"""
directly out
*ag c
indirectly

*ga c
*ac g
a*g c
ag* c

a =0
c =1
g = 2
t = 3
"""

l = ["a","g","c","t"]
bef = {"a":1,"g":1,"c":1,"t":1}
d = {}
m = {}

for i in range(4):
    for j in range(4):
        for k in range(4):
            temp = l[i]+l[j]+l[k]
            d[temp] = 1
d["agc"] = 0
d["acg"] = 0
d["gac"] = 0





for key in d.keys():
    if key[1:] == "ag":
        m[key] = {key[1:]+"a":1,key[1:]+"g":1,key[1:]+"c":0,key[1:]+"t":1}
    elif key[1:] == "ga":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[1:] == "ac":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 0, key[1:] + "c": 1, key[1:] + "t": 1}
    elif key[0] == "a" and key[2] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    elif key[0] == "a" and key[1] == "g":
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 0, key[1:] + "t": 1}
    else:
        m[key] = {key[1:] + "a": 1, key[1:] + "g": 1, key[1:] + "c": 1, key[1:] + "t": 1}

mod = 10**9 +7
for i in range(n-3):
    buf = {}
    for i in range(4):
        for j in range(4):
            for k in range(4):
                temp = l[i] + l[j] + l[k]
                buf[temp] = 0
    for key in d.keys():
        for to in m[key].keys():
            buf[to] += d[key]*m[key][to]
            buf[to] = buf[to]%mod
    d = buf

ans = 0
for key in d.keys():
    ans += d[key]
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
dp = [[[[0 for k in range(4)]
           for j in range(4)]
           for i in range(4)]
           for m in range(n + 1)]
T = 0
A = 1
G = 2
C = 3
MOD = 10 ** 9 + 7

dp[0][T][T][T] = 1
for m in range(n):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for c in range(4):
                    # ijkc
                    #  AGC
                    # A_GC
                    #  GAC
                    #  ACG
                    # AG_C
                    if            j == A and k == G and c == C: continue
                    if i == A            and k == G and c == C: continue
                    if            j == G and k == A and c == C: continue
                    if            j == A and k == C and c == G: continue
                    if i == A and j == G            and c == C: continue
                    dp[m + 1][j][k][c] += dp[m][i][j][k]
                    dp[m + 1][j][k][c] %= MOD

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9+7
#末尾の4文字が *AGC,*ACG,*GAC,A*GC,AGTCのいずれにもならない
#dp
dp = [[0]*4 for i in range(100)]
#0~3 = A,C,G,T

for i in range(n):
    if i == 0:
        for j in range(4):
            dp[i][j] = 1
    elif i == 1:
        for j in range(4):
            dp[i][j] = sum(dp[i-1])
    elif i == 2:
        for j in range(4):
            if j == 0 or j == 3:
                dp[i][j] = sum(dp[i-1])
            if j == 1:
                dp[i][j] = sum(dp[i-1]) - 2
            if j == 2:
                dp[i][j] = sum(dp[i-1]) - 1
    else:
        for j in range(4):
            if j == 0 or j == 3:
                dp[i][j] = sum(dp[i-1])
            if j == 1:
                dp[i][j] = sum(dp[i-1]) - dp[i-2][0] - dp[i-2][2]-dp[i-3][0]*3
            if j == 2:
                dp[i][j] = sum(dp[i-1]) - (sum(dp[i-3]) - dp[i-3][2])        
print(sum(dp[n-1])%MOD)

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-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:
mod = 10 ** 9 + 7


def is_ok(last4):
    for i in range(4):
        t = list(last4)
        if i != 3:
            t[i], t[i + 1] = t[i + 1], t[i]
            # i == 0,1,2 : 隣接交換
            # i == 3 : 交換なし
        if 'AGC' in ''.join(t):
            return False
    return True


def dfs(length, last3):
    # last3文字はAGCではない文字列
    if last3 in m[length]:
        return m[length][last3]

    if length == n:
        return 1

    res = 0
    for c in 'ACGT':
        # 末尾につける文字の候補c
        if is_ok(last3 + c):
            res += dfs(length + 1, last3[1:] + c)
            res %= mod

    m[length][last3] = res
    return res


n = int(input())
m = [{} for _ in range(n + 1)]
print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
A = [0, 1, 4]
G = [0, 1, 4]
C = [0, 1, 4]
T = [0, 1, 4]
AG = [0, 0, 1]
GA = [0, 0, 1]
AC = [0, 0, 1]
AT = [0, 0, 1]
AGG = [0, 0, 0]
ATG = [0, 0, 0]
AGT = [0, 0, 0]
for i in range(2, 100):
	A.append(A[i]+G[i]+C[i]+T[i])
	G.append(A[i]+G[i]+C[i]+T[i]-AC[i])
	C.append(A[i]+G[i]+C[i]+T[i]-AG[i]-GA[i]-AGG[i]-ATG[i]-AGT[i])
	T.append(A[i]+G[i]+C[i]+T[i])
	AG.append(A[i])
	GA.append(G[i])
	AC.append(A[i]-GA[i])
	AT.append(A[i])
	AGG.append(AG[i])
	ATG.append(AT[i])
	AGT.append(AG[i])
N = int(input())
print((A[N]+G[N]+C[N]+T[N])%(10**9+7))

Submission status: Accepted

Solution code:
N=int(input())
d={}
mod=10**9+7
from itertools import product
import re
for t in product('ATGC',repeat=3):
    s=''.join(t)
    d[s]=[0]*(N-2)
    d[s][0]=0 if s in ['AGC','ACG','GAC'] else 1
p=re.compile('.AGC|.ACG|.GAC|A.GC|AG.C')
for i in range(N-3):
    for t in product('ATGC',repeat=3):
        for c in 'ATGC':
            s=''.join(t)+c
            if p.search(s)==None:
                d[s[1:]][i+1]=(d[s[1:]][i+1]+d[s[:-1]][i])%mod
print(sum([i[-1] for i in d.values()])%mod)

Submission status: Accepted

Solution code:
# from https://atcoder.jp/contests/abc122/submissions/4932940


def main():
    n = int(input())
    MOD = 10 ** 9 + 7

    dpa = [0, 0, 1]
    dpc = [0, 0, 1]
    dpg = [0, 0, 1]
    dpt = [0, 0, 1]
    for i in range(2, n + 2):
        total = dpa[i] + dpc[i] + dpg[i] + dpt[i]
        if i == n + 1:
            break
        dpa.append(total)
        dpc.append(total - dpa[i-1] - dpg[i-1] - 3 * dpa[i-2])
        dpg.append(total - dpa[i-1] + dpg[i-2])
        dpt.append(total)
    print(total % MOD)


main()

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

def ok(S):
    for ng in ['AGC', 'GAC', 'ACG']:
        if S[1:] == ng or S[:3] == ng:
            return False
    if S[0] == 'A' and S[2:] == 'GC':
        return False
    if S[:2] == 'AG' and S[3] == 'C':
        return False
    return True


memo = {}
def find(i, prev):
    if (i, prev) in memo:
        return memo[(i, prev)]

    if i == N:
        return 1

    res = 0
    for c in 'ACGT':
        if ok(prev + c):
           res += find(i+1, prev[1:] + c)

    res %= 1000000007
    memo[(i, prev)] = res
    return res

print(find(0, 'TTT'))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    MOD = 10 ** 9 + 7
    note = [{} 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 note[cur]:
            return note[cur][last3]
        if cur == n:
            return 1
        ret = 0
        for c in 'ACGT':
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
                ret %= MOD
        note[cur][last3] = ret
        return ret

    print(dfs(0, 'TTT'))


main()

Submission status: Accepted

Solution code:
import re
import functools

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


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    return ret % MOD


print(dfs(0, 'TTT'))