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())

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

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


for L in range(N):
    for i in range(4):
        
        for j in range(4):
        
            for k in range(4):
                if (dp[L][i][j][k]==0): continue
                for a in range(4):
                    if (a == 2 and i == 1 and j == 0):    continue
                    if (a == 2 and i == 0 and j == 1):    continue
                    if (a == 1 and i == 2 and j == 0):    continue
                    if (a == 2 and i == 1 and k == 0):    continue
                    if (a == 2 and j == 1 and k == 0):    continue
                    
                    dp[L+1][a][i][j] += dp[L][i][j][k]
                    dp[L+1][a][i][j] %= modd
  
ans = 0         
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= modd
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
def to_bit(num,digit = 3,N = 4):
    bit = [0] * digit
    for i in range(digit):
        bit[i] = num % N
        num = int((num - (num % N)) / N)
    bit[0],bit[2] = bit[2],bit[0] 
    return bit

DP_map = [[0] * 64 for _ in range(100)]
'''
A = 0
C = 1
G = 2
T = 3

NG in 3 char
AGC = 0 * 16 + 2 * 4 + 1 * 1 = 9
ACG = 0 * 16 + 1 * 4 + 2 * 1 = 6
GAC = 2 * 16 + 0 * 4 + 1 * 1 = 33
'''
DP_map[0] = [1] * 64
DP_map[0][6] = 0
DP_map[0][9] = 0
DP_map[0][33] = 0

C_NG = [9,33]
for i in range(N - 2):
    for j in range(64):
        bit = to_bit(j)
        now = DP_map[i][j]
        added_A = bit[1] * 16 + bit[2] * 4 + 0
        added_C = bit[1] * 16 + bit[2] * 4 + 1
        added_G = bit[1] * 16 + bit[2] * 4 + 2
        added_T = bit[1] * 16 + bit[2] * 4 + 3
        DP_map[i + 1][added_A] = (DP_map[i + 1][added_A] + now) % (int(1e9 + 7))
        DP_map[i + 1][added_T] = (DP_map[i + 1][added_T] + now) % (int(1e9 + 7))
        if added_G != 6:
            DP_map[i + 1][added_G] = (DP_map[i + 1][added_G] + now) % (int(1e9 + 7))

        if (added_C not in C_NG) and (bit[0] != 0 or (bit[2] != 2 and bit[1] != 2)):
            DP_map[i + 1][added_C] = (DP_map[i + 1][added_C] + now) % (int(1e9 + 7))


#print(DP_map[1])
print(sum(DP_map[N-3]) % (int(1e9 + 7)))

Submission status: Accepted

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

def check(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 D[cur]:
        return D[cur][last3]
    if cur == N:
        return 1
    res = 0
    for c in 'ACGT':
        if check(last3 + c):
            res = (res + dfs(cur + 1, last3[1:] + c)) % mod
    D[cur][last3] = res
    return res
    
print(dfs(0, '000'))

Submission status: Accepted

Solution code:
import re,functools as f;d=f.lru_cache(None)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print(d(int(input()),'TTT'))

Submission status: Accepted

Solution code:
# DPを用いて解く。
# 少し複雑なので、自分の解説と照らし合わせて読むこと。
MOD = 10**9+7
N = int(input())

# AGCT→0123として扱う

# dpテーブルの作成shape=(101, 3,3,3) #長さが0~100まで扱いたいため
import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype="int64")

dp[0, 3, 3, 3] = 1  # 解説放送流テクニカルな楽な初期化
# 末尾がc3,c2,c1で終わる長さlの文字列の通りの数を計算していく
# print(dp)
for l in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                # すでに条件を満たしていないのでスキップ(なくても多分平気)
                if dp[l, c3, c2, c1] == 0:
                    continue
                # 最後につける一文字を考える
                for a in range(4):
                    # あかん条件
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l + 1, c2, c1, a] += dp[l, c3, c2, c1] % MOD
                    dp[l + 1, c2, c1, a] %= MOD

print(dp[N, :, :, :].sum() % MOD)

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 'AGCT':
        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:
# DPを用いて解く。
# 少し複雑なので、自分の解説と照らし合わせて読むこと。
MOD = 10**9+7
N = int(input())

# AGCT→0123として扱う

# dpテーブルの作成shape=(101, 3,3,3) #長さが0~100まで扱いたいため
import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype="longlong")

dp[0, 3, 3, 3] = 1  # 解説放送流テクニカルな楽な初期化
# 末尾がc3,c2,c1で終わる長さlの文字列の通りの数を計算していく
# print(dp)
for l in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                # すでに条件を満たしていないのでスキップ(なくても多分平気)
                if dp[l, c3, c2, c1] == 0:
                    continue
                # 最後につける一文字を考える
                for a in range(4):
                    # あかん条件
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l + 1, c2, c1, a] += dp[l, c3, c2, c1] % MOD
                    dp[l + 1, c2, c1, a] %= MOD

print(dp[N, :, :, :].sum() % MOD)

Submission status: Accepted

Solution code:
import re,functools as f
@f.lru_cache(None)
def d(n,b):return n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7)
print(d(int(input()),'TTT'))

Submission status: Accepted

Solution code:
# DPを用いて解く。
# 少し複雑なので、自分の解説と照らし合わせて読むこと。
MOD = 10**9+7
N = int(input())

# AGCT→0123として扱う

# dpテーブルの作成shape=(101, 3,3,3) #長さが0~100まで扱いたいため
import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype=int)

dp[0, 3, 3, 3] = 1  # 解説放送流テクニカルな楽な初期化
# 末尾がc3,c2,c1で終わる長さlの文字列の通りの数を計算していく
# print(dp)
for l in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                # すでに条件を満たしていないのでスキップ(なくても多分平気)
                if dp[l, c3, c2, c1] == 0:
                    continue
                # 最後につける一文字を考える
                for a in range(4):
                    # あかん条件
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l + 1, c2, c1, a] += dp[l, c3, c2, c1] % MOD
                    dp[l + 1, c2, c1, a] %= MOD
                    # print('ok?')

print(dp[N, :, :, :].sum() % MOD)

Submission status: Accepted

Solution code:
N = int(input())
mod = 1000000000+7

import numpy as np
dp=np.zeros((N+1, 4, 4, 4), dtype=np.int64)

dp[0,3,3,3] = 1
for length in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[length, 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[length+1, a, c1, c2] += dp[length, c1, c2, c3] 
                    dp[length+1, a, c1, c2] %= mod
print(dp[N].sum()%mod)

Submission status: Accepted

Solution code:
from copy import deepcopy

N = int(input())

dp = [{}] * 4

mod = int(1e9 + 7)


def ok(wxyz):
    if wxyz[1:] == "AGC" or wxyz == "AAGC" or wxyz == "ACGC" or wxyz == "AGGC" or wxyz == "ATGC" \
            or wxyz[1:] == "GAC" or wxyz[1:] == "ACG" \
            or wxyz == "AGAC" or wxyz == "AGCC" or wxyz == "AGTC" or wxyz == "AGGC":
        return 0
    else:
        return 1

# 初期化
for x in ["A", "C", "G", "T"]:
    for y in ["A", "C", "G", "T"]:
        for z in ["A", "C", "G", "T"]:
            xyz = "{}{}{}".format(x, y, z)
            dp[3][xyz] = 1 * ok("P" + xyz)


# dp
for i in range(3, N):
    dp.append({})
    for x in ["A", "C", "G", "T"]:
        for y in ["A", "C", "G", "T"]:
            for z in ["A", "C", "G", "T"]:
                xyz = "{}{}{}".format(x, y, z)
                dp[i + 1][xyz] = 0

                for w in ["A", "C", "G", "T"]:
                    wxyz = "{}{}".format(w, xyz)
                    dp[i + 1][xyz] = (dp[i + 1][xyz] + deepcopy(dp[i][wxyz[:-1]]) * ok(wxyz)) % mod

# 結果出力
print(sum(dp[N].values()) % mod)

Submission status: Accepted

Solution code:
import re
import functools

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


@functools.lru_cache(maxsize=2**24)
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'))

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

Submission status: Accepted

Solution code:
import re

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


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 not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    ret = ret % 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 _ in range(n+1)]
def check(L4):
  for i in range(4):
    t = list(L4)
    if i > 0:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True
def dfs(d, L3):
  if L3 in memo[d]:
    return memo[d][L3]
  if d >= n:
    return 1
  ret = 0
  for L in list("ACGT"):
    L4 = L3 + L
    if check(L4):
      ret += dfs(d + 1, L4[1:]) 
    memo[d][L3] = ret
  return ret % p
    
  
  
print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
#!bin/python3
from sys import exit
def check(a, b, c):
	d = a + b + c;
	off = ['ACG', 'AGC', 'GAC']
	if d in off:
		return False
	else:
		return True


n = int(input())

base = 1000000007

c = ['A', 'C', 'G', 'T']
pre = {}
cur = {}
for ch1 in c:
	for ch2 in c:
		for ch3 in c:
			if check (ch1, ch2, ch3):
				pre[ch1 + ch2 + ch3] = 1
for i in range(4, n+1):
	for s in pre.keys():
		for ch in c:
			st = s + ch
			if check(st[1], st[2], st[3]) and st[0] + st[2] + st[3] != 'AGC' and st[0] + st[1] + st[3] != 'AGC':
				key = st[1] + st[2] + st[3]
				if key in cur:
					tmp = cur[st[1] + st[2] + st[3]]
					tmp = (tmp + pre[s]) % base
					cur[st[1] + st[2] + st[3]] = tmp
				else:
					cur[key] = pre[s] 
				#cur[st[1] + st[2] + st[3]] += pre[s]
	pre = cur
	cur = {} 

res = 0
for num in pre.values():
	res = (res + num) % base 

print(res)

Submission status: Accepted

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

def ok(last4):
  if "AGC" in last4:
    return False
  if "ACG" in last4:
    return False
  if "GAC" in last4:
    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(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 += dfs(cur+1, last3[1:] + c)
  memo[cur][last3] = ret
  return ret

print(dfs(0, "TTT") % 1000000007)

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:
dp=[[[[0]*4 for i in range(4)] for i in range(4)] for i in range(101)]
dp[0][3][3][3]=1
mod=10**9+7

for length in range(100):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if dp[length][c1][c2][c3]==0:
          continue
        for a in range(4):
          if c2==0 and c3==1 and a==2:
            continue
          if c2==1 and c3==0 and a==2:
            continue
          if c2==0 and c3==2 and a==1:
            continue
          if c1==0 and c3==1 and a==2:
            continue
          if c1==0 and c2==1 and a==2:
            continue
          dp[length+1][c2][c3][a]+=dp[length][c1][c2][c3]
          dp[length+1][c2][c3][a]%mod

n=int(input())
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 = int(input())
dp = [{} for i in range(0, n + 1)]

for i in "ATGC":
    for j in "ATGC":
        for k in "ATGC":
            dp[3][i + j + k] = 1
            
del dp[3]["AGC"]
del dp[3]["ACG"]
del dp[3]["GAC"]

def add(i, k, v):
    global dp
    if k in dp[i]:
        dp[i][k] += v
    else:
        dp[i][k] = v

for i in range(4, n + 1):
    for k in dp[i - 1].keys():
        for c in "ATGC":
            l3 = k[1:] + c
            l4 = k + c
            if l3 != "AGC" and l3 != "ACG" and l3 != "GAC" and l4 != "AGGC" and l4 != "AGTC" and l4 != "ATGC":
                add(i, l3, dp[i - 1][k])

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

Submission status: Accepted

Solution code:
n = int(input())

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

print(ans[n])

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
    print(cur, memo)
    return ret

print(dfs(0, 'TTT'))
"""

n, mod = int(input()), 10 ** 9 + 7
memo = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
memo[0][3][3][3] = 1
for length in range(n):
    for s3 in range(4):  # 一番最後の文字
        for s2 in range(4):  # 最後から2番目の文字
            for s1 in range(4):  # 最後から3番目の文字
                # if memo[length][s3][s2][s1] == 0: continue
                # 新しく追加する文字
                for s4 in range(4):
                    # ダメな条件の時はcontinue
                    if s4 == 2 and s3 == 1 and s2 == 0: continue
                    if s4 == 2 and s3 == 0 and s2 == 1: continue
                    if s4 == 1 and s3 == 2 and s2 == 0: continue
                    if s4 == 2 and s3 == 1 and s1 == 0: continue
                    if s4 == 2 and s2 == 1 and s1 == 0: continue
                    
                    memo[length + 1][s4][s3][s2] += memo[length][s3][s2][s1]
                    memo[length + 1][s4][s3][s2] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += memo[n][i][j][k]
            ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

MOD = 10 ** 9 + 7

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n)]

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

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

for i in range(3, n):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                dp[i][b][c][0] = (dp[i][b][c][0] + dp[i-1][a][b][c]) % MOD
                dp[i][b][c][3] = (dp[i][b][c][3] + dp[i-1][a][b][c]) % MOD
                if not (b == 0 and c == 2):
                    dp[i][b][c][1] = (dp[i][b][c][1] + dp[i-1][a][b][c]) % MOD
                if not ((b == 0 and c == 1) or (b == 1 and c == 0) or (a == 0 and (b == 1 or c == 1))):
                    dp[i][b][c][2] = (dp[i][b][c][2] + dp[i-1][a][b][c]) % MOD

#print(dp)

ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans = (ans + dp[n-1][a][b][c]) % MOD

print(ans)

Submission status: Accepted

Solution code:
def check(i, j, k, l):
    if (j, k, l) in {(0, 1, 2), (0, 2, 1), (1, 0, 2)} or (i, k, l) == (0, 1, 2) or (i, j, l) == (0, 1, 2):
        return False
    return True


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

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

    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[3][i][j][k] = 1

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

    for i in range(2, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if check(j, k, l, m):
                            dp[i+1][k][l][m] = (dp[i+1][k][l][m] + dp[i][j][k][l]) % MOD

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#内包表記の時は小さい成分から作っていく（新しい次元から）ls[i][j][k]←ココ
dp=[[[[0 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

#後ろから3文字を見るからn-3文字が最大
#forを回す時は一番新しい次元から作っていくls[i][j][k]←ココ
for length in range(n):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if dp[length][c1][c2][c3]==0: #もともと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[length+1][a][c1][c2]+=dp[length][c1][c2][c3]
          dp[length+1][a][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)

#dpで覚えておくべきindexの話
#①内包表記は先に入れたものが一番小さい箱
#②forを回す時は一番内側のループから値が入る
# a=[[[[0]*1 for i in range(2)] for i in range(3)] for i in range(4)]
# for i in range(4):
#   for j in range(3):
#     for k in range(2):
#       for l in range(1):
#         a[i][j][k][l]=i
#         print(a)

Submission status: Accepted

Solution code:
MOD = 1000000007

def violate(s):
    if s[1:] == 'GAC' or s[1:] == 'ACG' or s[1:] == 'AGC':
        return True
    if s[:3] == 'GAC' or s[:3] == 'ACG' or s[:3] == 'AGC':
        return True
    if s[0] == 'A' and s[2:] == 'GC':
        return True
    if s[:2] == 'AG' and s[3] == 'C':
        return True
    return False

def dfs(i, s):
    if s in memo[i]:
        return memo[i][s]
    if i == n:
        return 1
    ret = 0
    for c in 'ATGC':
        if not violate(s + c):
            ret = (ret + dfs(i + 1, s[1:] + c)) % MOD
    memo[i][s] = ret
    return ret

if __name__ == '__main__':
    n = int(input())
    memo = []
    for _ in range(n + 1):
        memo.append({})

    print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
import numpy as np

def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)]for _ in range(4)]for _ in range(4)]for _ in range(N+1)]
    #ndp = np.array(dp)
    #print(ndp.shape)
    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] %= 1000000007
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= 1000000007

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import re

# +C
xAG = re.compile('[ACGT]AG')
AxG = re.compile('A[ACGT]G')
xGA = re.compile('[ACGT]GA')
AGx = re.compile('AG[ACGT]')

# +G
xAC = re.compile('[ACGT]AC')

def func(N):
    d = {a+b+c:1 for a in 'ACGT' for b in 'ACGT' for c in 'ACGT' if a+b+c not in ('AGC','ACG','GAC')}
    for i in range(N-3):
        e = {a+b+c:0 for a in 'ACGT' for b in 'ACGT' for c in 'ACGT' if a+b+c not in ('AGC','ACG','GAC')}
        for k,v in d.items():
            if xAG.match(k) or AxG.match(k) or xGA.match(k) or AGx.match(k):
                n = 'AGT'
            elif xAC.match(k):
                n = 'ACT'
            else:
                n = 'ACGT'
                
            for i in n:
                e[k[1:]+i] += v
                    
        d = e
    print(sum(d.values())%(10**9+7))
    
    
func(N=int(input()))

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['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for (p3, p2, p1), n in pre.items():
            for cur in 'AGCT':
                new = p2 + p1 + cur
                if new in ['AGC', 'GAC', 'ACG']:
                    continue
                if p3 + p1 + cur == 'AGC':
                    continue
                if p3 + p2 + cur == 'AGC':
                    continue
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

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['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for (p3, p2, p1), n in pre.items():
            for cur in 'AGCT':
                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
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

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['000'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for old, n in pre.items():
            for cur in 'AGCT':
                new = old[-2:] + cur
                if new in ['AGC', 'GAC', 'ACG']:
                    continue
                if old[-3] + old[-1] + cur == 'AGC':
                    continue
                if old[:-1] + cur == 'AGC':
                    continue
                dp[new] = (dp[new] + n) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

# dp = np.ones((100, 4, 4, 4))

# tot = 0
# for x in itertools.product(*["ACGT"]*5):
#     x = "".join(x)
#     if "AGC" in x or "ACG" in x or "GAC" in x:
#         tot += 0
#     else:
#         tot += 1
# print(tot)

MOD = 1000000007  # type: int

# 例外をカウントすべきだ。
# AGCT = "AGCT"
# dp = [[0]*4 for _ in range(4) for _ in range()]
# buf = [1, 4, 16, 64]
# ans = [1, 4, 16, 61]


def solve(N: int):
    A, C, G, T = 0, 1, 2, 3
    dp = np.zeros((102, 4, 4, 4))
    dp[3] = np.ones((4, 4, 4))
    dp[3][A][G][C] = 0
    dp[3][G][A][C] = 0
    dp[3][A][C][G] = 0
    for i in range(3, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if k == A and l == G and m == C:
                            # print("AGC")
                            continue
                        elif k == G and l == A and m == C:
                            # print("GAC")
                            continue
                        elif k == A and l == C and m == G:
                            # print("ACG")
                            continue
                        elif j == A and k == G and m == C:
                            # print("AG*C")
                            continue
                        elif j == A and l == G and m == C:
                            # print("A*GC")
                            continue
                        else:
                            dp[i+1][k][l][m] += dp[i][j][k][l] % MOD
        # print(dp[i])
    print(int(np.sum(dp[N])) % MOD)
    # n = 3
    # while 1:
    #     if n == N:
    #         break
    #     dp.append(((dp[n]*4 % MOD)+(2*ans[n-2] %
    #                                 MOD)+(5*ans[n-3] % MOD)) % MOD)
    #     buf.append((buf[-1]*4) % MOD)
    #     ans.append((buf[-1]-dp[-1]) % MOD)
    #     n += 1
    # print(dp)
    # print(ans[-1])
    # print(MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()