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:
import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1

A = np.array(A, dtype = "object")

def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)
# y = np.dot(mat_power(A, N, mod), x) % mod
# for i in range(64):
#   print(to_str(i, 3) + ":", y[i])

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
MOD = 10**9+7
D = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+3)]
D[0][3][3][3] = 1
for n in range(1,N+1):
    for i, j, k, l in product(range(4), repeat=4):
        if (i,j,l)==(2,1,0) or (i,k,l) == (2,1,0) or (i,j,k) == (1,2,0) or (i,j,k) == (2,0,1) or (i,j,k) == (2,1,0): continue
        D[n][i][j][k] += D[n-1][j][k][l]%MOD
res = 0
for i, j, k in product(range(4),repeat=3):
    res += D[N][i][j][k]
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
def summ(M):
    S = 0
    for i in range(4):
        for j in range(4):
            S += M[i][j]
            S %= MOD
    return S

N = int(input())
MOD = 10**9 + 7
D = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+3)]
for i in range(4):
    for j in range(4):
        D[1][i][j][3] = 1
for n in range(2,N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                D[n][i][j][k] = sum(D[n-1][j][k])%MOD
    for l in range(4):
        D[n][2][1][l] -= D[n-1][1][l][0]
        D[n][2][l][1] -= D[n-1][l][1][0]
    D[n][2][1][1] += D[n-1][1][1][0]
    D[n][1][2][0] = 0
    D[n][2][0][1] = 0
    D[n][2][1][0] = 0
print(sum(summ(D[N-1][i]) for i in range(4))%MOD)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

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

    for i in range(1, N):
        for s, v in dp[i - 1].items():
            t = s[:2]
            for c in 'AT':
                dp[i][c + t] = (dp[i][c + t] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + t] = (dp[i]['G' + t] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + t] = (dp[i]['C' + t] + v) % MOD

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

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

    for i in range(1, N):
        for s, v in dp[i - 1].items():
            for c in 'AT':
                dp[i][c + s[:2]] = (dp[i][c + s[:2]] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + s[:2]] = (dp[i]['G' + s[:2]] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + s[:2]] = (dp[i]['C' + s[:2]] + v) % MOD

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n = int(input())
ng = set(["AGC", "GAC", "ACG", "AGGC", "ACGC", "ATGC", "AGAC", "AGGC", "AGTC"])
#moji_count[str] => num_of_moji
moji_count = dd()
moji_count[""] = 1
cand = ["A", "G", "C", "T"]
mod = 10**9 + 7

for i in range(n):
    temp = dd(int)
    for base_moji, num_moji in moji_count.items():
        if len(base_moji) >= 4:
            base_moji = base_moji[1:]
        for add_moji in cand:
            new_moji = base_moji + add_moji
            for ng_word in ng:
                if ng_word in new_moji:
                    break
            else:
                temp[new_moji] += num_moji % mod
        moji_count = temp

print(sum(moji_count.values()) % mod)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import product

input = sys.stdin.readline

P = 10 ** 9 + 7


def is_ok(a, b, c, d):
    s = "".join((a, b, c, d))
    if ("AGC" in s) or ("ACG" in s) or ("GAC" in s):
        return False
    if (s[0] == "A" and s[2:4] == "GC") or (s[0:2] == "AG" and s[3] == "C"):
        return False
    return True


def main():
    N = int(input())

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

    for i in range(N):
        for a, b, c, d in product("ACGT", repeat=4):
            if is_ok(a, b, c, d):
                dp[i + 1][(b, c, d)] = (dp[i + 1][(b, c, d)] + dp[i][(a, b, c)]) % P

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
dp=[[0]*64 for _ in range(n+1)]
dp[0][0]=1
#3前、2前,1前,今の文字
#t=0,a=1,g=2,c=3
ban_list=[]
for i in range(256):
	p=[i//64%4,i//16%4,i//4%4,i%4]
	if p[1:]==[1,2,3] or p[1:]==[1,3,2] or p[1:]==[2,1,3]\
	or (p[:2]==[1,2] and p[3]==3) or (p[0]==1 and p[2:]==[2,3]):
		ban_list.append(i)
for i in range(n):
	for j in range(4):
		for k in range(64):
			three=k*4%64+j
			four=k*4+j
			if four not in ban_list:
				dp[i+1][three]+=dp[i][k]
				dp[i+1][three]%=mod
ans=0
for x in dp[-1]:
	ans+=x
	ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import sys
sys.setrecursionlimit(10**9)

N, MOD = int(input()), 10 ** 9 + 7
dp = [[0] * 64 for _ in range(N+1)]
strs = [""] * 64
strs_d = {}
for i, s in enumerate(product("AGCT", repeat=3)):
    strs[i] = "".join(s)
    strs_d["".join(s)] = i

def check(s):
    assert len(s) == 4
    if "".join(s).count("AGC") >= 1:
        return False
    for i in range(3):
        s[i], s[i + 1] = s[i + 1], s[i]
        if "".join(s).count("AGC") >= 1:
            return False
        s[i], s[i + 1] = s[i + 1], s[i]
    return True

# dp[i][str] := N-i桁かつ末尾4桁がstr文字列のとき、作成可能な文字列の個数

dp[0] = [1] * 64
for i in range(1,1+N):
    for j, s in enumerate(strs):
        for ns in "AGCT":
            if check(list(s+ns)):
                dp[i][strs_d[s[1:]+ns]] += dp[i-1][j]
                dp[i][strs_d[s[1:]+ns]] %= MOD

if N == 3:
    print("61")
else:
    print(sum(dp[N-3])%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
"""
違反文字列
AGC -> AGときたらCはNG
GAC -> GAときたらCはNG
ACG -> ACときたらGはNG
AQGC-> A*GときたらCはNG
AGQC-> AG*ときたらCはNG
"""
n=int(input())
p=10**9+7
ok = ['A','G','C','T']
ng = ['AGC','GAC','ACG']
memo =[{} for i in range(n+1)]

def check(text):
  if text[1:] in ng:
    return 0
  if (text[:2] == 'AG' and text[3]=='C') or (text[0]=='A' and text[2:]=='GC'):
    return 0
  return 1

def dfs(cnt, last):
  if last in memo[cnt]:
    return memo[cnt][last]
  if cnt == n:
    return 1
  ans=0
  for o in ok:
    if check(last+o):
      ans += dfs(cnt+1, last[1:]+o) % p
  memo[cnt][last] = ans
  return ans % p
  

print(dfs(0,'TTT')%p)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

n = int(input())

mod = 10**9 + 7
A, G, C, T = range(1, 5)
dp = np.zeros((n+1, 5, 5, 5), dtype=np.int64)
dp[0, 0, 0, 0] = 1
for m in range(n):
    for i, j, k, l in product(range(5), range(5), range(5), range(1, 5)):
        if i == A and j == G and l == C:
            continue
        if i == A and k == G and l == C:
            continue
        if j == A and k == G and l == C:
            continue
        if j == G and k == A and l == C:
            continue
        if j == A and k == C and l == G:
            continue
        dp[m+1, j, k, l] += dp[m, i, j, k]
        dp[m, i, j, k] %= mod

res = 0
for i, j, k in product(range(1, 5), repeat=3):
    res += dp[n, i, j, k]
    res %= mod
print(res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

    # dp[i文字目][3文字前][2文字前][1文字前]
    dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]
    dp[0][0][0][0] = 1

    # _,A,G,C,T = 0,1,2,3,4
    for n in range(N):
        # 3文字前
        for i in range(5):
            # 2文字前
            for j in range(5):
                # 1文字前
                for k in range(5):
                    # 最後の文字
                    for l in range(1, 5):
                        # AG*C
                        if i == 1 and j == 2 and l == 3: continue
                        # A*GC
                        if i == 1 and k == 2 and l == 3: continue
                        # *AGC
                        if j == 1 and k == 2 and l == 3: continue
                        # *GAC
                        if j == 2 and k == 1 and l == 3: continue
                        # *ACG
                        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] %= mod
    res = 0
    for i in range(5):
        for j in range(5):
            for k in range(5):
                res += dp[-1][i][j][k]
                res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s]
    dp = dp2
print(sum(dp.values()) % mod)

Submission status: Accepted

Solution code:
import collections, itertools
N = int(input())
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s] % mod
    dp = dp2
print(sum(dp.values()) % mod)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a, c, g, t = 0, 1, 2, 3
    dic = {0: "A", 1: "C", 2: "G", 3: "T"}

    dp = [[[[0 for _ in range(4)] for __ in range(4)] for ___ in range(4)] for ____ in range(n + 1)]
    dp[0][t][t][t] = 1

    for x in range(n):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if [j, k, l] not in [[a, g, c], [g, a, c], [a, c, g]]:
                            if [i, j, l] != [a, g, c]:
                                if [i, k, l] != [a, g, c]:
                                    dp[x + 1][j][k][l] += dp[x][i][j][k]
                                    dp[x + 1][j][k][l] %= 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())
mod = pow(10, 9)+7

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

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

def dfs(cur, last3):
  if cur == n:
    return 1
  if last3 in memo[cur]:
    return memo[cur][last3]
  ans = 0
  for c in "AGCT":
    if judge(last3+c):
      ans = (ans+dfs(cur+1, last3[1:]+c))%mod
  memo[cur][last3] = ans
  return ans

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0]*64 for _ in [0]*n]
mod = 10**9+7

A = 0
C = 1
G = 2
T = 3

AGC = 16*A+4*G+C
ACG = 16*A+4*C+G
GAC = 16*G+4*A+C

for j in range(64):
  if j==AGC or j==ACG or j==GAC:
    dp[2][j] = 0
  else:
    dp[2][j] = 1

for i in range(3, n):
  tot = [sum(dp[i-1][k::16]) for k in range(16)]
  for j in range(64):
    c1 = j//16
    c2 = j//4%4
    c3 = j%4
    d = tot[j//4]

    if j==AGC or j==ACG or j==GAC:
      d = 0
    elif c2==G and c3==C:
      d -= dp[i-1][c1*4+G]
    elif c1==G and c3==C:
      d -= dp[i-1][G*4+c2]
    dp[i][j] = d % mod

print(sum(dp[-1]) % 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 'ACGT':
    if ok(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
  memo[cur][last3] = ret
  return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
dp=[{}for i in range(N)]
list=['AGC','ACG','GAC']
def dfs(x,y):
  if x in list:
    return 0
  if y==N:
    return 1
  if x in dp[y]:
    return dp[y][x]
  ans=0
  for i in 'ACGT':
    if x[0]=='A' and i=='C' and (x[1]=='G' or x[2]=='G'):
      continue
    ans+=dfs(x[1:]+i,y+1)
  dp[y][x]=ans%mod
  return ans%mod
print(dfs('TTT',0))

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9 + 7
# dp[i][x][y][z] 0:A 1:C 2:G 3:T
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
for i in range(1, n+1):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if x == 0 and z == 2 and w == 1:
                        continue
                    elif y == 0 and z == 2 and w == 1:
                        continue
                    elif y == 2 and z == 0 and w == 1:
                        continue
                    elif y == 0 and z == 1 and w == 2:
                        continue
                    elif x == 0 and y == 2 and w == 1:
                        continue

                    dp[i][y][z][w] += dp[i-1][x][y][z]
                    dp[i][y][z][w] %= MOD

ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9 + 7
# dp[i][x][y][z] 0:A 1:C 2:G 3:T
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
for i in range(n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if x == 0 and z == 2 and w == 1:
                        continue
                    elif y == 0 and z == 2 and w == 1:
                        continue
                    elif y == 2 and z == 0 and w == 1:
                        continue
                    elif y == 0 and z == 1 and w == 2:
                        continue
                    elif x == 0 and y == 2 and w == 1:
                        continue

                    dp[i+1][y][z][w] += dp[i][x][y][z]
                    dp[i+1][y][z][w] %= MOD

ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9+7

N = int(input())
# memo[i]: i番目の文字まで作った時の候補数
memo = [{} for _ in range(N+1)]

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

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    res = 0
    for c in 'AGCT':
        if ok(last3 + c):
            res = (res + dfs(cur+1, last3[1:]+c)) % m
    memo[cur][last3] = res
    return res

print(dfs(0,'TTT'))

Submission status: Accepted

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

al=pow(4,n,mod)

import itertools
itr=itertools.product([0,1,2,3],repeat=4)
itr=list(itr)
dic1={} #dec
dic2={} #enc
for i in enumerate(itr):
    dic1[i[0]]=[i[1]]
    dic2[i[1]]=[i[0]]

    

dp=[[0 for i in range(4**3)] for q in range(n+1)]

for i in range(4**3):
    if i!=9 and i!=33 and i!=6:
        dp[3][i]=1


for i in range(3,n):
    for q in range(4**3):
        for r in range(4):
            p1=q//16%4
            p2=q//4%4
            p3=q%4
            
            if p2==0 and p3==2 and r==1:
                continue
            if p1==0 and p3==2 and r==1:
                continue
            if p1==0 and p2==2 and r==1:
                continue
            if p2==0 and p3==1 and r==2:
                continue
            if p2==2 and p3==0 and r==1:
                continue
        
            ck=q%16*4
            dp[i+1][ck+r]+=dp[i][q]
            dp[i+1][ck+r]%=mod

print(sum(dp[n])%mod)

Submission status: Accepted

Solution code:
import copy

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

dp = [[[[0]*(5) for i in range(5)] for i in range(5)] for i in range(n+1)]

dp[0][0][0][0] = 1
# A:1, C:2, G:3, T:4
for cn in range(1, n+1):
    for c3 in range(5):
        if cn <= 3 and c3 > 0:
            continue
        for c2 in range(5):
            if cn <= 2 and c2 > 0:
                continue
            for c1 in range(5):
                if cn == 1 and c1 > 0:
                    continue
                
                if c2 == 1 and c1 == 3: # AGX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 1 and c1 == 2: # ACX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = 0
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 3 and c1 == 1: # GAX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c1 == 3: # AXGY        
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c2 == 3: # AGXY        
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                else:
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    
total = 0
for c3 in range(1, 5):
    for c2 in range(1, 5):
        for c1 in range(1, 5):
            total = (total + dp[n][c3][c2][c1]) % MOD
print(total)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
out = [ "AGC", "ACG", "GAC"]
from functools import *

def check(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') >= 1:
            return False
    return True

@lru_cache(None)
def dfs(n, s):
    if n == N:
        return 1
    res = 0
    for c in "ACGT":
        if not check(s + c):
            continue
        res += dfs(n + 1, s[1:] + c) % MOD
    return res

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

Submission status: Accepted

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

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

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

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

print(dfs(0, 'XXX'))

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
mod = 10**9+7

from collections import defaultdict
from itertools import product

A = [('A','G','C'),('G','A','C'),('A','C','G')]

for i in range(3,N+1):
    if i == 3:
        d = defaultdict(int)  # d[a] = aで終わる条件を満たす文字列の個数
        for a in list(product(['A','C','G','T'],repeat=3)):
            d[(a[0],a[1],a[2])] = 1
        for a in A:
            d[a] = 0
    else:
        new_d = defaultdict(int)
        for a in ['A','C','G','T']:
            for b in list(product(['A','C','G','T'],repeat=3)):
                if not ((b[1],b[2],a) in A or (b[0],b[1],a) == ('A','G','C') or (b[0],b[2],a) == ('A','G','C')):
                    new_d[(b[1],b[2],a)] += d[b]
                    new_d[(b[1], b[2], a)] %= mod
        d = new_d

print(sum(d.values()) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9 + 7

N = int(input())

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

def sol(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 sol(ns):
                dp[n+1][ns[-3:]] += cnt
                dp[n+1][ns[-3:]] %= MOD

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

Submission status: Accepted

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

def ok(x, y, z, nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def f(num,A):
  if num==N:
    return 1
  else:
    x,y,z=A[0],A[1],A[2]
    if (x,y,z) in memo[num]:
      return  memo[num][(x,y,z)]
    else:
      s=0
      for i in ['A','C','G','T']:
        if ok(x,y,z,i):
          s+=f(num+1,(y,z,i))
      memo[num][(x,y,z)]=s%mod
      return s%mod
print(f(0,'ZZZ'))

Submission status: Accepted

Solution code:
n=int(input())
if n==3:
  print(61)
  exit()
mod=pow(10,9)+7
#d={'A':0,'G':1,'C':2,'T':3}
d={0:'A',1:'G',2:'C',3:'T'}
dd={}
dinitial={}
for i in range(4**4):
  key=[]
  for _ in range(4):
    key.append(d[i%4])
    i//=4
  key=''.join(key)
  if 'AGC' in key:continue
  if 'ACG' in key:continue
  if 'GAC' in key:continue
  if key[0]=='A' and key[2:4]=='GC':continue
  if key[0:2]=='AG' and key[3]=='C':continue
  dd[key]=1
  dinitial[key]=0

for _ in range(n-4):
  ddd=dinitial.copy()
  for k in dd:
    if k[1:]+'A' in ddd:
      ddd[k[1:]+'A']+=dd[k]
      ddd[k[1:]+'A']%=mod
    if k[1:]+'G' in ddd:
      ddd[k[1:]+'G']+=dd[k]
      ddd[k[1:]+'G']%=mod
    if k[1:]+'C' in ddd:
      ddd[k[1:]+'C']+=dd[k]
      ddd[k[1:]+'C']%=mod
    if k[1:]+'T' in ddd:
      ddd[k[1:]+'T']+=dd[k]
      ddd[k[1:]+'T']%=mod
  dd=ddd

print(sum(dd.values())%mod)

Submission status: Accepted

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

def ok(x,y,z,nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def dfs(idx,lis):
    if idx==N:
      return 1
    x,y,z=lis[0],lis[1],lis[2]
    if (x,y,z) in memo[idx]:
        return memo[idx][(x,y,z)]
    ret=0
    for nx in ['A','G','C','T']:
        if ok(x,y,z,nx):
            ret+=dfs(idx+1,(y,z,nx))
    memo[idx][(x,y,z)]=ret%mod
    return ret%mod

print(dfs(0,'DDD'))

Submission status: Accepted

Solution code:
N=int(input())

ch=['A','G','C','T']
ban3=['AGC','GAC','ACG']
ban4=['ATGC','AGGC','AGTC']
dp=[{},{}]

mod=10**9+7

for i in range(4**3):
    s=''
    for j in range(3):
        s+=ch[(i>>(j*2))%4]
    
    if s in ban3:
        dp[0][s]=0
    else:
        dp[0][s]=1
    
    dp[1][s]=0

cnt=0

while N>3:
    for k in dp[(cnt+1)%2]:
        dp[(cnt+1)%2][k]=0
    
    for k,v in dp[cnt].items():
        for c in ch:
            nk=k+c

            if nk in ban4:
                continue

            if nk[1:] in ban3:
                continue

            dp[(cnt+1)%2][nk[1:]]+=dp[cnt][nk[:3]]
            dp[(cnt+1)%2][nk[1:]]%=mod
            
    N-=1
    cnt=(cnt+1)%2

print(sum(dp[cnt].values())%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

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

# ATCGは0123と読み替える
# 長さ0の文字列は1。0,1,2に関する制約しかないので、Sは333Sと考えても問題がない
dp[0][3][3][3] = 1

# 文字列の文字数
for length in range(n):
    # 最後から1文字目の文字
    for c1 in range(4):
        # 最後から2文字目の文字
        for c2 in range(4):
            # 最後から3文字目の文字
            for c3 in range(4):
                # 条件に当てはまる物がない場合はcontinue
                if dp[length][c1][c2][c3] == 0: continue
                # 新しく追加する文字
                for a in range(4):
                    
                    # ダメな5条件をカット
                    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
                    
                    # ダメな条件を抜けたら、aを足した文字列を作れる
                    # S = ... c3 c2 c1
                    # nextS = ... c2 c1 a
                    dp[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                    dp[length+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):
            # 長さnの文字列の値をまとめる
            ans += dp[n][c1][c2][c3]
            ans %= MOD
            
print(ans)