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:
MOD = 10**9+7
n = int(input())
dp = [[[ [0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
A, C, G, T = 0, 1, 2, 3
dp[0][3][3][3] = 1
for i in range(1, n+1):
    for s in range(4):
        for t in range(4):
            for u in range(4):
                for v in range(4):
                    if any( x==(t, u, v) for x in ((A,G,C), (A,C,G), (G,A,C)) ) or any( (A,G,C)==x for x in ((s,u,v), (s,t,v)) ):
                        continue
                    dp[i][t][u][v] = ( dp[i][t][u][v]+dp[i-1][s][t][u] )%MOD
print( sum( dp[n][i][j][k] for i in range(4) for j in range(4) for k in range(4) )%MOD )

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=[]
for j in zt:
    if not j in ng:
        z.append(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   # if not z[i] in ng:
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            #if not z[k] in ng:
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)

Submission status: Accepted

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

a=[1,4,16]
g=[1,4,15]
c=[1,4,14]
t=[1,4,16]

for i in range(3,n):
  a.append((a[i-1]+g[i-1]+c[i-1]+t[i-1])%m)
  t.append((a[i-1]+g[i-1]+c[i-1]+t[i-1])%m)
  g.append((a[i-1]+g[i-1]+(c[i-1]-a[i-2]+g[i-3])+t[i-1])%m)
  c.append(((a[i-1]-g[i-2])+(g[i-1]-a[i-2]-2*a[i-3])+c[i-1]+(t[i-1]-a[i-3]))%m)

n=n-1

ans=a[n]+g[n]+c[n]+t[n]
print(ans%m)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
A = [1] * 64
A[6] = A[9] = A[33] = 0
for _ in range(N-3):
    B = [0] * 64
    for p in range(256):
        i = p >> 2
        j = p & 63
        b = ((i == 6) or (i == 9) or (i == 33)
            or (j == 6) or (j == 9) or (j == 33)
            or (p & 207 == 9) or (p & 243 == 33))
        if not b:
            B[j] = (B[j] + A[i]) % MOD
    A[:] = B[:]
res = 0
for a in A:
    res = (res + a) % MOD
print(res)

Submission status: Accepted

Solution code:
def tetra(x):
    ret = ""
    for _ in range(3):
        ret = str(x%4) + ret
        x = (x-x%4)//4
    return ret
n = int(input())
mod = 10**9+7
if n<=2:
    print(4**n)
    exit()
DP = [[0]*64 for i in range(n+1)]
for i in range(64):
    if tetra(i) not in ["023","032","203"]:
        DP[0][i] = 1
for i in range(1,n+1):
    for j in range(64):
        tj = tetra(j)
        jprelist = [j//4+l*16 for l in range(4)]
        for jprev in jprelist:
            tjp = tetra(jprev)
            if ((tjp[1:]  in ["02","20"] or tjp[:2] == "02" or tjp == "012")
                and (tj[2] == "3")) or (tjp[1:]  == "03" and tj[2] == "2"):
                continue
            else:            
                DP[i][j] = (DP[i][j]+DP[i-1][jprev])%mod
print(sum(DP[n-3])%mod)

Submission status: Accepted

Solution code:
N=int(input())
dp=[[[[0]*5 for i in range(5)] for j in range(5)] for k in range(N+1)]
dp[0][0][0][0]=1
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):
                    if i==1 and j==2 and l==3:continue
                    if i==1 and k==2 and l==3:continue
                    if j==1 and k==2 and l==3:continue
                    if j==2 and k==1 and l==3:continue
                    if j==1 and k==3 and l==2:continue
                    dp[n+1][j][k][l]+=dp[n][i][j][k]
                    dp[n+1][j][k][l]%=(10**9+7)

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

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
mod = 10 ** 9 + 7
dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
dp[0][0][0][0] = 1
# 1:A, 2:G, 3:C, 4:T
for t in range(n):
	for i, j, k, l in product(range(5), repeat=4):
		if not (l == 0 or (j == 1) & (k == 2) & (l == 3) or (i == 1) & (j == 2) & (l == 3) or (j == 1) & (k == 3) & (l == 2)
				  or (j == 2) & (k == 1) & (l == 3) or (i == 1) & (k == 2) & (l == 3)):
			dp[t + 1][j][k][l] += dp[t][i][j][k] % mod
ans = sum(dp[-1][i][j][k] % mod for i, j, k in product(range(1, 5), repeat=3)) % mod
print(ans)

Submission status: Accepted

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

A, G, C, T = 0, 1, 2, 3  # 文字を数字に割り当てる
# dp[n][最後の前の前の文字][最後の前の文字][最後の文字]:= 長さnも字列が何通り作れるか
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
# 禁止されている文字列は [AGC, GAC, ACG] と [A*GC, AG*C]
# 数字に対応させると[012, 102, 021] と [0*12, 01*2]
# 末尾の3文字 + 今見ている1文字の合計4文字だけを見ればよい
# 文頭のTが影響を与えることはないので初期化時にTを使ってもよい
dp[0][T][T][T] = 1
for n in range(N):
    for c0 in range(4):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    # 禁止のパターンならcontinue
                    if c1 == A and c2 == G and c3 == C: continue
                    if c1 == G and c2 == A and c3 == C: continue
                    if c1 == A and c2 == C and c3 == G: continue
                    if c0 == A and c1 == G and c3 == C: continue
                    if c0 == A and c2 == G and c3 == C: continue
                    # nの値を進めるとともに、末尾の3文字列
                    dp[n+1][c1][c2][c3] += dp[n][c0][c1][c2]
                    dp[n+1][c1][c2][c3] %= mod
ans = 0
for c0 in range(4):
    for c1 in range(4):
        for c2 in range(4):
            ans += dp[N][c0][c1][c2]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
CHARS = 'ACGT'

def pos(ch):
    return CHARS.index(ch)

def ok(s):
    if 'AGC' in s:
        return False
    l = list(s)
    for i in range(len(s) - 1):
        l[i], l[i + 1] = l[i + 1], l[i]
        if 'AGC' in ''.join(l):
            return False
        l[i], l[i + 1] = l[i + 1], l[i]
    return True

n = int(input())
#dp[i][a][b][a] - number of ways to construct a correct string of length n, ending in abc characters
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            if ok(a + b + c):
                dp[3][pos(a)][pos(b)][pos(c)] += 1
for i in range(4, n + 1):
    for a in CHARS:
        for b in CHARS:
            for c in CHARS:
                for d in CHARS:
                    if not ok(a + b + c + d):
                        continue
                    dp[i][pos(b)][pos(c)][pos(d)] += dp[i - 1][pos(a)][pos(b)][pos(c)]
                    dp[i][pos(b)][pos(c)][pos(d)] %= MOD
ret = 0
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            ret += dp[n][pos(a)][pos(b)][pos(c)]
            ret %= MOD
print(ret)

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
#AAA AAC AAG AAT ACA ACC ACG! ACT AGA AGC! AGG AGT ATA ATC ATG ATT
#0   1   2   3   4   5   6    7   8   9    10  11  12  13  14  15

#CAA CAC CAG CAT CCA CCC CCG CCT CGA CGC CGG CGT CTA CTC CTG CTT
#16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31

#GAA GAC! GAG GAT GCA GCC GCG GCT GGA GGC GGG GGT GTA GTC GTG GTT
#32  33   34  35  36  37  38  39  40  41  42  43  44  45  46  47

#TAA TAC TAG TAT TCA TCC TCG TCT TGA TGC TGG TGT TTA TTC TTG TTT
#48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
ans=[1]*64
ans[6]=0
ans[9]=0
ans[33]=0
for i in range(N-3):
  val=[0]*64
  for j in range(16):
    for k in range(4):
      val[4*j+k]=(ans[j]+ans[j+16]+ans[j+32]+ans[j+48])%MOD
  val[6]=0
  val[9]=0
  val[33]=0
  val[41]=(val[41]-ans[10])%MOD
  val[45]=(val[45]-ans[11])%MOD
  val[57]=(val[57]-ans[14])%MOD
  ans=val
print(sum(ans)%MOD)

Submission status: Accepted

Solution code:
n = int(input())
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  # 先頭の方はチェック済み
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])[-4:]
  return v
 
memo = {}  # 今の長さと最新4つだけメモする
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]
 
print(f(0, '') % int(1e9+7))

Submission status: Accepted

Solution code:
n = int(input())
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  # 先頭の方はチェック済み
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v

memo = {}  # 今の長さと最新4つだけメモする
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print(f(0, '') % int(1e9+7))

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
hoges = []
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  # for k in range(max(1, 0), len(currents)):
  for k in range(max(1, len(currents) - 3), len(currents)):
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v
memo = {}
ng_memo = {} # 後ろ4つだけ見ればNGわかる？
def f(index, currents):
  ng_key = currents[-4:]
  key = '%d:%s' % (index, currents[-4:])
  # print(key)
  if ng_key in ng_memo:
    return 0
  if key in memo:
    return memo[key]
  if ng(currents):
    ng_memo[key] = True
    return 0
  if index == n:
    return 1
  memo[key] = sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print(f(0, '') % int(1e9+7))

# 3:      61
# 4:     230
# 5:     865
# 6:    3247
# 7:   12185
# 8:   45719

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000)

n = int(input())
mod = 1000000007
memo = {}
def doit(n, a, b, c):
    if n == 0:
        return 1
    key = (n, a, b, c)
    if not key in memo:
        ret = (doit(n - 1, b, c, 'A') + doit(n - 1, b, c, 'T')) % mod
        if (b != 'A' or c != 'C'):
            ret = (ret + doit(n - 1, b, c, 'G')) % mod
        if (b != 'A' or c != 'G') and (b != 'G' or c != 'A') and (a != 'A' or c != 'G')  and (a != 'A' or b != 'G'):
            ret = (ret + doit(n - 1, b, c, 'C')) % mod
        memo[key] = ret
    return memo[key]
print(doit(n, '', '', ''))

Submission status: Accepted

Solution code:
import os
import re
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())


def is_ok(s):
    ok = True
    for ng in ['AGC', 'GAC', 'ACG']:
        ok &= ng not in s
    ok &= not re.match(r'A.GC', s)
    ok &= not re.match(r'AG.C', s)
    return ok


# 最後が s である文字の数
dp = [defaultdict(int) for _ in range(N)]
for c in 'AGCT':
    for d in 'AGCT':
        for e in 'AGCT':
            if is_ok(c + d + e):
                dp[2][c + d + e] = 1

for i in range(3, N):
    for k in dp[i - 1].keys():
        for c in 'AGCT':
            if is_ok(k + c):
                dp[i][k[-2:] + c] += dp[i - 1][k]
                dp[i][k[-2:] + c] %= MOD

print(sum(dp[-1].values()) % MOD)

Submission status: Accepted

Solution code:
def solve():
    MOD = 10**9+7
    N = int(input())
    
    dp = [[0 for _ in range(4)] for _ in range(N+1)]
    dp[1] = [1, 1, 1, 1]
    
    for i in range(2, N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1])
            dp[i][j] %= MOD
        dp[i][1] -= dp[i-2][0] + dp[i-2][2]
        dp[i][2] -= dp[i-2][0]
        if 3 <= i:
            dp[i][1] -= dp[i-3][0] * 3
            dp[i][2] += dp[i-3][2]
    
    ans = sum(dp[N]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
cs = 'ATGC'
ng = [
  'AGC',
  'GAC',
  'ACG',
  'AGGC',
  'ATGC',
  'ACGC',
  'AGAC',
  'AGTC'
]

mod = 10**9 + 7
d = defaultdict(int)
for c1 in cs:
  for c2 in cs:
    for c3 in cs:
      s = c1 + c2 + c3
      if s not in ng:
        d[s] += 1
for i in range(3, n):
  nd = defaultdict(int)
  for key in d.keys():
    for c in cs:
      cn = key[1:3] + c
      cn4 = key + c
      if cn not in ng and cn4 not in ng:
        nd[cn] = (nd[cn] + d[key]) % mod
  d = nd
print(sum([d[key] for key in d]) % mod)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

N = inp()
#dp[n][i][j][k] 全体でn文字あってn-1,n-2,n-3文字目がk,j,iであるパターン数
#0:A 1:C 2:G 3:T
dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+5)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i,j,k) == (0,2,1) or (i,j,k) == (0,1,2) or (i,j,k) == (2,0,1):
                continue
            dp[3][i][j][k] = 1
# pprint.pprint(dp)
if N == 3:
    print(61)
    quit()
for n in range(4,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (j,k,l) == (0,2,1) or (i,k,l) == (0,2,1) or (i,j,l) == (0,2,1) or (j,k,l) == (2,0,1) or (j,k,l) == (0,1,2):
                        continue
                    dp[n][j][k][l] += dp[n-1][i][j][k]
                    dp[n][j][k][l] %= mod
res = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            res += dp[N][i][j][k]
            res %= mod
print(res)
# pprint.pprint(dp)

Submission status: Accepted

Solution code:
# DPをつかった解放を全然思いつけなかった
# 解説動画がわかりやすい

mod = 1000000007
N = int(input())

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

# 全部TのときはOK
dp[0][3][3][3] = 1

# 文字の数
for n in range(N):
  # 後ろから1文字目
  for c1 in range(4):
    # 後ろから2文字目
    for c2 in range(4):
      # 後ろから3文字目
      for c3 in range(4):
        # 該当するものがないとき
        if dp[n][c1][c2][c3] == 0: continue

        # 新しく追加する文字
        for a in range(4):
          # AGCに当てはまる文字
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

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

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

print(ans % mod)

Submission status: Accepted

Solution code:

mod = 1000000007
N = int(input())

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

# 全部TのときはOK
dp[0][3][3][3] = 1

# 文字の数
for n in range(N):
  # 後ろから1文字目
  for c1 in range(4):
    # 後ろから2文字目
    for c2 in range(4):
      # 後ろから3文字目
      for c3 in range(4):
        # 該当するものがないとき
        if dp[n][c1][c2][c3] == 0: continue

        # 新しく追加する文字
        for a in range(4):
          # AGCに当てはまる文字
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]
          dp[n+1][a][c1][c2] %= mod

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

Submission status: Accepted

Solution code:
def main():
    '''
    A => 0
    C => 1
    G => 2
    T => 3
    '''
    N = int(input())
    MOD = 10 ** 9 + 7
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(105)]
    
    dp[0][3][3][3] = 1

    for n in range(N):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for new in range(4):
                        if j == 0 and k == 2 and new == 1:
                            continue
                        if j == 2 and k == 0 and new == 1:
                            continue
                        if j == 0 and k == 1 and new == 2:
                            continue
                        if i == 0 and k == 2 and new == 1:
                            continue
                        if i == 0 and j == 2 and new == 1:
                            continue

                        dp[n+1][j][k][new] += dp[n][i][j][k]
                        dp[n+1][j][k][new] %= 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)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0 for _ in range(4**4)] for _ in range(N-3)]
cau = [6, 9, 24, 25, 26, 27, 33, 36, 37, 38, 39, 41, 45, 57, 70, 73, 97, 132, 133, 134, 135, 137, 161, 198, 201, 225]
if N==3:
    print(61)
    exit()

for i in range(4**4):
    dp[0][i] = 1 - cau.count(i)
for i in range(N-4):
    for j in range(4**4):
        if j in cau:
            dp[i+1][j] = 0
            continue
        tgt = 4*(j%(4**3))
        tgt_list = [tgt+i for i in range(4) if tgt+i not in cau]
        for elem in tgt_list:
            dp[i+1][j] += dp[i][elem]
        dp[i+1][j] = dp[i+1][j]%(10**9+7)
print(sum(dp[N-4])%(10**9+7))
"""
# calc cau
res = [[] for _ in range(8)]
for j in range(4**4):
    j1 = j//(4**3)
    j2 = j%(4**3)//(4**2)
    j3 = j%(4**2)//4
    j4 = j%4
    #res = 0
    if j2==0 and j3==2 and j4==1:
        res[0].append(j)
    if j1==0 and j3==2 and j4==1:
        res[1].append(j)
    if j1==0 and j2==2 and j4==1:
        res[2].append(j)
    if j2==2 and j3==0 and j4==1:
        res[3].append(j)
    if j2==0 and j3==1 and j4==2:
        res[4].append(j)
    if j1==0 and j2==2 and j3==1:
        res[5].append(j)
    if j1==2 and j2==0 and j3==1:
        res[6].append(j)
    if j1==0 and j2==1 and j3==2:
        res[7].append(j)
print(res)
"""

Submission status: Accepted

Solution code:
import numpy as np

MOD = 10**9+7

N = int(input())
DP = [{} for i in range(N+1)]

out = []
AGCT = []
for i in "AGCT":
    for j in "AGCT":
        for k in "AGCT":
            for l in "AGCT":
                str = [i,j,k,l]
                AGCT.append(''.join(str))
                if ''.join(str).count("AGC") >= 1:
                    out.append(''.join(str))
                    continue
                for x  in range(3):
                    hoge = str.copy()
                    hoge[x], hoge[x+1] = hoge[x+1], hoge[x]
                    if ''.join(hoge).count("AGC") >= 1:
                        out.append(''.join(str))
                        break
DP[0]["TTTT"] = 1
for i in range(N):
    for key in AGCT:
        DP[i+1][key] = 0
    for key in DP[i]:
        for c in "AGCT":
            DP[i+1][(key+c)[-4:]] += DP[i][key]
            DP[i+1][(key+c)[-4:]] %= MOD
    for key in out:
        DP[i+1][key] = 0
ans = 0
for i in DP[-1]:
    ans += DP[-1][i]
    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 = 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 for a in range(4)] for b in range(4)] for c in range(4)] for i in range(100+1)]
#A,G,C,T: 0,1,2,3

mod = 10**9 + 7

for a in range(4):
  for b in range(4):
    for c in range(4):
      dp[3][a][b][c] = 1
dp[3][0][1][2] = 0
dp[3][0][2][1] = 0
dp[3][1][0][2] = 0
#print(dp[3])

for i in range(4,100+1):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for j in range(4):
          dp[i][a][b][c] += dp[i-1][j][a][b]
          if b == 1 and c == 2 and j == 0:
            dp[i][a][b][c] -= dp[i-1][j][a][b]
          if a == 1 and c == 2 and j == 0:
            dp[i][a][b][c] -= dp[i-1][j][a][b]
          if a == 1 and b == 1 and c == 2 and j == 0:
            dp[i][a][b][c] += dp[i-1][j][a][b]
          dp[i][a][b][c] %= mod
  dp[i][0][1][2] = 0
  dp[i][1][0][2] = 0
  dp[i][0][2][1] = 0

answer = 0
for a in range(4):
  for b in range(4):
    for c in range(4):
      answer += dp[N][a][b][c]
answer %= mod
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
mask = 0b111111
mod = 10**9+7
dp = [[0]*4**3 for _ in range(n+1)]
dp[0][63] = 1
for i in range(n):
  for bit in range(4**3):
    for x in range(4):
      nb = bit<<2&63|x
      f = nb == 6 or nb == 9 or nb == 33
      f |= bit&51 == 2 and x == 1
      f |= bit&60 == 8 and x == 1
      if f:
        continue
      dp[i+1][nb] += dp[i][bit]
      dp[i+1][nb] %= mod
print(sum(dp[-1])%mod)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()

# dp[i][j][k][l] := i文字目まで見て、3文字前がj、2文字前がk、1文字前がlである通り数
dp = list4d(N+1, 5, 5, 5, 0)
dp[0][0][0][0] = 1

# A: 1, C: 2, G: 3, T: 4
for i in range(N):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                # A,C,G,Tへの遷移
                for m in range(1, 5):
                    # AGC
                    if k == 1 and l == 3 and m == 2:
                        continue
                    # ACG
                    elif k == 1 and l == 2 and m == 3:
                        continue
                    # GAC
                    elif k == 3 and l == 1 and m == 2:
                        continue
                    # A?GC
                    elif j == 1 and l == 3 and m == 2:
                        continue
                    # AG?C
                    elif j == 1 and k == 3 and m == 2:
                        continue
                    dp[i+1][k][l][m] += dp[i][j][k][l]
                    dp[i+1][k][l][m] %= MOD
ans = 0
for j in range(5):
    for k in range(5):
        for l in range(5):
            ans += dp[N][j][k][l]
            ans %= MOD
print(ans)

Submission status: Accepted

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

# In[1]:


N = int(input())


# In[14]:


# N = 4
MOD = 10 ** 9 + 7


# In[15]:


char = ['A', 'C', 'G', 'T']
S = [c1 + c2 + c3 for c1 in char for c2 in char for c3 in char]
S


# In[16]:


ng3 = ['AGC', 'GAC', 'ACG']
ng4 = [c + ng for c in char for ng in ng3] + [ng + c for c in char for ng in ng3] + ['A' + c + 'GC' for c in char] + ['AG' + c + 'C' for c in char]
ng4 = set(ng4)
ng4


# In[17]:


dict1 = {s: 1 if s not in ng3 else 0 for s in S}


# In[18]:


for _ in range(N - 3):
    dict2 = {}

    for s in S:
        val = 0
        for c in char:
            if c + s not in ng4:
                val = (val + dict1[c + s[:2]]) % MOD
        dict2[s] = val
    dict1 = dict2


# In[19]:


ans = 0
for s in dict1.keys():
    ans = (ans + dict1[s]) % MOD
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
def p_d():
    n = int(input())
    mod = 10 ** 9 + 7
    # dp[i][j][k][l]: 長さiの文字列でi-2番目がj、i-1番目がk、i番目がlであるものの総数
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if j == 1 and k == 2 and l == 3:
                    continue
                if j == 2 and k == 1 and l == 3:
                    continue
                if j == 1 and k == 3 and l == 2:
                    continue
                dp[3][j][k][l] = 1
    for i in range(4, n + 1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == 1 and k == 2 and l == 3:
                            continue
                        if j == 2 and k == 1 and l == 3:
                            continue
                        if j == 1 and k == 3 and l == 2:
                            continue
                        if m == 1 and k == 2 and l == 3:
                            continue
                        if m == 1 and j == 2 and l == 3:
                            continue
                        dp[i][j][k][l] += dp[i - 1][m][j][k]
                        dp[i][j][k][l] %= mod

    ans = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                ans += dp[n][j][k][l]
                ans %= mod
    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
N = int(input())
dp = [ [] for _ in range(N+1)] 
mod = 10**9 +7

for s_len in range(N+1):
    for c1 in range(4):
        dp[s_len].append([])
        for c2 in range(4):
            dp[s_len][c1].append([0,0,0,0])
dp[0][3][3][3] = 1            

for s_len in range(N):
    for c4 in range(4):
        for c3 in range(4):
            for c2 in range(4):
                if dp[s_len][c2][c3][c4] == 0:
                    continue
                for c1 in range(4):
                    if c3 == 0 and c2 == 1 and c1 == 2:
                        continue
                    if c3 == 1 and c2 == 0 and c1 == 2:
                        continue
                    if c3 == 0 and c2 == 2 and c1 == 1:
                        continue
                    if c4 == 0 and c2 == 1 and c1 == 2:
                        continue
                    if c4 == 0 and c3 == 1 and c1 == 2:
                        continue
                    dp[s_len+1][c1][c2][c3] += dp[s_len][c2][c3][c4]
                    current_num = dp[s_len][c2][c3][c4]
                    dp[s_len+1][c1][c2][c3] = dp[s_len+1][c1][c2][c3]%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 = ans%mod
print(ans)

Submission status: Accepted

Solution code:
def solve():
    from functools import lru_cache

    mod = 10 ** 9 + 7

    def is_ok(last4: str) -> bool:
        if 'AGC' in last4:
            return False
        for j in range(3):
            t = list(last4)
            t[j], t[j + 1] = t[j + 1], t[j]
            if 'AGC' in ''.join(t):
                return False
        return True

    @lru_cache(maxsize=None)
    def dfs(curr: int = 0, last3: str = 'XXX'):
        ret = 0
        if curr == n:
            return 1
        for c in 'ACGT':
            last4 = last3 + c
            if is_ok(last4):
                ret += dfs(curr + 1, last4[1:])
        return ret % mod

    n = int(input())
    print(dfs())


solve()

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
dp[0][0][0][0] = 1
# 0 -> T
# 1 -> C
# 2 -> G
# 3 -> A

def chk(s):
# NG Case : AG*C A*GC *ACG *GAC *AGC
  if   s[0] == 3 and s[1] == 2 and s[3] == 1: return False
  elif s[0] == 3 and s[2] == 2 and s[3] == 1: return False
  elif s[1] == 3 and s[2] == 1 and s[3] == 2: return False
  elif s[1] == 2 and s[2] == 3 and s[3] == 1: return False
  elif s[1] == 3 and s[2] == 2 and s[3] == 1: return False
  else: return True

def dfs(c, j, k, l):
  for m in range(4):
    if chk([j, k, l, m]):
      dp[c][k][l][m] += dp[c-1][j][k][l]

for i in range(1, n+1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        dfs(i, j, k, l)

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:
#18:29
n = int(input())
mod = 10 ** 9 + 7
now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
now[3][3][3] = 1
#print(part)
boo = [[0,0,1,2],[1,0,1,2],[2,0,1,2],[3,0,1,2],
       [0,0,1,2],[0,1,1,2],[0,2,1,2],[0,3,1,2],
       [0,1,0,2],[0,1,1,2],[0,1,2,2],[0,1,3,2],
       [0,1,0,2],[1,1,0,2],[2,1,0,2],[3,1,0,2],
       [0,0,2,1],[1,0,2,1],[2,0,2,1],[3,0,2,1]]
#print(now)
for i in range(n):
  last = now
  now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
  #print(i,'l',last)
  #print(i,'n',now)
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          if [i,j,k,l] not in boo:
            now[j][k][l] += last[i][j][k]
            now[j][k][l] %= mod
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += now[i][j][k]
      ans %= mod
#print(last)
#print(now)
print(ans)