Problem:


Score : 400 points

Problem Statement

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

The string does not contain characters other than A, C, G and T.

The string does not contain AGC as a substring.

The condition above cannot be violated by swapping two adjacent characters once.

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

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

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

3

Sample Output 1

61

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

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



Sample input:
3


Sample output:
61

Submission status: Accepted

Solution code:
N = int(input())


def is_valid(last_4):
    cand = [last_4]
    for i in range(3):
        cand.append(last_4[:i] + last_4[i + 1] + last_4[i] + last_4[i + 2:])

    for m in cand:
        if "AGC" in m:
            return False
    return True


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


def dfs(index, last_3):
    if last_3 in memo[index].keys():
        return memo[index][last_3]
    elif index == N:
        return 1
    else:
        s = 0
        for c in "AGCT":
            if is_valid(last_3 + c):
                s = (s + dfs(index + 1, last_3[1:] + c)) % mod
        memo[index][last_3] = s
        return s


print(dfs(0, "HHH"))

Submission status: Accepted

Solution code:
N=int(input())
M=10**9+7
dp={b:1 for b in 'ACGT'}
for i in range(N-1):
    dp_next={}
    for j in dp:
        for k in 'AGCT':
            elem=j[-3:]+k
            if elem[-3:] in ('AGC','GAC','ACG') or elem in ('AGGC','ATGC','ACGC','AGTC','AGGC'):
                continue
            else:
                dp_next.setdefault(elem,0)
                dp_next[elem]+=dp[j]
    dp=dp_next
print(sum(dp.values())%M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,input().split())

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

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

def dfs(last3="TTT",cnt=0):
    if last3 in memo[cnt]:
        return memo[cnt][last3]
    if cnt==n:
        return 1
    ans=0
    for i in "AGCT":
        last4 = last3+i
        if ok(last4):
            ans = ans+dfs(last4[1:],cnt+1)
    memo[cnt][last3]=ans
    return ans

print(dfs()%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
for i in range(N+1):
    if i == 0:
        memo[0]["****"] = 1
    elif i == 1:
        memo[1]["***A"] = 1
        memo[1]["***C"] = 1
        memo[1]["***G"] = 1
        memo[1]["***T"] = 1
    else:
        #print("aa")
        for c in 'ACGT':
            for j in memo[i-1]:
                #print(j)
                if ok(j[1:] + c):
                    if j[1:] + c not in memo[i]:               
                        memo[i][j[1:] + c] = memo[i-1][j] % MOD
                    else:
                        memo[i][j[1:] + c] += memo[i-1][j] % MOD

s = 0
for i in memo[N].values():
    s += i % MOD
print(s % MOD)

Submission status: Accepted

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

dp = [{} for _ in range(N + 1)]
s = ['A', 'C', 'G', 'T']
dp[0]['TTT'] = 1

for l in range(1, N + 1):
	for c1 in s:
		for c2 in s:
			for c3 in s:
				for c4 in s:
					tmp = c1 + c2 + c3 + c4
					tm = c1 + c2 + c3
					mp = c2 + c3 + c4
					if re.search(r'AGC', tmp):
						continue
					if re.search(r'GAC', tmp):
						continue
					if re.search(r'ACG', tmp):
						continue
					if re.search(r'A.GC', tmp):
						continue
					if re.search(r'AG.C', tmp):
						continue
					if tm in dp[l - 1].keys():
						if mp in dp[l].keys():
							dp[l][mp] += dp[l - 1][tm]
						else:
							dp[l][mp] = dp[l - 1][tm]

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

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:
			tmp = t[i]
			t[i] = t[i - 1]
			t[i - 1] = tmp
		if ''.join(t).count('AGC') >= 1:
			return False
	return True
			
def AGC(n, last3):
	if last3 in memo[n]:
		return memo[n][last3]
	if n == N:
		return 1
	ret = 0
	for c in 'AGCT':
		if ok(last3 + c):
			ret = (ret + AGC(n + 1, last3[1:] + c)) % MOD
		memo[n][last3] = ret
	return ret
	
print(AGC(0, 'TTT'))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(N+1)]

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

# Aを1、Gを2、Cを3、Tを4とする
# j は３つ前、kは２つ前、lは１つ前の情報
for i in range(N):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                # tは今の情報
                for t in range(1, 5):
                    if k == 1 and l == 2 and t == 3:
                        continue
                    if k == 2 and l == 1 and t == 3:
                        continue
                    if k == 1 and l == 3 and t == 2:
                        continue
                    if j == 1 and l == 2 and t == 3:
                        continue
                    if j == 1 and k == 2 and t == 3:
                        continue
                    dp[i+1][t][l][k] += dp[i][l][k][j]

sums = 0
for j in range(1, 5):
    for k in range(1, 5):
        for l in range(1, 5):
            sums += dp[N][l][k][j]

print(sums % (10**9 + 7))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(N+1)]

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

# Aを1、Gを2、Cを3、Tを4とする
# k は３つ前、jは２つ前、iは１つ前の情報
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                # tは今の情報
                for t in range(1, 5):
                    #AGC
                    if i == 2 and j == 1 and t == 3:
                        continue
                    #ACG
                    if i == 3 and j == 1 and t == 2:
                        continue
                    #GAC
                    if i == 1 and j == 2 and t == 3:
                        continue
                    #A?GC
                    if i == 2 and k == 1 and t == 3:
                        continue
                    #AG?C
                    if j == 2 and k == 1 and t == 3:
                        continue
                        
                    dp[n+1][t][i][j] += dp[n][i][j][k]

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

print(sums % (10**9 + 7))

Submission status: Accepted

Solution code:
import re
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N = int(input())
CHAR = ["A", "C", "G", "T"]
invalid_pattern = r'ACG|GAC|A.?GC|AG.?C'
invalid_reg = re.compile(invalid_pattern)

# 一個前の状態だけあればいいので、一次元のdpでいい
dp = {a+b+c: 1 if not invalid_reg.search(a+b+c)
      else 0 for a in CHAR for b in CHAR for c in CHAR}


# dpで、最後の３文字を記憶-> 新しく加える文字4通りで、加えても大丈夫なら遷移。
# loop iでは、i+4文字の長さの条件を満たす文字列の数を数える
for i in range(N-3):
    next_dp = {key: 0 for key, _ in dp.items()}
    for key, val in dp.items():
        for c in CHAR:
            next_val = key+c
            if invalid_reg.search(next_val):
                # 新しい文字を追加した時に、条件に違反するなら遷移なし
                continue
            else:
                # 加えても大丈夫なので遷移
                next_dp[(key+c)[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= MOD
# sumの後のMODを忘れない
print(sum(dp.values()) % MOD)

Submission status: Accepted

Solution code:
import re
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N = int(input())
CHAR = ["A", "C", "G", "T"]
pattern = r'ACG|GAC|A.?GC|AG.?C'
reg = re.compile(pattern)

dp = {a+b+c: 1 if not reg.search(a+b+c)
      else 0 for a in CHAR for b in CHAR for c in CHAR}


for i in range(N-3):
    next_dp = {key: 0 for key, _ in dp.items()}
    for key, val in dp.items():
        for c in CHAR:
            next_val = key+c
            if reg.search(next_val):
                continue
            else:
                next_dp[(key+c)[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= MOD
print(sum(dp.values()) % MOD)

Submission status: Accepted

Solution code:
# a:0 c:1 g:2 t:3
# agc acg gac a?gc ag?c
from collections import defaultdict
MOD = 10 ** 9 + 7


def ok(s: str) -> bool:
    if 'AGC' in s:
        return False
    sl = list(s)
    if len(s) < 3:
        return True
    for i in range(len(s)-1):
        st = sl.copy()
        st[i], st[i + 1] = sl[i + 1], sl[i]
        if 'AGC' in ''.join(st):
            return False
    return True


n = int(input())
dp = [defaultdict(int) for _ in range(n + 1)]
dp[0][''] = 1
for i in range(1, n + 1):
    for k in dp[i - 1].keys():
        for c in 'ACGT':
            st = k[1 if i > 4 else 0:] + c
            if ok(st):
                dp[i][st] += dp[i - 1][k]
                dp[i][st] %= MOD
print(sum(dp[n].values()) % MOD)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
dp = [{} 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 0
    return 1

for c1 in 'ACGT':
    for c2 in 'ACGT':
        for c3 in 'ACGT':
            if not c1 + c2 + c3 in {'AGC', 'GAC', 'ACG'}:
                dp[3][c1 + c2 + c3] = 1
for i in range(n - 3):
    for last3 in dp[3 + i]:
        for c in 'ACGT':
            if check(last3 + c):
                if last3[1:] + c in dp[4 + i]:
                    dp[4 + i][last3[1:] + c] += dp[3 + i][last3]
                else:
                    dp[4 + i][last3[1:] + c] = dp[3 + i][last3]
    for key, value in dp[4 + i].items():
        dp[4 + i][key] = value % mod
print(sum(dp[n].values()) % mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
memo = [{} 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 0
    return 1

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

print(dfs(0, 'TTT'))

Submission status: Accepted

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

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

memo=[dict() for _ in range(N)]
def dfp(i,seq):
    if i==N:
        return 1
    if seq in memo[i]:
        return memo[i][seq]
    ret=0
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    memo[i][seq] = ret
    return ret

print(dfp(0,"TTT"))

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())
mod = 10**9+7

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

@lru_cache(maxsize=None)
def dfp(i,seq):
    ret=0
    if i==N:
        return 1
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    return ret

print(dfp(0,"TTT"))

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
a,f=1,1
l=2
b,c,d,e,g,h,i,j,k=0,0,0,0,0,0,0,0,0

for p in range(N-1):
    A=(d+e+i+l)%mod
    B=(a+g)%mod
    C=(b+j)%mod
    D=(b+j)%mod
    E=(a+h)%mod
    F=(c+d+f+k+l)%mod
    G=(b+c+f+j+k)%mod
    H=(a+g+h)%mod
    I=(a+g+h)%mod
    J=(h)%mod
    K=(i)%mod
    L=(c+d+2*e+2*f+2*i+k+2*l)%mod
    a,b,c,d,e,f,g,h,i,j,k,l=A,B,C,D,E,F,G,H,I,J,K,L
print((a+b+c+d+e+f+g+h+i+j+k+l)%mod)

Submission status: Accepted

Solution code:
## クソみたいな漸化式をクソみたいなコードで書いてしまった

def ABC122D_sum():
  return ACT_A[-1]+G_A[-1]+A_G[-1]+GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]

N = int(input())

mod = int(1e9+7)

## N=3の場合で初項を作る
ACT_A = [4*3*1]
G_A = [4*1*1]
A_G = [4*1*1]
GCT_G_G = [3*1*1]
A_G_G = [1*1*1]
C_G = [3*1*1]
A_T_G = [1*1*1]
GCT_T_G = [3*1*1]
A_C = [3*1*1]
GCT_C = [4*2*1+3*1*1]
A_T = [4*1*1]
A_G_T = [1*1*1]
GCT_G_T = [3*1*1]
CT_T = [4*2*1]
#print(ABC122D_sum())

if N == 3:
  print(ABC122D_sum())
  exit()

for i in range(N-3):
  new_ACT_A = ACT_A[-1]+G_A[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_G_A = A_G[-1]+GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_A_G = ACT_A[-1]+G_A[-1]
  new_GCT_G_G = GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_A_G_G = A_G[-1]
  new_C_G = GCT_C[-1]
  new_A_T_G = A_T[-1]
  new_GCT_T_G = A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_A_C = ACT_A[-1]
  new_GCT_C = GCT_G_G[-1]+C_G[-1]+GCT_T_G[-1]+A_C[-1]+GCT_C[-1]+A_T[-1]+GCT_G_T[-1]+CT_T[-1]
  new_A_T = ACT_A[-1]+G_A[-1]
  new_A_G_T = A_G[-1]
  new_GCT_G_T = GCT_G_G[-1]+A_G_G[-1]+C_G[-1]+A_T_G[-1]+GCT_T_G[-1]
  new_CT_T = A_C[-1]+GCT_C[-1]+A_T[-1]+A_G_T[-1]+GCT_G_T[-1]+CT_T[-1]
  ACT_A.append(new_ACT_A)
  G_A.append(new_G_A)
  A_G.append(new_A_G)
  GCT_G_G.append(new_GCT_G_G)
  A_G_G.append(new_A_G_G)
  C_G.append(new_C_G)
  A_T_G.append(new_A_T_G)
  GCT_T_G.append(new_GCT_T_G)
  A_C.append(new_A_C)
  GCT_C.append(new_GCT_C)
  A_T.append(new_A_T)
  A_G_T.append(new_A_G_T)
  GCT_G_T.append(new_GCT_G_T)
  CT_T.append(new_CT_T)
  
ans = ABC122D_sum() % mod
print(ans)

Submission status: Accepted

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


#4文字を与えて条件に合致するかを判断
def check(last4):
    for i in range(4):
        t = list(last4) #4文字をリストに格納
        if i >= 1: #最初の文字以外に着目する時
            t[i-1], t[i] = t[i], t[i-1] #i番目とi-1番目を交換
        if ''.join(t).count('AGC') >= 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 c in 'ATCG':
        if check(last3+c):
            ret = (ret+dfs(cur+1, last3[1:]+c))%mod
    memo[cur][last3] = ret
    return ret

print (dfs(0, 'TTT'))


#print (memo)

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:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def is_ok(s: str, c: str):
    if (s[1:3] == "AG"\
      or s[1:3] == "GA"\
      or (s[0:1] == "A" and s[2:3] == "G")\
      or s[0:2] == "AG")\
      and c == "C":
        return False

    elif s[1:3] == "AC" and c == "G":
        return False

    else:
        return True

from collections import defaultdict

n = ni()

dic = defaultdict(int)
dic["xxx"] = 1

atcg = "ATCG"
MOD = 10**9 + 7

for i in range(n):
    new_dic = defaultdict(int)
    for key, val in dic.items():
        for ci in atcg:
            if is_ok(key, ci):
                new_dic[key[1:] + ci] += val
                new_dic[key[1:] + ci] %= MOD

    dic = new_dic

ans = 0

for _, val in dic.items():
    ans += val
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

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 + 1)]

# 初期値
for c3 in range(4):
    for c2 in range(4):
        for c1 in range(4):
            c321 = (c3, c2, c1)
            if c321 == (0, 1, 2) or c321 == (1, 0, 2) or c321 == (0, 2, 1):
                continue
            dp[3][c3][c2][c1] = 1

# DPテーブル更新
for n in range(4, N + 1):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                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[n][c2][c1][a] += dp[n - 1][c3][c2][c1]
                    dp[n][c2][c1][a] %= MOD

# DPテーブルから答えを出す
ans = 0
for c3 in range(4):
    for c2 in range(4):
        for c1 in range(4):
            ans += dp[N][c3][c2][c1]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict

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

N = int(input())
dp = [defaultdict(int) for i in range(N+1)]
dp[0]['TTT'] = 1

for i in range(1, N+1):
    for last3 in dp[i-1].keys():
        for c in 'ATGC':
            if ok(last3+c):
                dp[i][last3[1:]+c] += dp[i-1][last3] %  (1e9 + 7)
                dp[i][last3[1:]+c] %= (1e9 + 7)
            
ans = 0
for i in dp[N].keys():
    ans += dp[N][i]
    ans %= (1e9 + 7)
    
print(int(ans))

Submission status: Accepted

Solution code:
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############


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(current, last3):
    if last3 in memo[current]:
        return memo[current][last3]
    if current == N:
        return 1
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(current + 1, last3[1:] + c)) % MOD
    memo[current][last3] = ret
    return ret

print(int(dfs(0, "TTT") % MOD))

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9 +7
stack = [[0 for _ in range(64)] for _ in range(N+1)]
LI = ['0','1','2','3']
def judge(x):
    for i in range(4):
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
        if ''.join(x).count('012') >= 1:
            return False
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
    return True
def nu(x,y,z):
    return 16*int(x)+4*int(y)+int(z)
for i in range(64):
    if (i == 6) or (i == 9) or (i == 18):
        stack[3][i] = 0
    else:
        stack[3][i] = 1
for i in range(4,N+1):
    for j in LI:
        for k in LI:
            for l in LI:
                cnt = 0
                for m in LI:
                    if judge([m,j,k,l]):
                        cnt += stack[i-1][nu(m,j,k)] 
                stack[i][nu(j,k,l)] = cnt % mod
ans = 0
for i in range(64):
    ans += stack[N][i]
print(ans % mod)

Submission status: Accepted

Solution code:
# 最後の文字を書くことで初めて反例ができたとする
# 判定に関係があるのは末尾4文字のみ
# 制限が小さいのでルール通り書く


from collections import defaultdict
MOD = 10**9 + 7

N = int(input())

dp = [defaultdict(int) for _ in range(N+1)]
dp[0][''] = 1

def test(s):
  if s.find('ABC') != -1:
    return False
  L = len(s)
  for i in range(L-1):
    li = list(s)
    li[i],li[i+1] = li[i+1],li[i]
    t = ''.join(li)
    if t.find('ABC') != -1:
      return False
  return True
    

for n in range(N):
  for s,cnt in dp[n].items():
    for c in 'ABCD':
      ns = s + c
      if test(ns):
        dp[n+1][ns[-3:]] += cnt
        dp[n+1][ns[-3:]] %= MOD

        
answer = sum(dp[N].values())
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
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 'AGC' in ''.join(t):
            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


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

print(dfs(0, 'TTT'))
# print(memo)

Submission status: Accepted

Solution code:
Mod = 10**9+7
f3 = ["AGC", "GAC", "ACG"]
f4 = ["AGAC","AGGC","AGCC","AGTC"] + ["AAGC","AGGC","ACGC","ATGC"]
q = ["A", "G", "C", "T"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in f3:
        d[s] = 1
        e[s] = 0
      
n = int(input())
for i in range(n-3):
  for s in e.keys():
    for c in q:
      t = s+c
      if t[1:] in f3 or t in f4:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in e.keys():
    d[s] = e[s]
    e[s] = 0
    
print(sum(d.values())%Mod)

Submission status: Accepted

Solution code:
Mod = 10**9+7
p = ["XAGC", "XGAC", "XACG"] + ["AGCX", "GACX", "ACGX"] + ["AGXC", "AXGC"]
q = ["A", "G", "C", "T"]
f = []
for s in p:
  for c in q:
    f.append(s.replace("X",c))

r = ["AGC", "GAC", "ACG"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in r:
        d[s] = 1
        e[s] = 0
      
n = int(input())
for i in range(n-3):
  for s in e.keys():
    for c in q:
      t = s+c
      if t in f:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in e.keys():
    d[s] = e[s]
    e[s] = 0
    
print(sum(d.values())%Mod)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product
N = int(input())
S = ['AAAA','AAAG','AAAC','AAAT','AAGA','AAGG','AAGT','AACA','AACC','AACT','AATA','AATG','AATC','AATT','AGAA','AGAG','AGAT','AGGA','AGGG','AGGT','AGTA','AGTG','AGTT','ACAA','ACAG','ACAC','ACAT','ACCA','ACCG','ACCC','ACCT','ACTA','ACTG','ACTC','ACTT','ATAA','ATAG','ATAC','ATAT','ATGA','ATGG','ATGT','ATCA','ATCG','ATCC','ATCT','ATTA','ATTG','ATTC','ATTT','GAAA','GAAG','GAAC','GAAT','GAGA','GAGG','GAGT','GATA','GATG','GATC','GATT','GGAA','GGAG','GGAT','GGGA','GGGG','GGGC','GGGT','GGCA','GGCG','GGCC','GGCT','GGTA','GGTG','GGTC','GGTT','GCAA','GCAG','GCAC','GCAT','GCGA','GCGG','GCGC','GCGT','GCCA','GCCG','GCCC','GCCT','GCTA','GCTG','GCTC','GCTT','GTAA','GTAG','GTAC','GTAT','GTGA','GTGG','GTGC','GTGT','GTCA','GTCG','GTCC','GTCT','GTTA','GTTG','GTTC','GTTT','CAAA','CAAG','CAAC','CAAT','CAGA','CAGG','CAGT','CACA','CACC','CACT','CATA','CATG','CATC','CATT','CGAA','CGAG','CGAT','CGGA','CGGG','CGGC','CGGT','CGCA','CGCG','CGCC','CGCT','CGTA','CGTG','CGTC','CGTT','CCAA','CCAG','CCAC','CCAT','CCGA','CCGG','CCGC','CCGT','CCCA','CCCG','CCCC','CCCT','CCTA','CCTG','CCTC','CCTT','CTAA','CTAG','CTAC','CTAT','CTGA','CTGG','CTGC','CTGT','CTCA','CTCG','CTCC','CTCT','CTTA','CTTG','CTTC','CTTT','TAAA','TAAG','TAAC','TAAT','TAGA','TAGG','TAGT','TACA','TACC','TACT','TATA','TATG','TATC','TATT','TGAA','TGAG','TGAT','TGGA','TGGG','TGGC','TGGT','TGCA','TGCG','TGCC','TGCT','TGTA','TGTG','TGTC','TGTT','TCAA','TCAG','TCAC','TCAT','TCGA','TCGG','TCGC','TCGT','TCCA','TCCG','TCCC','TCCT','TCTA','TCTG','TCTC','TCTT','TTAA','TTAG','TTAC','TTAT','TTGA','TTGG','TTGC','TTGT','TTCA','TTCG','TTCC','TTCT','TTTA','TTTG','TTTC','TTTT']
S = set(S)
mod = 10**9+7
DP1 = Counter()
for a, b, c in product('AGCT', repeat = 3):
    DP1[a+b+c] = 1
DP1['AGC'] = 0
DP1['ACG'] = 0
DP1['GAC'] = 0
for _ in range(N-3):
    DP2 = Counter()
    for k, v in DP1.items():
        for x in 'AGCT':
            s = k + x
            if s in S:
                DP2[s[1:]] = (DP2[s[1:]] + v) % mod
    DP1 = DP2.copy()
print(sum(v for v in DP1.values()) % mod)

Submission status: Accepted

Solution code:
N = int(input())

def ok(s):
    result = True if 'AGC' not in s else False
    for i in range(len(s)-1):
        s_swap = s[:i] + s[i+1] + s[i] + s[i+2:]
        if 'AGC' in s_swap:
            result = False
    return result

CANDIDATE = 'AGCT'

prev = {}
for i in CANDIDATE:
    for j in CANDIDATE:
        for k in CANDIDATE:
            str_ = i + j + k
            if ok(str_):
                prev[str_] = 1

depth = 3
while depth < N:
    next_ = {}
    for item in prev:
        for i in CANDIDATE:
            str_ = item[-3:] + i
            if ok(str_):
                if str_ in next_:
                    next_[str_] += prev[item]
                else:
                    next_[str_] = prev[item]
    depth += 1
    prev = next_

print(sum(prev.values()) % 1000000007)

Submission status: Accepted

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

dp = [
    [[[1 if i==0 else 0 for i in range(N-2)] for j in range(4)] for k in range(4)] for l in range(4)
]

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

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]

total %= M
print(total)

Submission status: Accepted

Solution code:
ngs4 = ["ATGC", "AGTC","ACGC", "AGCC","AGGC", "AGGC"]
ngs3 = ["AGC", "ACG", "GAC"]
def is_valid(b):
    s = b[-4:]
    if s in ngs4:
        return False
    s = s[-3:]
    if s in ngs3:
        return False
    return True

N = int(input())
memo = [{} for i in range(N+1)]
acgt = ["A", "C", "G", "T"]
MOD = 10**9 + 7
def dp(i, last3):
    if last3 in memo[i]:
        return memo[i][last3]

    if i == N:
        return 1
    
    ret = 0
    for c in acgt:
        candi = last3 + c
        if is_valid(candi):
            ret = (ret + dp(i+1, last3[1:] +c)) % MOD
    memo[i][last3] = ret
    return ret

def sub():
    print(dp(0, "TTT"))

sub()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from collections import defaultdict


def find_ans(dp, mod):
    nex = defaultdict(int)
    for key, val in dp.items():
        for c in ["A", "G", "C", "T"]:
            if (key[1:] == "AG" and c == "C")\
                or (key[1:] == "AC" and c == "G")\
                or (key[1:] == "GA" and c == "C")\
                or (key[:1] == "A" and key[2:] == "G" and c == "C")\
                or (key[:1] == "A" and key[1:2] == "G" and c == "C"):
                continue
            else:
                nex[key[1:] + c] += val
                nex[key[1:] + c] %= mod

    return nex

n = ni()
dp = defaultdict(int)
mod = 10**9 + 7

dp["TTT"] = 1

for _ in range(n):
    dp = find_ans(dp, mod)

ans = 0
for key, val in dp.items():
    ans += val
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
mod = 10**9 + 7

logs = np.zeros((N+1, 4, 4, 4))
logs[0,3,3,3] = 1

for length in range(1, N+1):
#    tmp_for_debug = logs[length-1,:,:,:]
#    print(tmp_for_debug)
#    print("\n\n\n")
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if logs[length-1, c1, c2, c3] == 0:
                    continue
                for n in range(4):
                    if n == 2 and c1 == 1 and c2 == 0:  continue
                    if n == 1 and c1 == 2 and c2 == 0:  continue
                    if n == 2 and c1 == 0 and c2 == 1:  continue
                    if n == 2 and c2 == 1 and c3 == 0:  continue
                    if n == 2 and c1 == 1 and c3 == 0:  continue
                    
                    logs[length, n, c1, c2] += logs[length - 1, c1, c2, c3]
                    logs[length, n, c1, c2] %= mod

M = int(np.sum(logs[N])) % mod
print(M)