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())
MOD = 10 ** 9 + 7

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

def f(x):
  for i in range(4):
    temp = list(x)
    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(temp, x):
  if x in memo[temp]:
    return memo[temp][x]
  if temp == N:
    return 1
  ans = 0
  for c in 'ACGT':
    if f(x + c):
      ans = (ans + dfs(temp + 1, x[1:] + c)) % MOD
  memo[temp][x] = ans
  return ans

print(dfs(0, 'XXX'))

Submission status: Accepted

Solution code:
n = int(input())
mod = 1000000007
dp = [[[0]*4 for _ in range(4)] for _ in range(n+1)]
for j in range(4):
    for k in range(4): dp[2][j][k] = 1

for i in range(2,n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if (j,k,l) in ((2,1,0),(1,2,0),(1,0,2)): continue
                dp[i+1][j][k] += dp[i][k][l]
                dp[i+1][j][k] %= mod
    dp[i+1][1][2] -= dp[i-1][2][0]
    dp[i+1][1][2] %= mod
    dp[i+1][1][3] -= dp[i-1][2][0]
    dp[i+1][1][3] %= mod
    dp[i+1][1][2] -= dp[i-1][3][0]
    dp[i+1][1][2] %= mod

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

# for i in range(n+1): print(dp[i])

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9+7
d = {"A":0, "C":1, "G":2, "T":3}
dic = {}
dic_r = {}
for i0 in "ACGT":
    for i1 in "ACGT":
        for i2 in "ACGT":
            v = 4**2*d[i2] + 4*d[i1] + d[i0]
            k = i2+i1+i0
            dic[k] = v
            dic_r[v] = k

dp = [[0] * 64 for i in range(n)]
for i in range(64):
    dp[0][i] = 1
dp[0][dic["AGC"]] = 0
dp[0][dic["ACG"]] = 0
dp[0][dic["GAC"]] = 0
for i in range(n-3):
    for j in range(64):
        v = dic_r[j]
        for s in "ACGT":
            # AG*C
            if v[0] == "A" and v[1] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # A*GC
            elif v[0] == "A" and v[2] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *GAC
            elif v[1] == "G" and v[2] == "A":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *ACG
            elif v[1] == "A" and v[2] == "C":
                if s != "G":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            # *AGC
            elif v[1] == "A" and v[2] == "G":
                if s != "C":
                    new = v[1]+v[2]+s
                    dp[i+1][dic[new]] += dp[i][dic[v]]
            else:
                new = v[1] + v[2] + s
                dp[i+1][dic[new]] += dp[i][dic[v]]
    continue
print(sum(dp[n-3])%MOD)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    
    def isOk(i3, i2, i1, i0):
        if i2 == 0 and i1 == 1 and i0 == 2: return False
        if i2 == 1 and i1 == 0 and i0 == 2: return False
        if i2 == 0 and i1 == 2 and i0 == 1: return False
        if i3 == 0 and i1 == 1 and i0 == 2: return False
        if i3 == 0 and i2 == 1 and i0 == 2: return False
        return True
     
    dp = [[[[0 for _ in range(4)] for __ in range(4)] for ___ in range(4)] for ____ in range(N+1)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if isOk(None, i, j, k):
                    dp[3][i][j][k] = 1

    for n in range(3, N):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if not isOk(i, j, k, l):
                            continue
                        dp[n+1][j][k][l] += dp[n][i][j][k]
                        dp[n+1][j][k][l] %= (10**9)+7

    total = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                total += dp[N][i][j][k]
                total %= (10**9)+7
    print(total)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
def ch2int(ch):
    if ch == 'A':
        return 0
    elif ch == 'C':
        return 1
    elif ch == 'G':
        return 2
    else:
        return 3


def acgt2int(agct):
    ret = 0
    for ch in agct:
        ret = (ret << 2) + ch2int(ch)
    return ret


def int2acgt(val):
    ret = []
    tmp = val
    for i in range(3):
        amari = tmp % 4
        if amari == 0:
            ret.append('A')
        elif amari == 1:
            ret.append('C')
        elif amari == 2:
            ret.append('G')
        else:
            ret.append('T')
        tmp //= 4
    ret.reverse()
    return ret


n = int(input())
dp = [[0] * 64 for _ in range(n)]

dp[0][acgt2int('TTA')] = 1
dp[0][acgt2int('TTC')] = 1
dp[0][acgt2int('TTG')] = 1
dp[0][acgt2int('TTT')] = 1


def is_valid(chs):
    tmp = ''.join(chs)
    ng = ['AGC', 'GAC', 'ACG', 'AAGC', 'ACGC', 'AGGC',
          'ATGC', 'AGAC', 'AGCT', 'AGGC', 'AGTC']
    for item in ng:
        if item in tmp:
            return False
    return True


for i in range(1, n):
    for j in range(64):
        chs = int2acgt(j)
        tmp = 0
        for ch in ['A', 'C', 'G', 'T']:
            my_chs1 = [ch] + chs
            if is_valid(my_chs1):
                tmp += dp[i-1][acgt2int(my_chs1[:-1])] % (10 ** 9 + 7)
        dp[i][j] = tmp

print(sum(dp[-1]) % (10 ** 9 + 7))

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

#3<=N<=100

#i文字目がdの件数
#ACGT
mod=10**9+7
#NG
#AGC
#ACG
#GAC
#AGGC
#AGAC

index=[]
for s1 in "AGCT":
    for s2 in "AGCT":
        for s3 in "AGCT":
            for s4 in "AGCT":
                index.append(s1+s2+s3+s4)

#dp[i][bk]

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

if n==3:
    print(61)
    exit()
elif n==4:
    print(230)
    exit()

cnt=0
for i,item in enumerate(index):
    flag=0
    for ng in ["AGC","ACG","GAC","AGGC","ACGC","AGAC","ATGC","AGTC"]:
        if item==ng or item[1:]==ng or item[:-1]==ng:
            flag=1
    if flag==0:
        dp[3][index.index(item)]=1

for i in range(4,n):
    for j,item in enumerate(index):
        for s in "AGCT":
            ss=item[1:]+s
            flag=0
            for ng in ["AGC","ACG","GAC","AGGC","ACGC","AGAC","ATGC","AGTC"]:
                if ss==ng or ss[1:]==ng or ss[:-1]==ng:
                    flag=1
            if flag==0:
                dp[i][index.index(ss)]+=dp[i-1][j]%mod

print(sum(dp[-1])%mod)

Submission status: Accepted

Solution code:
n = int(input())

mod = 10 ** 9 + 7

if n == 3:
    print(61)
else:

    from collections import defaultdict
    from itertools import product
    keys = []
    for prod in product('AGCT', 'AGCT', 'AGCT', 'AGCT'):
        last = ''.join(prod)
        f = ('AGC' not in last)

        for i in range(len(last) - 1):
            last2 = list(last)
            last2[i], last2[i+1] = last2[i+1], last2[i]
            last2 = ''.join(last2)
            if 'AGC' in last2:
                f = False

        if f:
            keys.append(''.join(last))

    dp = dict()
    for key in keys:
        dp[key] = 1

    for _ in range(4, n):
        dp_new = defaultdict(int)

        for key in keys:
            for char in 'AGCT':
                last = (key + char)[1:]
                f = ('AGC' not in last)

                for i in range(len(last) - 1):
                    last2 = list(last)
                    last2[i], last2[i+1] = last2[i+1], last2[i]
                    last2 = ''.join(last2)
                    if 'AGC' in last2:
                        f = False

                if f:
                    dp_new[''.join(last)] += dp[key]

        dp = dict()
        for key in keys:
            dp[key] = dp_new[key] % mod

    print(sum(list(dp.values())) % mod)

Submission status: Accepted

Solution code:
# ABC122D - We Like AGC
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:
#!/usr/bin/env python3
import copy

n = int(input())

mod = 10**9+7

memo = {}

banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG',
          'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

count = 0


def dp(lettrs, state):

    if state in banned:
        return 0
    if lettrs == 0:
        return 1
    if (lettrs, state) in memo:
        return memo[lettrs, state]

    ans = 0
    for c in "ACGT":
        ans += dp(lettrs-1, (state+c)[-4:])
        ans %= mod
    ans %= mod
    memo[lettrs, state] = ans

    return ans


print(dp(n, ""))
# print(memo)
# AG = [0, 1]
# for i in range(2, n):
#     ans_pre = copy.deepcopy(ans)
#     ans = copy.deepcopy(ans_base)
#     print(ans_pre)
#     for key in ans_pre.keys():

#         for l in ["A", "C", "G", "T"]:

#             if key+l in miss:
#                 print(key+l)
#                 continue
#             else:
#                 # print((key+l))
#                 ans[(key+l)[1:]] += ans_pre[key] % mod
#     AG.append(ans["AG"])
#     print(AG)
#     ans["AC"] -= AG[-3]
#     ans["GC"] -= AG[-3]
#     ans["TC"] -= AG[-3]


# print(sum(ans.values()) % mod)

# AA
# AC
# AG
# AT
# CA
# CC
# CG
# CT
# GA
# GC
# GG
# GT
# TA
# TC
# TG
# TT

Submission status: Accepted

Solution code:
import re


def ok(last4):
    pattern = '.?AGC.?|.?GAC.?|.?ACG.?|A.GC|AG.C'
    res = re.match(pattern, last4)
    return res is None


def dfs(cur, last3, n, m, mod):
    if last3 in m[cur]:
        return m[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, n, m, mod)) % mod

    m[cur][last3] = ret
    return ret


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

    m = [{} for _ in range(n + 1)]
    ans = dfs(0, 'TTT', n, m, mod)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    n=int(readline())

    A=0
    T=1
    G=2
    C=3
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
    dp[0][T][T][T]=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==A and k==G and l==C:
                            pass
                        elif j==A and k==C and l==G:
                            pass
                        elif j==G and k==A and l==C:
                            pass
                        elif m==A and k==G and l==C:
                            pass
                        elif m==A and j==G and l==C:
                            pass
                        else:
                            dp[i][j][k][l]+=dp[i-1][m][j][k]
    ans=0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                ans+=dp[n][j][k][l]
                ans%=mod

    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

def judge(i, j, k):
    if i == 0 and j == 2 and k == 1:
        return False
    elif i == 0 and j == 1 and k == 2:
        return False
    elif i == 2 and j == 0 and k == 1:
        return False
    else:
        return True

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

def judge(j, k, l, m):
    if k == 0 and l == 2 and m == 1:
        return False
    elif k == 0 and l == 1 and m == 2:
        return False
    elif k == 2 and l == 0 and m == 1:
        return False
    elif j == 0 and l == 2 and m == 1:
        return False
    elif j == 0 and k == 2 and m == 1:
        return False
    else:
        return True

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):
                    dp[i][k][l][m] += dp[i - 1][j][k][l] * judge(j, k, l, m)
                    dp[i][k][l][m] %= 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 % mod)

Submission status: Accepted

Solution code:
n=int(input())
dp = [[[[0 for i in range(4)]for i in range(4)]for i in range(4)]for i in range(n)]
mod=10**9+7
for i in range(4):
    dp[0][0][0][i]=1

for i in range(n-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for st in range(4):
                    if i>=1:
                        if k==0 and l==1 and st==2:continue
                        if k==0 and l==2 and st==1:continue
                        if k==1 and l==0 and st==2:continue
                    if i>=2:
                        if j==0 and k==1 and st==2:continue
                        if j==0 and l==1 and st==2:continue
                    dp[i+1][k][l][st] = (dp[i+1][k][l][st]+dp[i][j][k][l])%mod


sum=0
for j in range(4):
    for k in range(4):
        for l in range(4):
            sum = (sum+dp[n-1][j][k][l])%mod

#print(*dp[n-1],sep="\n")
print(sum)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][-1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD   
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD  
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10**9 + 7

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
C = 2
G = 3
T = 4

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
M = 64
blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue
            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if not p3.startswith(q2):
                    continue
                if p3[1] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                if p3[0] == "G" and p3[2] == "C" and q3[0] == "A":
                    continue
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print(solve())

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
MOD = 10 ** 9 + 7
AGCT3 = ["".join(x) for x in itertools.product("AGCT", repeat=3)]
A, G, C, T = 0, 1, 2, 3
M = 64

blacklist3 = {"AGC", "ACG", "GAC"}


def solve():
    dp = [[0] * M for _ in range(N + 1)]
    for i in range(M):
        if AGCT3[i] not in blacklist3:
            dp[3][i] = 1
    for i in range(4, N + 1):
        for j in range(M):
            p3 = AGCT3[j]
            if p3 in blacklist3:
                dp[i][j] = 0
                continue

            if p3[1] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            if p3[0] == "G" and p3[2] == "C":
                for k in range(M):
                    q3 = AGCT3[k]
                    q2 = q3[1:]
                    if p3.startswith(q2) and q3[0] != "A":
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= MOD
                continue

            for k in range(M):
                q3 = AGCT3[k]
                q2 = q3[1:]
                if p3.startswith(q2):
                    dp[i][j] += dp[i - 1][k]
                    dp[i][j] %= MOD
    ans = 0
    for x in dp[N]:
        ans = (ans + x) % MOD
    return ans


print(solve())

Submission status: Accepted

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

for i in range(N):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        if dp[i][j][k][l] == 0:
          continue

        for m in range(4):
          if k == 1 and l == 0 and m == 2: # GAC
            continue
          if k == 0 and l == 2 and m == 1: # ACG
            continue
          if k == 0 and l == 1 and m == 2: # AGC
            continue
          if j == 0 and l == 1 and m == 2: # A?GC
            continue
          if j == 0 and k == 1 and m == 2: # AG?C
            continue
          dp[i+1][k][l][m] += dp[i][j][k][l]
          dp[i+1][k][l][m] %= mod

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

Submission status: Accepted

Solution code:
"""
AtCoder Beginner Contest 122  D - We Like AGC

愚直解
・N文字のうち、各文字についてA,C,G,Tの4通りを取りうるので、4^N
・できた文字について、AGCを含まないか確認：N
・隣接する2文字を一回だけ入れ替えて、AGCができないか確認：N
なので、4^N * N * N ぐらいか？後ろ二つはまとめてもいいが。
また、AAAGCでNGなのがわかっているのに、AAAGCAAを作って調べる〜みたいな重複もいけてない。
このような重複を避けるには、小さい問題からメモ化で解決するDPがよいと思う

入れ替えてAGCができる時、
GAC -> AGC か、 ACG -> AGC、　AXGC -> XAGC、　AGXC -> AGCX
なので、作っている文字列の右端から3文字がわかって入れば行けそう


dp[i+1][j(i-2文字目)][k(i-1文字目)][l(i文字目)]：i文字目をl、一個手前をk、もう一個手前をjとした時の文字列の個数
とすると

遷移
・dp[i+1][A][G][C], dp[i+1][G][A][C], dp[i+1][A][C][G] :こいつらは作ってはいけない
・dp[i][A][＊][G] -> dp[i+1][*][G][C] : Aと* を入れ替えるとAGCができるのでNG
・dp[i][A][G][*] -> dp[i+1][G][*][C] : *とCを入れ替えるとAGCになるのでだめ

上の遷移はなんかややこしいので、ざっくりまとめると、　・・・pqrs　と並んでいて、pqrsについて、
A,G,*,C
A,*,G,C
*,A,G,C,
*,G,A,C
*,A,C,G
がアウトで他はOK
これをDPでやるとよい

最後に末尾3文字について、全パターン見て足し合わせる。


"""

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

# dp[i+1][j(i-2文字目)][k(i-1文字目)][l(i文字目)]：i文字目をl、一個手前をk、もう一個手前をjとした時の文字列の個数
# j,k,lについて、A=1,C=2,G=3,T=4, 初期化の都合上0もある
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
C = 2
G = 3
T = 4

for i in range(N):
    # 初期値をうまく利用したいので、p,q,rは0~4まで
    for p in range(5):
        for q in range(5):
            for r in range(5):
                # sをA,C,G,Tで動かす
                for s in range(1, 5):
                    # ・・・・・pqrsの並びにできるか考える
                    """
                    A,G,*,C
                    A,*,G,C
                    *,A,G,C,
                    *,G,A,C
                    *,A,C,G
                    がアウト
                    """
                    if p == A and q == G and s == C : continue
                    if p == A and r == G and s == C : continue
                    if q == A and r == G and s == C : continue
                    if q == G and r == A and s == C : continue
                    if q == A and r == C and s == G : continue

                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD


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


print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
dp[0][3][3][3] = 1
for len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[len][i][j][k] == 0: continue

                for l in range(4):
                    if l == 2 and i == 1 and j == 0: continue
                    if l == 2 and i == 0 and j == 1: continue
                    if l == 1 and i == 2 and j == 0: continue
                    if l == 2 and i == 1 and k == 0: continue
                    if l == 2 and j == 1 and k == 0: continue
                    dp[len + 1][l][i][j] += dp[len][i][j][k]
                    dp[len + 1][l][i][j] %= 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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

dp = [[[[0]*5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
ng_3 = [(0, 1, 2), (0, 2, 1), (1, 0, 2)]
dp[0][4][4][4] = 1
for i in range(n):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                for m in range(4):
                    if (m, j, k) in ng_3 or (m == 0 and k == 1 and l == 2) or (m == 0 and j == 1 and l == 2):
                        continue
                    dp[i + 1][m][j][k] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
c = [0, 1, 2, 3]
import itertools
pers = itertools.product(c, repeat=3)
ng_3 = [(0, 1, 2), (0, 2, 1), (1, 0, 2)]
for p in pers:
    if p in ng_3:
        continue
    dp[3][p[0]][p[1]][p[2]] = 1
for i in range(3, n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if (m, j, k) in ng_3 or (m == 0 and k == 1 and l == 2) or (m == 0 and j == 1 and l == 2):
                        continue
                    dp[i + 1][m][j][k] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
c = [0, 1, 2, 3]
import itertools
pers = itertools.product(c, repeat=3)
for p in pers:
    if p in [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
        continue
    dp[3][p[0]][p[1]][p[2]] = 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 [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
                    continue
                elif (j == 0 and l == 1) or (j == 0 and k == 1):
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4) if x != 2])
                else:
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4)])
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans % (10**9 + 7))

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):
        t = list(last4)
        if i >= 1:
            t[i - 1], t[i] = t[i], t[i - 1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


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

print (dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
import itertools

ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

N = int(input())

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

for i, p, q, r, s in itertools.product(range(N), range(5), range(5), range(5), range(4)):
    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
        dp[i + 1][q][r][s] += dp[i][p][q][r]
        dp[i + 1][q][r][s] %= MOD

print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Accepted

Solution code:
ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

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

dp[0][4][4][4] = 1
for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(4):
                    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
                            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
                            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
                        dp[i + 1][q][r][s] += dp[i][p][q][r]
                        dp[i + 1][q][r][s] %= MOD

print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Accepted

Solution code:
N = int(input())
A = ['A', 'C', 'G', 'T']
dp = [[0]*64 for _ in range(N+1)]
MOD = 10**9+7

for i in range(4):
    for j in range(4):
        for k in range(4):
            if A[i]+A[j]+A[k] in ['AGC', 'ACG', 'GAC']:
                continue

            dp[3][16*k+4*j+i] = 1
    
for i in range(3, N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if A[k]+A[l]+A[m] in ['AGC', 'ACG', 'GAC']:
                        continue
                    
                    if A[j]+A[l]+A[m]=='AGC':
                        continue
                    
                    if A[j]+A[k]+A[m]=='AGC':
                        continue
                    
                    dp[i+1][16*m+4*l+k] += dp[i][16*l+4*k+j]
                    dp[i+1][16*m+4*l+k] %= MOD

print(sum(dp[N])%MOD)

Submission status: Accepted

Solution code:
# T:0 A:1 G:2 C:3 

N = int(input())
dp = [[[[0] * 4 for i in range(4)] for j in range(4)] for k in range(N+1)]
dp[0][0][0][0] = 1
mod = 10 ** 9 + 7
for n in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for NEXT in range(4):
          if j == 1 and k == 2 and NEXT == 3:
            continue
          if j == 1 and k == 3 and NEXT == 2:
            continue
          if j == 2 and k == 1 and NEXT == 3:
            continue
          if i == 1 and j == 2 and NEXT == 3:
            continue
          if i == 1 and k == 2 and NEXT == 3:
            continue
          dp[n+1][j][k][NEXT] += dp[n][i][j][k]
          dp[n+1][j][k][NEXT] %= mod
          
ans = 0
for i in dp[N]:
  for j in i:
    for k in j:
      ans += k
ans %= mod
print(ans)