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 sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    MOD = 10**9+7
    A,T,G,C = 0,1,2,3
    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 i==A and j==G and k==C:
                    continue
                if i==A and j==C and k==G:
                    continue
                if i==G and j==A and k==C:
                    continue
                dp[3][i][j][k] = 1

    if N == 3:
        print("61")
    else:
        for n in range(4,N+1):
            for i in range(4):
                for j in range(4):
                    for k in range(4):
                        for l in range(4):
                            if i==A and j==G and k==C:
                                continue
                            if i==A and j==C and k==G:
                                continue
                            if i==G and j==A and k==C:
                                continue
                            if l==A and i==G and k==C:
                                continue
                            if l==A and j==G and k==C:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= 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)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

base = ['A', 'C', 'G', 'T']
base3 = list(itertools.product(base, repeat=3))
index_dict = dict(zip(base3, range(64)))


def is_NG(b, s):
  for i in range(4):
    lb = list(b) + [s]
    if i >= 1:
      lb[i-1], lb[i] = lb[i], lb[i-1]
    if ''.join(lb).count('AGC') == 1:
      return True
  return False


# 0:A->A->A, 1:A->A->C, 2:A->A->G, 3:A->A->T, ...
dp = [[0]*64 for i in range(N)]
dp[2] = [1] * 64
for b in [('A', 'G', 'C'), ('A', 'C', 'G'), ('G', 'A', 'C')]:
  dp[2][index_dict[b]] = 0


for i in range(3, N):
  for j in range(64):
    b = base3[j]
    if is_NG(b, 'C'):
      for s in 'AGT':
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][j]
        dp[i][idx] %= MOD
    elif is_NG(b, 'G'):
      for s in 'ACT':
        idx = index_dict[('A', 'C', s)]
        dp[i][idx] += dp[i-1][j]
    else:
      for s in 'ACGT':
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][j]
        dp[i][idx] %= MOD
        

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

Submission status: Accepted

Solution code:
import itertools

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

base = ['A', 'C', 'G', 'T']
base3 = list(itertools.product(base, repeat=3))
index_dict = dict(zip(base3, range(64)))

s0 = set((('A', 'G', 'C'), ('A', 'C', 'G'), ('G', 'A', 'C')))
s1 = set((('A', 'A', 'G'), ('C', 'A', 'G'), ('G', 'A', 'G'), ('T', 'A', 'G')))
s2 = set((('A', 'A', 'G'), ('A', 'C', 'G'), ('A', 'G', 'G'), ('A', 'T', 'G')))
s3 = set((('A', 'G', 'A'), ('C', 'G', 'A'), ('G', 'G', 'A'), ('T', 'G', 'A')))
s4 = set((('A', 'G', 'A'), ('A', 'G', 'C'), ('A', 'G', 'G'), ('A', 'G', 'T')))
s5 = set((('A', 'A', 'C'), ('C', 'A', 'C'), ('G', 'A', 'C'), ('T', 'A', 'C')))

# 0:A->A->A, 1:A->A->C, 2:A->A->G, 3:A->A->T, ...
dp = [[0]*64 for i in range(N)]

for j in range(64):
  if base3[j] in s0:
    continue
  
  dp[2][j] = 1


for i in range(3, N):
  for j in range(64):
    b = base3[j]
    idx_b = index_dict[b]
    if b in s1 or b in s2 or b in s3 or b in s4:
      for s in ['A', 'G', 'T']:
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][idx_b]
        dp[i][idx] %= MOD
    elif b in s5:
      for s in ['A', 'C', 'T']:
        idx = index_dict[('A', 'C', s)]
        dp[i][idx] += dp[i-1][idx_b]
    else:
      for s in ['A', 'C', 'G', 'T']:
        idx = index_dict[(b[1], b[2], s)]
        dp[i][idx] += dp[i-1][index_dict[b]]
        dp[i][idx] %= MOD
        

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

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
h = {
 'AG':1,
 'CG':1,
 'AGG':0,
 'aGG':1,
 'ATG':0,
 'aTG':1,
 'GA':1,
 'gA':3,
 'AC':1,
 'aC':3,
 'AT':1,
 'AGT':0,
 'aGT':1,
 'agT':2
}
for i in range(2,n):
    g = {}
    g['AG'] = h['GA']+h['gA']
    g['CG'] = h['aC']
    g['AGG'] = h['AG']
    g['aGG'] = h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['ATG'] = h['AT']
    g['aTG'] = h['AGT']+h['aGT']+h['agT']
    g['GA'] = h['AG']+h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['gA'] = h['GA']+h['gA']+h['AC']+h['aC']+h['AT']+h['AGT']+ \
             h['aGT']+h['agT']
    g['AC'] = h['gA']
    g['aC'] = h['AC']+h['aC']+h['AT']+ \
             h['aGT']+h['agT'] + \
             h['CG']+h['aTG']+h['aGG']
    g['AT'] = h['GA']+h['gA']
    g['AGT'] = h['AG']
    g['aGT'] = h['CG']+h['AGG']+h['aTG']+h['aGG']+h['ATG']
    g['agT'] = h['AC']+h['aC']+h['AT']+h['AGT']+ \
             h['aGT']+h['agT']
    h = g
sm = 0
for k in h:
    sm = (sm+h[k])%R
print(sm)

Submission status: Accepted

Solution code:

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

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

dp = [ [[[0 for c3 in range(4)]  for c2 in range(4)]  for c1 in range(4)] for n in range(N+1)]

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

for n in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for new in range(4):
          if c2 == A and c1 == G and new == C: continue
          if c2 == A and c1 == C and new == G: continue
          if c2 == G and c1 == A and new == C: continue
          if c3 == A and c1 == G and new == C: continue
          if c3 == A and c2 == G and new == C: continue

          dp[n+1][c2][c1][new] += dp[n][c3][c2][c1]      

ans = 0
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      ans += dp[N][c1][c2][c3]

print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10**9 + 7


n = int(input())

def satisfy(s):
    for i in range(4):
        S = list(s)
        if i >= 1:
            S[i - 1], S[i] = S[i], S[i - 1]
        if "AGC" in "".join(S):
            return False
    return True

def dfs(depth, last4):
    if depth == n:
        if satisfy(last4):
            return 1
        else:
            return 0
    if last4 in MEMO[depth]:
        return MEMO[depth][last4]
    if satisfy(last4):
        ret = 0
        for c in "ACGT":
            ret += dfs(depth + 1, last4[1:] + c)
            ret %= mod
        MEMO[depth][last4] = ret
        return ret
    else:
        return 0

MEMO = [{} for _ in range(n + 1)]
print(dfs(0, "TTTT"))

Submission status: Accepted

Solution code:
# ちーともわからんので解説見た
# ら、悔しさあふれる感じ
# NGになる文字の並びは限定される。3文字のものは"ACG" "GAC", 4文字のものは"AxGC", "AGxC"
# ここで, "AAGC"とか"AGCC"なんてのを考え出すと「すでに"AGC"が含まれとるやんけ」->（だから何？）みたいなよくわからん思考に陥ってしまった
# （いまみてるのとそれ以前の3つを保存して探索すると結局かぶらず全探索できるので考えなくていい）

# n = input()

# なんで？？？？？？？？？？？
# これが無限ループになるの？？？？？？？？？？？？？？？？
# は？？？？？？？？？？？？？？？？？？？？？？？？？？？
# def f(i, s):
#     if i == n:
#         return 1
#     # print("now s : {}".format(s))
#     ret = 0
#     for c in "ACGT":
#         print(s + c)
#         is_include = True if "AGC" in s + c else False
#         if is_include:
#             continue
#         ret += f(i + 1, s[1:] + c)
#     return ret
# print(f(0, "xxx"))
# coding: utf-8
# Your code here!

n = int(input())
memo = {}


def f(i, s):
    if (i, s) in memo:
        return memo[(i, s)]
    if i == n:
        return 1
    ret = 0
    for c in "AGCT":
        flag = False
        for j in range(4):
            t = list(s + c)
            if j >= 1:
                t[j], t[j - 1] = t[j - 1], t[j]
            if "AGC" in "".join(t):
                flag = True
        if not flag:
            ret += f(i + 1, s[1:] + c)
            ret %= 10 ** 9 + 7
    memo[(i, s)] = ret
    return ret


print(f(0, "TTT"))

Submission status: Accepted

Solution code:
n=int(input())
alph=["A","C","G","T"]
a=[alph[i]+alph[j]+alph[k] for i in range(4) for j in range(4) for k in range(4)]
#print(len(a))
d1={l:0 for l in a}
for i in d1:
    if i!="AGC" and i!="ACG" and i!="GAC":
        d1[i]=1
d2={l:0 for l in a}
for i in range(n-3):
    for j in d1:
        next=[j+alph[k] for k in range(4)]
        for k in range(4):
            l=next[k]
            if l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC":
                #print(l)
                pass
            elif l[0]=="A" and l[3]=="C" and (l[1]=="G" or l[2]=="G"):
                #rint(l)
                pass
            else:
                d2[l[1:]]+=d1[j]
    for j in d1:
        d1[j]=d2[j]
        d2[j]=0
print(sum(d1.values())%(1000000007))

Submission status: Accepted

Solution code:
N=int(input())
#含んではいけない
#AGC
#GAC
#ACG
#ACGC
#AGGC
#ATGC
#AGAC
#AGTC

# AAA,AAC,AAG...という3文字セットの組み合わせ64通り
from collections import deque
stack=deque([""])
buf=[]
while stack:
  s=stack.popleft()
  if len(s)==3:
    buf.append(s)
    continue
  for c in ("ACGT"):
    stack.append(s+c)

# dp["XXX"] : 直近3文字がXXXになっている場合の数のDP
dp={}
for b in buf:
  dp[b]=[0 for i in range(N+1)]
  if b not in ("AGC","ACG","GAC"):
    dp[b][3]=1

# ある3文字に対して次に来てはいけない文字
NG={
  "ACG":"C",
  "AGG":"C",
  "ATG":"C",
  "AGA":"C",
  "AGT":"C"
}
DIV=10**9+7

for i in range(3,N):
  for item in dp.items():
    key=item[0]
    value=item[1]
    ngnex=""
    if key in NG:
      ngnex=NG[key]
    las2=key[1:]
    for c in ("ACGT"):
      if las2+c in ("AGC","ACG","GAC"):
        continue
      if c!=ngnex:
        dp[las2+c][i+1]+=dp[key][i]
        dp[las2+c][i+1]%=DIV

ans=0
for v in dp.values():
  ans+=v[-1]
print(ans%DIV)

Submission status: Accepted

Solution code:
# maspyさんの見て書いた。
# 最初自分で書いたけど、改善していたらほぼ写経になってしまった。。。

from collections import defaultdict

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

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

def check(s):
    if 'AGC' in s:
        return False
    for i in range(len(s)-1):
        l = list(s)
        l[i],l[i+1]=l[i+1],l[i]
        t = ''.join(l)
        if 'AGC' in t:
            return False
    return True

for i in range(n):
    for k,v in dp[i].items():
        for x in 'AGCT':
            y = k[-3:]+x
            if check(y):
                dp[i+1][y]+=v

print(sum(dp[n].values())%m)

Submission status: Accepted

Solution code:
# 末尾3つの塩基配列を4進数で表記して記録する。

def base_10to(n,m):
    if (n//m):
        return base_10to(n//m, m) + str(n%m)
    return str(n%m)


def base_10from(n,m):
    a = 0
    for i in range(len(n)):
        a*=m
        a+=int(n[i])
    return a


n = int(input())

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


for i in range(64):
    a = base_10to(i,4)
    a= a.zfill(3)
    if a=='012' or a=='102' or a=='021':
        dp[2][i]=0
    else:
        dp[2][i]=1

for i in range(2,n-1):
    for j in range(64):
        a = base_10to(j, 4)
        a = a.zfill(3)
        if a[1:]=='02':
            for k in [0,2,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]
        elif a[1:]=='10' or a[1:]=='01' or a[:2]=='01' or (a[0]=='0' and a[2]=='1'):
            for k in [0,1,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]
        else:
            for k in [0,1,2,3]:
                dp[i+1][base_10from(a[1:]+str(k),4)] += dp[i][j]

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

Submission status: Accepted

Solution code:
from functools import lru_cache


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


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 ''.join(t).count('AGC') > 0:
            return False
    return True


@lru_cache(maxsize=1000)
def dfs(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
    return ret


print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4)])%MOD for d in range(4)])%MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4) for d in range(4)])%MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[0][1][2][x]=0
    tmp[2][0][1][x]=0
    tmp[0][2][1][x]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4) for d in range(4)])%MOD)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9+7
n = int(input())
dp = np.zeros((n+1, 4, 4, 4), dtype=np.int64)
dp[0, 3, 3, 3] = 1
for i in range(n):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for d in range(4):
          if d==1:
            if (a==0 and b==2) or (a==0 and c==2) or (b==0 and c==2) or (c==0 and b==2):
              continue
          if b==0 and d==2 and c==1:
            continue
          dp[i+1, b, c, d] += dp[i, a, b, c]
          dp[i+1, b, c, d] %= MOD
print(dp[n].sum()%MOD)

Submission status: Accepted

Solution code:
p = 10**9+7
N = int(input())
dp = [[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not(j==0 and k==1 and l==2) and not(j==0 and k==2 and l==1) and not(j==1 and k==0 and l==2):
                dp[3][0][j][k][l] = 1
for n in range(4,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not(j==0 and k==1 and l==2) and not(j==0 and k==2 and l==1) and not(j==1 and k==0 and l==2) \
                    and not(i==0 and k==1 and l==2) and not(i==0 and j==1 and l==2):
                        dp[n][i][j][k][l] = 0
                        for m in range(4):
                            dp[n][i][j][k][l] = (dp[n][i][j][k][l]+dp[n-1][m][i][j][k])%p
tot = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                tot = (tot + dp[N][i][j][k][l])%p
print(tot)

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def ok(W):
    if W.count("AGC") >= 1:
        return False

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


def main():
    mod = 10 ** 9 + 7
    dp = {}
    W = "ACGT"
    for a in W:
        for b in W:
            for c in W:
                w = a + b + c
                if w in ("AGC", "ACG", "GAC"):
                    continue
                dp[w] = 1

    N = int(input())
    for n in range(N - 3):
        dp2 = {}
        for a in dp.keys():
            for b in W:
                if ok(a + b):
                    w = a[1:] + b
                    dp2[w] = (dp[a] + dp2.setdefault(w, 0)) % mod
        dp.update(dp2)
    print(sum(v for v in dp.values()) % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

def check1(a,b,c):
    t=[a,b,c]
    if t==[1,2,4] or t==[1,4,2] or t==[2,1,4]:
        return False
    return True

def check2(a,b,c,m):
    if ([b,c]==[2,4] and m==1) or ([a,c]==[2,4] and m==1):
        return False
    return check1(a,b,c)
    
    
#初期化
for n in range(min(4,N+1)):
    for i in range(A):
        for j in range(A):
            for k in range(A):
                if check1(i,j,k):
                    dp[n][i][j][k]=1
                    
for n in range(4,N+1):
    for i in range(1,A):
        for j in range(1,A):
            for k in range(1,A):
                for m in range(1,A):
                    if check2(i,j,k,m):
                        dp[n][i][j][k]+=dp[n-1][m][i][j]
                dp[n][i][j][k]%=mod
                        
ans=0
if N>=3:
    for i in range(1,A):
            for j in range(1,A):
                for k in range(1,A):
                    ans+=dp[N][i][j][k]

if N==1:
    ans=4
elif N==2:
    ans=16

print(ans%mod)

Submission status: Accepted

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


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

def check1(a,b,c):
    t=[a,b,c]
    if t==[1,2,4] or t==[1,4,2] or t==[2,1,4]:
        return False
    return True

def check2(a,b,c,m):
    if ([b,c]==[2,4] and m==1) or ([a,c]==[2,4] and m==1):
        return False
    return check1(a,b,c)
    
    
#初期化
for n in range(min(4,N+1)):
    for i in range(A):
        for j in range(A):
            for k in range(A):
                if check1(i,j,k):
                    dp[n][i][j][k]=1
                    
for n in range(4,N+1):
    for i in range(1,A):
        for j in range(1,A):
            for k in range(1,A):
                for m in range(1,A):
                    if check2(i,j,k,m):
                        dp[n][i][j][k]+=dp[n-1][m][i][j]
                dp[n][i][j][k]%=mod
                        
ans=0
if N>=4:
    for i in range(1,A):
            for j in range(1,A):
                for k in range(1,A):
                    ans+=dp[N][i][j][k]

if N==1:
    ans=4
elif N==2:
    ans=16
elif N==3:
    ans=61

print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
A,G,C,T,mod,ans=0,1,2,3,pow(10,9)+7,0
dp=[[[[0]*4for k in range(4)]for j in range(4)]for i 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(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):
            dp[i][k][l][m]+=dp[i-1][j][k][l]
            dp[i][k][l][m]%=mod
for j in range(4):
  for k in range(4):
    for l in range(4):
      ans+=dp[n][j][k][l]
print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())

DIVIDER = 1000000007

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

tab_pow4 = [1]
tab_tmp = 1
for i in range(N):
    tab_tmp *= 4
    tab_pow4.append(tab_tmp)

def dp(Nlen, end):
    if Nlen < len(end):
        return 0
    elif memo[Nlen].setdefault(end, None) != None:
        return memo[Nlen][end]
    #
    if end in ('AGC', 'GAC', 'ACG'):
        ret = 0
    elif Nlen == len(end):
        ret = 1
    else:
        ret = 0
        if end not in ('AGC', 'TGC', 'CGC', 'GGC', 'GAC', 'GTC', 'GCC', 'GGC'):
            ret = (ret + dp(Nlen - 1, 'A' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'C' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'G' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'T' + end[:2])) % DIVIDER
    #
    memo[Nlen][end] = ret
    return ret

import itertools

ans = 0
for end in itertools.product('ACGT', repeat=3):
    if end in ('AGC', 'CAG', 'ACG'): continue
    ans = (ans + dp(N, ''.join(end))) % DIVIDER

# for i in range(N + 1):
#     print("#", memo[i], sum(memo[i].values()))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

memo = [{} for _ in range(N)]  # i 文字目に dict.key がきたとき, これ以降を何通りあるか を保存する


def judge(last):
    if last[1:] in ('AGC', 'ACG', 'GAC'):
        return False
    if last[0] == 'A':
        if last[1] == 'G' and last[-1] == 'C': return False
        if last[2] == 'G' and last[-1] == 'C': return False
    return True


MOD = 10 ** 9 + 7


def dfs(i, last):
    if i >= N:  # 末尾
        return 1

    if last in memo[i]:
        return memo[i][last]

    res = 0
    for c in 'AGCT':
        l = last[1:] + c
        if judge(l):
            res += dfs(i + 1, l) % MOD
    memo[i][last] = res % MOD
    return res


print(dfs(0, 'XXXX') % MOD)

Submission status: Accepted

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


def isOK(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'):
            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 isOK(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:
from collections import Counter


MOD = 10 ** 9 + 7


def isOK(last3, s):
    for i in range(len(last3 + s)):
        t = list(last3 + s)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).count('AGC'):
            return False
    return True


S = 'ACGT'
N = int(input())
dp = [None] * (N + 1)

dp[1] = Counter()
for s1 in S:
    dp[1][s1] += 1

dp[2] = Counter()
for s1 in S:
    for s2 in S:
        dp[2][s1 + s2] += dp[1][s1]

dp[3] = Counter()
for s1 in S:
    for s2 in S:
        for s3 in S:
            if isOK(s1 + s2, s3):
                dp[3][s1 + s2 + s3] += dp[2][s1 + s2]

for i in range(4, N + 1):
    dp[i] = Counter()
    for s1 in S:
        for s2 in S:
            for s3 in S:
                for s4 in S:
                    if isOK(s1 + s2 + s3, s4):
                        dp[i][s2 + s3 + s4] += dp[i - 1][s1 + s2 + s3]
                        dp[i][s2 + s3 + s4] %= MOD

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import re
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    def is_ok(S):
        if re.match(r'(.?(AGC|GAC|ACG).?|A(.G|G.)C)',S):
            return False
        else:
            return True
    memo=[{} for _ in range(N+1)]
    def saiki(i,last3):
        if last3 in memo[i]:
            return memo[i][last3]
        if i==N:
            return 1
        c=0
        for s in 'ATGC':
            if is_ok(last3+s):
                c+=saiki(i+1,last3[1:]+s)
                c%=MOD
        memo[i][last3]=c
        return c
    print(saiki(0,'TTT'))
            
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp[0][0][0][0] = 1 
A, G, C, T = 0, 1, 2, 3

for i in range(N):
    for c1 in range(4): 
        for c2 in range(4): 
            for c3 in range(4): 
                for c in range(4): 
                    if (c, c1, c2) in [(A,G,C), (G,A,C), (A,C,G)]:
                        continue
                    if (c, c2, c3) == (A,G,C):
                        continue
                    if (c, c1, c3) == (A,G,C):
                        continue
                    dp[i+1][c][c1][c2] += (dp[i][c1][c2][c3] % MOD)

ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[N][c3][c2][c1]

print(ans % MOD)

Submission status: Accepted

Solution code:
N, MOD = int(input()), 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):
    global N, MOD, memo

    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:
from datetime import datetime as dt
import itertools
N = int(input())
dp = [ [[[0 for _ in range(N + 1) ]for _ in range(5)] for _ in range(5)] for _ in range(5)]

# c1 c2 c3
# 0: dammy (DP を初期化するのにこれがあると便利)
# for c2 in range(4):
#     for c3 in range(4):
#         for c1 in range(4):
#             dp[c3][c2][c1][2] = 1 #末尾2文字に関してDP (規約違反に関しては，
        # 規約違反でない文字列の末尾2文字に対して1文字加えたときに判断できるので)
MOD = 10 ** 9 + 7

dp[0][0][0][0] = 1 # 0→ 存在しない の意味
A = 1
G = 2
C = 3
T = 4

# ~~~~ c1 c2
for i in range(0,N):
    for c1 in range(5): #1文字前
        for c2 in range(5): #2文字前
            for c3 in range(5): # 3文字前
                for c in range(1,5): # 新たな文字を加える
                    if c2 == A and c1 == G and c == C:
                        continue
                    if c3 == A and c2 == G and c == C:
                        continue
                    if c3 == A and c1 == G and c == C:
                        continue
                    if c2 == G and c1 == A and c == C:
                        continue
                    if c2 == A and c1 == C and c == G:
                        continue
                    dp[c2][c1][c][i + 1] +=(dp[c3][c2][c1][i] % MOD)


ans = 0
for c1 in range(1,5):
    for c2 in range(1,5):
        for c3 in range(1,5):
            ans += dp[c3][c2][c1][N]
        # print(f"{alpha[c1] + alpha[c2]}: {dp[c1][c2][N]}")

print(ans % MOD)

Submission status: Accepted

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

N = int(input())

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

for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    if b == 1 and c == 3 and d == 2: # AGC
                        continue
                    if b == 1 and c == 2 and d == 3: # ACG
                        continue
                    if b == 3 and c == 1 and d == 2: # GAC
                        continue
                    if N <= 3:
                        dp[i+1][b][c][d] = 1
                        continue
                    if a == 1 and b == 3 and d == 2: # AGXC
                        continue
                    if a == 1 and c == 3 and d == 2: # AXGC
                        continue
                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d] %= ((10**9)+7)

ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += dp[N][a][b][c]
            ans %= ((10**9)+7)

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    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

    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 == 0 and l == 1 and m == 2:
                            continue
                        if k == 0 and l == 2 and m == 1:
                            continue
                        if k == 1 and l == 0 and m == 2:
                            continue
                        if j == 0 and k == 1 and m == 2:
                            continue
                        if j == 0 and l == 1 and m == 2:
                            continue

                        dp[i + 1][k][l][m] += dp[i][j][k][l]
                        dp[i + 1][k][l][m] %= MOD

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

    print(ans % MOD)


    

    

if __name__ == '__main__':
    main()