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:
# 解説AC
n = int(input())
mod = 10**9+7

# -----------DP解法----------
# ---考え方---
# 文字列として入ってはいけないものは、以下の5通り
# 'AGC', 'ACG', 'GAC', 'A?GC', 'AG?C'
# i文字目の決定に関与するのは、i-1, i-2, i-3文字目のみ

# 参考: https://drken1215.hatenablog.com/entry/2019/04/23/120400
# DP[i][i-3文字目:x][i-2文字目:y][i-1文字目:z] = 条件を満たす長さiの文字列の総数
# 以下、i文字目をmで表す

# 文字管理として、初期値:0, A:1, G:2, C:3, T:4とする
# (xyzm)として、(?123), (?132), (?213), (1?23), (12?3)が条件を満たさないパターン
# 


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

for i in range(n):
    # i-3~i-1文字目
    for x in range(5):
        for y in range(5):
            for z in range(5):
                # i文字目
                for m in range(1,5):
                    if y == 1 and z == 2 and m == 3:
                        continue
                    elif y == 1 and z == 3 and m == 2:
                        continue
                    elif y == 2 and z == 1 and m == 3:
                        continue
                    elif x == 1 and z == 2 and m == 3:
                        continue
                    elif x == 1 and y == 2 and m == 3:
                        continue
                    DP[i+1][y][z][m] = (DP[i+1][y][z][m] + DP[i][x][y][z]) % mod

ans = 0
for x in range(1,5):
    for y in range(1,5):
        for z in range(1,5):
            ans = (ans + DP[n][x][y][z]) % mod

print(ans)
                    

# -----------以下はメモ化再帰解法------------

# # 先に上記文字列が入っているかどうかを判定する関数を用意する
# # 入力されるsは4文字とする
# def moji_check(s):
#     if s.count('AGC') >= 1 or s.count('ACG') >= 1 or s.count('GAC') >= 1:
#         return False
#     elif s[0] == 'A' and s[2:4] == 'GC':
#         return False
#     elif s[:2] == 'AG' and s[3] == 'C':
#         return False
#     else:
#         return True

# # メモ化再帰で求める
# # memo[i]: 現在の文字数目に登場した
# memo = [{} for i in range(n+1)]

# def dfs(cur, s):
#     if s in memo[cur]:
#         return memo[cur][s]
#     if cur == n:
#         return 1
#     ret = 0
#     for c in 'AGCT':
#         if moji_check(s+c) == True:
#             ret = (ret + dfs(cur+1, s[1:] + c)) % mod
#     memo[cur][s] = ret
#     return ret
# print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""

N=int(input())
mod=10**9+7
num=pow(4,N,mod)

S={}
for i in range(1,N+1):
    S[i]={}

S[1]={"A":1,"G":1,"C":1,"T":1}
C=["A","G","C","T"]
for i in range(1,N):
    for s in S[i]:
        for c in C:
            st=s+c
            if len(st)>=5:
                st="".join(list(st)[1:])

            if len(st)==3:
                if st in ["AGC","GAC","ACG"]:
                    continue
            elif len(st)==4:
                if "AGC" in st or "GAC" in st or "ACG" in st:
                    continue
                if st[0]+st[1]+st[3]=="AGC":
                    continue
                if st[0]+st[2]+st[3]=="AGC":
                    continue
            if not st in S[i+1]:
                S[i+1][st]=S[i][s]
            else:
                S[i+1][st]+=S[i][s]
                S[i+1][st]%=mod

#print(S)
print(sum([S[N][i] for i in S[N]])%mod)

Submission status: Accepted

Solution code:
#we like agc
n=int(input())
import itertools
P=list(itertools.product('ACGT', repeat=3))
mod=10**9+7
use=[] 
for some in P:
    some=list(some)
    K="".join(some)
    use.append(K)
dp=[{some:0 for some in use}for k in range(n+1)]
for some in use:
    if some!="AGC" and some!="ACG" and some!="GAC":
        dp[3][some]=1

D=["A","C","G","T"]
for i in range(4,n+1):
    for some in use:
        #some=AAA,AAC,AAG,,,,,,,,TTT
        for j in range(4):
            S=list(some+D[j])
            if (S[0]=="A" and S[2]=="G" and S[3]=="C")  or (S[1]=="G" and S[2]=="A "and S[3]=="C") or (S[0]=="A" and S[1]=="G" and S[3]=="C"):
                pass
            else:
                if some!="AGC" and some!="ACG" and some!="GAC":
                    dp[i]["".join(S[1:])]+=dp[i-1][some]
                    dp[i]["".join(S[1:])]=dp[i]["".join(S[1:])]%mod
ans=0
for some in use:
    if some!="AGC" and some!="ACG" and some!="GAC":
        ans+=dp[n][some]
print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product, permutations

MOD = 1000000007  # type: int

def solve(N: int):
    f = lambda : {c:{cc:{ccc:0 for ccc in 'ACGT'} for cc in 'ACGT'} for c in 'ACGT'}
    dp = [f() for _ in range(N+2)]
    ng = set(map(tuple, ('AGC', 'ACG', 'GAC', #.XXX, XXX.
                         'AAGC', 'AGGC', 'ACGC', 'ATGC', #A.GC
                         'AGAC', 'AGCC', 'AGGC', 'AGTC', #AG.C
                     )))
    for a, b, c in product('ACGT', repeat=3):
        if (a, b, c) in ng:
                continue
        dp[2][a][b][c] = (dp[2][a][b][c] + 1) % MOD
    for i in range(2, N):
        for a, b, c, d in product('ACGT', repeat=4):
            if (a, b, c, d) in ng or (a, b, c) in ng or (b, c, d) in ng:
                continue
            dp[i][b][c][d] = (dp[i][b][c][d] + dp[i-1][a][b][c]) % MOD
    return sum(sum(sum(dd.values()) for dd in d.values()) for d in dp[N-1].values()) % MOD

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    print(solve(N))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline   
sys.setrecursionlimit(100000000)
from functools import lru_cache
INF = 1000000000
MOD = 10**9+7

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

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

    dp[3]=[[[1]*4 for _ in range(4)] for _ in range(4)]    
    dp[3][0][2][1]=0
    dp[3][0][1][2]=0
    dp[3][2][0][1]=0
    
    cannot={(0,1,2),(0,2,1),(2,0,1)}

    for i in range(4,n+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (j,k,l) in cannot:
                        dp[i][j][k][l]=0
                    else:
                        for m in range(4):
                            if (m,j,l)==(0,2,1) or (m,k,l)==(0,2,1):
                                continue
                            else:
                                dp[i][j][k][l]+=dp[i-1][m][j][k]
                                dp[i][j][k][l]%=MOD

    ans=0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans+=dp[-1][i][j][k]
                ans%=MOD
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

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

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
let = {i:l for i,l in enumerate('AGCT')}

for i in range(1,N+1):
    for l3 in range(4):
        for l2 in range(4):
            for l1 in range(4):
                for nextl in range(4):
                    flag = True
                    for j in range(4):
                        lets = list(let[l3]+let[l2]+let[l1]+let[nextl])
                        if j >= 1:
                            lets[j-1],lets[j] = lets[j],lets[j-1]
                        if 'AGC' in ''.join(lets):
                            flag = False
                            break
                    if flag:
                        dp[i][l2][l1][nextl] += dp[i-1][l3][l2][l1]
                        dp[i][l2][l1][nextl] %= mod
ans = 0
for l3 in range(4):
    for l2 in range(4):
        for l1 in range(4):
            ans = (ans + dp[N][l3][l2][l1])%mod
print(ans)

Submission status: Accepted

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

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
let = {i:l for i,l in enumerate('AGCT')}

def judge(lets):
    for i in range(4):
        t = lets.copy()
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]
        if 'AGC' in ''.join(t):
            return False
    return True

for i in range(1,N+1):
    for l3 in range(4):
        for l2 in range(4):
            for l1 in range(4):
                for nextl in range(4):
                    lets = list(let[l3]+let[l2]+let[l1]+let[nextl])
                    if judge(lets):
                        dp[i][l2][l1][nextl] += dp[i-1][l3][l2][l1]
                        dp[i][l2][l1][nextl] %= mod
ans = 0
for l3 in range(4):
    for l2 in range(4):
        for l1 in range(4):
            ans = (ans + dp[N][l3][l2][l1])%mod
print(ans)

Submission status: Accepted

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

memo = [{} for i in range(N+1)]

def judge(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(i,last3):
    if last3 in memo[i]:
        return memo[i][last3]
    if i == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if judge(last3+c):
            ret = (ret + dfs(i+1,last3[1:]+c))%mod
    memo[i][last3] = ret
    return ret

print(dfs(0,'TTT'))

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

comp = {"A": 0, "C": 1, "G": 2, "T": 3}
keys = comp.keys()

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

bad = [0b001001, 0b000110, 0b100001]
for i in range(4 ** 3):
    if not i in bad:
        dp[3][i] = 1


def is_ok(li):
    for i in range(4):
        tmp = deepcopy(li)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]

        if "".join(tmp).count("AGC") >= 1:
            return False

    return True


def comp2int(li):
    ret = 0
    for i, e in enumerate(li):
        ret += comp[e] << 2 * (2 - i)

    return ret


for i in range(3, n):
    for last4 in product(keys, repeat=4):
        last4 = list(last4)
        if is_ok(last4):
            j_prev = comp2int(last4[:-1])
            j_nxt = comp2int(last4[1:])
            dp[i+1][j_nxt] += dp[i][j_prev]
            dp[i+1][j_nxt] %= mod

ans = 0
for i in range(4 ** 3):
    ans += dp[n][i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

comp = {"A": 0, "C": 1, "G": 2, "T": 3}

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

bad = [0b001001, 0b000110, 0b100001]
for i in range(4 ** 3):
    if not i in bad:
        dp[3][i] = 1


def is_ok(li):
    for i in range(4):
        tmp = deepcopy(li)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]

        if "".join(tmp).count("AGC") >= 1:
            return False

    return True


def comp2int(li):
    ret = 0
    for i, e in enumerate(li):
        ret += comp[e] << 2 * (2 - i)

    return ret


for i in range(3, n):
    for j in product(comp.keys(), repeat=3):
        for k in comp.keys():
            last4 = list(j) + [k]
            if is_ok(last4):
                j_prev = comp2int(j)
                j_nxt = comp2int(last4[1:])
                dp[i+1][j_nxt] += dp[i][j_prev]
                dp[i+1][j_nxt] %= mod

ans = 0
for i in range(4 ** 3):
    ans += dp[n][i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#賢く解くと...
n=int(input())
mod=10**9+7
memo=[{} for _ in range(n+1)]

def judge(last4):
    for i in range(4):
        t=list(last4)
        if i<3:
            t[i],t[i+1]=t[i+1],t[i]
        s=''.join(t)
        if 'AGC' in s:
            return False
    return True

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

print(dfs(0,'TTT'))

Submission status: Accepted

Solution code:
#122_D
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 k in range(4):
    for l in range(4):
        for m in range(4):
            flg=(k==0 and l==1 and m==2) or (k==0 and l==2 and m==1) or (k==2 and l==0 and m==1)
            if not flg:
                dp[3][k][l][m]=1
        

        
for i in range(4,n+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    flg=(j==0 and (k==2 or l==2) and m==1) or (k==0 and l==1 and m==2) or (k==0 and l==2 and m==1) or (k==2 and l==0 and m==1)
                    if not flg:
                        dp[i][k][l][m]+=dp[i-1][j][k][l]
ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[n][i][j][k]
print(ans%mod)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

g_cnt = 0
def main():
    N = I()
    dp = [[[[0 for _ in range(4)] for ____ in range(4)] for __ in range(4)] for ___ in range(N+1)]
    s2i = {
        'A': 0,
        'G': 1,
        'C': 2,
        'T': 3,
    }
    dp[0][3][3][3] = 1

    for i in range(0, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for char in ['A', 'G', 'C', 'T']:
                        if char == 'G':
                            if k == s2i['A'] and l == s2i['C']:
                                continue
                        elif char == 'C':
                            if j == s2i['A'] and l == s2i['G']:
                                continue
                            if k == s2i['G'] and l == s2i['A']:
                                continue
                            if k == s2i['A'] and l == s2i['G']:
                                continue
                            if j == s2i['A'] and k == s2i['G']:
                                continue
                        else:
                            pass
                        dp[i+1][k][l][s2i[char]] += dp[i][j][k][l]
                        dp[i+1][k][l][s2i[char]] %= mod

    cnt = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                cnt += (dp[N][j][k][l] % mod)
                cnt %= mod
    print(cnt)
main()

Submission status: Accepted

Solution code:
n = int(input())

dp = [0]*64
#dpの保持変更

#a,g,c =0,1,2
##末尾4文字見る必要がある。3文字ではない

def test(w,x,y,z):
    s = ((0,1,2),(1,0,2),(0,2,1))
    if (x,y,z) not in s and (w,y,z)!=(0,1,2) and (w,x,z)!=(0,1,2):##これ手でノーミスは無理なのだが、処理の実装を思いつく気がしない
        return True
    else:
        return False

for i in range(64):
    x,y,z = i>>4,(i>>2)&3,i&3
    if test(3,x,y,z):
        dp[i]=1

for i in range(3,n):
    dp2 = [0]*64
    for j in range(64):
        w,x,y = j>>4,(j>>2)&3,j&3
        """
        if w not in (0,1,2,3) or x not in (0,1,2,3) or y not in ( 0,1,2,3):
            print(j,w,x,y)
            exit()
        """
        for z in range(4):
            if test(w,x,y,z):
                dp2[(x<<4)+(y<<2)+z]+=dp[j]
    dp = dp2

#for i in range(16):
#    ans+=dp[i][n-1]
ans = sum(dp)
ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0]*64 for i in range(n)]


#a,g,c =0,1,2
##末尾4文字見る必要がある。3文字ではない

def test(w,x,y,z):
    s = ((0,1,2),(1,0,2),(0,2,1))
    if (x,y,z) not in s and (w,y,z)!=(0,1,2) and (w,x,z)!=(0,1,2):##これ手でノーミスは無理なのだが、処理の実装を思いつく気がしない
        return True
    else:
        return False

for i in range(64):
    x,y,z = i>>4,(i>>2)&3,i&3
    if test(3,x,y,z):
        dp[2][i]=1

for i in range(3,n):
    for j in range(64):
        w,x,y = j>>4,(j>>2)&3,j&3
        """
        if w not in (0,1,2,3) or x not in (0,1,2,3) or y not in ( 0,1,2,3):
            print(j,w,x,y)
            exit()
        """
        for z in range(4):
            if test(w,x,y,z):
                dp[i][(x<<4)+(y<<2)+z]+=dp[i-1][j]

#for i in range(16):
#    ans+=dp[i][n-1]
ans = sum(dp[n-1])
ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    mod = 10**9 + 7
    v = {'TTTT': 1}
    for _ in range(N):
        u = {}
        for c, k in v.items():
            c = c[1:]
            for i in 'ACGT':
                t = c + i
                if 'AGC' in t or 'GAC' in t or 'ACG' in t or (t[0] == 'A' and t[2:] == 'GC') or (t[:2] == 'AG' and t[3] == 'C'):
                    continue
                u[t] = (u.get(t, 0) + k) % mod
        v = u
    print(sum(v.values()) % mod)

main()

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10**9 + 7

# dp[s][i][j][k] = str[s:s+3]が(i,j,k)となる個数の数え上げ
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]

# 初期条件
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue #AGC
            if i==0 and j==2 and k==1: continue #ACG
            if i==1 and j==0 and k==2: continue #GAC
            dp[0][i][j][k] = 1

# 先頭から末尾に向けてループ
for i in range(N-3):
    # 確定している文字列 (ppp,pp,p)
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                # 次の文字 (n)
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue #AGC
                    if pp==0 and p==2 and n==1: continue #ACG
                    if pp==1 and p==0 and n==2: continue #GAC
                    if ppp==0 and p==1 and n==2: continue #A?GC
                    if ppp==0 and pp==1 and n==2: continue #AG?C
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
p = 10 ** 9 + 7
dp = np.zeros((N + 1, 4, 4, 4), dtype = "int64")

# dp[0][c3][c2][c1] = 0 for all *** except c1=c2=c3=3
dp[0][3][3][3] = 1
for len in range(0, N):
    for c3 in range(0, 4):
        for c2 in range(0, 4):
            for c1 in range(0, 4):
                for newchar in range(0, 4):
                    # 条件を満たさないもの
                    if c2 == 0 and c1 == 1 and newchar == 2: continue
                    if c2 == 1 and c1 == 0 and newchar == 2: continue
                    if c2 == 0 and c1 == 2 and newchar == 1: continue
                    if c3 == 0 and c1 == 1 and newchar == 2: continue
                    if c3 == 0 and c2 == 1 and newchar == 2: continue
                    dp[len + 1][c2][c1][newchar] += dp[len][c3][c2][c1]
                    dp[len + 1][c2][c1][newchar] %= p

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [[[[0
            for c3 in range(4)]
            for c2 in range(4)]
            for c1 in range(4)]
            for L  in range(N+1)]
    dp[0][3][3][3] = 1
    for L in range(1, N+1):
        for c3 in range(4):
            for c2 in range(4):
                for c1 in range(4):
                    for c0 in range(4):
                        if ((c2 == 0 and c1 == 2 and c0 == 1) or
                            (c2 == 2 and c1 == 0 and c0 == 1) or
                            (c2 == 0 and c1 == 1 and c0 == 2) or
                            (c3 == 0 and c2 == 2 and c0 == 1) or
                            (c3 == 0 and c1 == 2 and c0 == 1)):
                            continue
                        dp[L][c0][c1][c2] += dp[L-1][c1][c2][c3]
                        dp[L][c0][c1][c2] %= 10**9 + 7
    ans = 0
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= 10**9 + 7
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
MOD = 10**9+7
dp = np.zeros(64,np.int64)
pdp = np.ones(64,np.int64)
a = 16
b = 4
pdp[0*a+2*b+1] = 0
pdp[0*a+1*b+2] = 0
pdp[2*a+0*b+1] = 0
dic = {}
dic[0] = 'A'
dic[1] = 'C'
dic[2] = 'G'
dic[3] = 'T'
for i in range(N-3):
  for j in range(64):
    x = j//16
    y = (j-x*16)//4
    z = j%4
    m = 16*y+4*z
    if y==2 and z==0:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==1:
      for h in range(4):
        if h==2:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and y==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    else:
      for h in range(4):
        dp[m+h] += pdp[j]
  dp %= MOD
  pdp = np.copy(dp)
  dp = np.zeros(64,np.int64)
print(pdp.sum()%MOD)

Submission status: Accepted

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

# T -> 0
# A -> 1
# G -> 2
# C -> 3 とする

# 先頭の文字をi、先頭から2番めの文字をj、先頭から3番目の文字をkとなるような
# 場合の数をDPテーブルで管理する
# dp[n][i][j][k] += dp[n-1][j][k][l]

# 新しく文字を追加したとき、
# 先頭4文字が以下のようにならないようにしたい
# AGC*, ACG*, GAC*, AG*C, A*GC 

# j,k,lがこれらのときアウト
# AGC -> 123 -> 321
# ACG -> 132 -> 231
# GAC -> 213 -> 312

# j,k,l,mがこれらのときアウト
# AG*C -> 12*3 -> 3*21
# A*GC -> 1*23 -> 32*1

for i in range(1, N+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):

                    if j==3 and k==2 and l==1:continue
                    elif j==2 and k==3 and l==1:continue
                    elif j==3 and k==1 and l==2:continue
                    elif j==3 and k==2 and m==1:continue
                    elif j==3 and l==2 and m==1:continue

                    d[i][j][k][l] += d[i-1][k][l][m]
                    d[i][j][k][l] %= mod

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

print(ans)

Submission status: Accepted

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

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

def ok(last4):
  for i in range(4):
    temp = list(last4)
    if i >= 1:
      temp[i-1], temp[i] = temp[i], temp[i-1]
    if ''.join(temp).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 = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
dp[0][3][3][3] = 1

for Length in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                if dp[Length][i][j][k] == 0:
                    continue

                for d in range(4):  # 追加する文字
                    if d == 1 and j == 0 and k == 2:
                        continue
                    if d == 2:
                        if j == 0 and k == 1:
                            continue
                        if j == 1 and k == 0:
                            continue
                        if i == 0 and k == 1:
                            continue
                        if i == 0 and j == 1:
                            continue

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    D={
        "A":0, "G":1, "C":2, "T":3
    }

    DP=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N)] #DP[i][a][b][c] := i文字目までで、最後の文字ががabcな場合の数
    DP[1][3] = [[1]*4 for _ in range(4)] 
    for i in range(2,N):
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for s in range(4):
                        if s==0: #なんでもOK
                            pass
                        elif s==1: #ACGだとout
                            if (b,c)==(D["A"],D["C"]):
                                continue
                        elif s==2: #AGC,GAC,A?GC,AG?Cがout
                            if (b,c) in ((D["A"],D["G"]), (D["G"],D["A"])) or (a,c) == (D["A"], D["G"]) or (a,b) == (D["A"], D["G"]) :
                                continue
                        else: #なんでもOK
                            pass
                        DP[i][b][c][s] += DP[i-1][a][b][c]
                        DP[i][b][c][s] %= mod

    ans = 0
    for a in DP[-1]:
        ans += sum([sum(i) for i in a])
    print(ans%mod)
    """
    AGC
    ACG
    GAC
    A?GC
    AG?C

    """
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())

MOD = 10**9 + 7

# dp[s][i][j][k] = str[s:s+3]が(i,j,k)となる個数の数え上げ
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]

# 初期条件
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue #AGC
            if i==0 and j==2 and k==1: continue #ACG
            if i==1 and j==0 and k==2: continue #GAC
            dp[0][i][j][k] = 1

# 先頭から末尾に向けてループ
for i in range(N-3):
    # 確定している文字列 (ppp,pp,p)
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                # 次の文字 (n)
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue #AGC
                    if pp==0 and p==2 and n==1: continue #ACG
                    if pp==1 and p==0 and n==2: continue #GAC
                    if ppp==0 and p==1 and n==2: continue #A?GC
                    if ppp==0 and pp==1 and n==2: continue #AG?C
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD

ans = sum(sum(sum(a) for a in b) for b in dp[-1])
print(ans % MOD)

Submission status: Accepted

Solution code:
N = int(input())
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N-2)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==0 and j==1 and k==2: continue #AGC
            if i==0 and j==2 and k==1: continue #ACG
            if i==1 and j==0 and k==2: continue #GAC
            dp[0][i][j][k] = 1
MOD = 10**9+7
for i in range(N-3):
    for ppp in range(4):
        for pp in range(4):
            for p in range(4):
                for n in range(4):
                    if pp==0 and p==1 and n==2: continue #AGC
                    if pp==0 and p==2 and n==1: continue #ACG
                    if pp==1 and p==0 and n==2: continue #GAC
                    if ppp==0 and p==1 and n==2: continue #A?GC
                    if ppp==0 and pp==1 and n==2: continue #AG?C
                    dp[i+1][pp][p][n] += dp[i][ppp][pp][p]
                    dp[i+1][pp][p][n] %= MOD
ans = sum(sum(sum(a) for a in b) for b in dp[-1])
print(ans%MOD)

Submission status: Accepted

Solution code:
n = int(input())
memo = [{} for i in range(n+1)]
mod = 10**9+7
#想定解法の写経
def ok(last4):
    #隣接する二つを入れ替えてAGC二ならないかどうかをチェック
    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(now, last3):
    if last3 in memo[now]:
        return memo[now][last3]
    if now == n:
        return 1
    ret = 0
    for i in 'AGCT':
        #もし、次の一文字を足した4文字がずらしてAGCに引っかからなければ
        if ok(last3 + i):
            #今回をiにした場合のこの後の文字列の数を全て計算
            ret = (ret + dfs(now+1, last3[1:] + i)) % mod
    memo[now][last3] = ret
    return ret
print(dfs(0,'TTT'))