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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
acgt = ["A", "C", "G", "T"]
dp = {acgt[i]+acgt[j]+acgt[k]: 1 for i in range(4) for j in range(4) for k in range(4)}
dp["AGC"] = 0
dp["ACG"] = 0
dp["GAC"] = 0

for i in range(n-3):
    next_dp = {key: 0 for key in dp.keys()}
    for key, val in dp.items():
        for item in acgt:
            next_key = key + item
            if next_key[1:] == "AGC" or next_key[1:] == "ACG" or next_key[1:] == "GAC":
                continue
            elif next_key[0] + next_key[2:] == "AGC" or next_key[:2] + next_key[3] == "AGC":
                continue
            else:
                next_dp[next_key[1:]] = (next_dp[next_key[1:]] + val) % mod
    dp = next_dp
print(sum(dp.values()) % mod)

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)]
dp[0][0][0][0]=1
MOD=10**9+7
# 0,1,2,3
# T,A,C,G
# NG
# AGC:132
# GAC:312
# ACG:123
# A?GC:1?32
# AG?C:13?2

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): # nxt
                    if b==1 and c==3 and d==2: # AGC
                        continue
                    if b==3 and c==1 and d==2: # GAC
                        continue
                    if b==1 and c==2 and d==3:  # ACG
                        continue
                    if a==1 and c==3 and d==2:  # ACG
                        continue
                    if a==1 and b==3 and d==2:  # ACG
                        continue

                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d]%=MOD
ans=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans+=dp[-1][a][b][c]
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

N = int(input())
mod = 10 ** 9 + 7
L = [{} for i in range(101)]

def check(txt):
    if 'AGC' in txt:
        return False
    List = list(txt)
    for i in range(3):
        List[i], List[i+1] = List[i+1], List[i]
        if 'AGC' in ''.join(List):
            return False
        List[i], List[i+1] = List[i+1], List[i]
    return True
    
def dfs(i, txt):
    if i == N:
        return 1
    if txt in L[i]:
        return L[i][txt]
    ans = 0
    for char in 'AGCT':
        if check(txt[1:] + char):
            ans += dfs(i+1, txt[1:] + char)
    L[i][txt] = ans % mod
    return ans % mod

print(dfs(0, 'TTTT'))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9+7
# dp[i][j][k][l]:文字列長iで,後ろから3文字目がj,2文字目がk,1文字目がlの文字列の個数
#                ただしA:0,C:1,G:2,T:3とする。
dp= [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(101)]
# 文字列長0の文字列Sは、333+Sと考えてよい。
dp[0][3][3][3] = 1
for i in range(100):
  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):
          # 条件を満たさないパターンを除外する。
          # 条件を満たさないのは、文字列の末尾が下記の場合。
          # 021,201,021,0?21,02?1
          if k == 0 and l == 2 and m == 1:
            continue
          if k == 2 and l == 0 and m == 1:
            continue
          if k == 0 and l == 1 and m == 2:
            continue
          if j == 0 and l == 2 and m == 1:
            continue
          if j == 0 and k == 2 and m == 1:
            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]
      ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
"""
?AGC
AG?C
A?GC
?ACG
?CAG
"""

n = int(input())

# dp i文字目までのパターン　前の3文字を保存する
import itertools
l = ["A", "G", "C", "T"]
pl = itertools.product(l, repeat=3)

dic = dict()
dic2 = dict()
from collections import defaultdict
ng_list = defaultdict(int)


for idx, p in enumerate(pl):
    dic[idx] = p
    dic2[p] = idx

pl = itertools.product(l, repeat=4)
for idx, p in enumerate(pl):
    if p[1] == "A" and p[2] == "G" and p[3] == "C":
        ng_list[p] = 1
    elif p[0] == "A" and p[1] == "G" and p[3] == "C":
        ng_list[p] = 1
    elif p[1] == "A" and p[2] == "C" and p[3] == "G":
        ng_list[p] = 1
    elif p[1] == "G" and p[2] == "A" and p[3] == "C":
        ng_list[p] = 1
    elif p[0] == "A" and p[2] == "G" and p[3] == "C":
        ng_list[p] = 1

pl = itertools.product(l, repeat=3)
dic3 = dict()
dic4 = dict()
for idx, p in enumerate(pl):
    dic3[idx] = p
    dic4[p] = idx

dp = [[0 for _ in range(4**3)] for _ in range(n+1)]
dp[0][dic4[("T", "T", "T")]] = 1
MOD = 10 ** 9 + 7
for i in range(n):
    for j in range(4**3):
        for k in l:
            if ng_list[dic3[j] + (k,)] == 0:
                dp[i+1][dic4[dic3[j][1:] + (k,)]] += dp[i][j]
                dp[i+1][dic4[dic3[j][1:] + (k,)]] %= MOD

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

Submission status: Accepted

Solution code:
# D - We Like AGC

from collections import defaultdict

MOD = 10**9+7
N = int(input())
charactors = ['A', 'G', 'C', 'T']

# dp[l][s] := 長さがlで、末尾3文字がsである文字列の個数
dp = [defaultdict(int) for _ in range(N+1)]

# 無関係の文字で初期化しておく
dp[0]['ZZZ'] = 1

# NGケース: AGC, ACG, GAC, A?GC, AG?C
def check(s, c):
    if c=='C':
        if s[1:]=='AG' or s[1:]=='GA' or \
            (s[0]=='A' and (s[1]=='G' or s[2]=='G')):
            return False
        else:
            return True
    elif c=='G':
        if s[1:]=='AC':
            return False
        else:
            return True
    else:
        return True

for i in range(N):
    for s in dp[i].keys():
        for c in charactors:
            # NGケースに該当しなければ、カウントする
            if check(s, c): 
                dp[i+1][s[1:]+c] += dp[i][s]
                dp[i+1][s[1:]+c] %= MOD

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
dp = np.zeros((N+1, 5, 5, 5), dtype = np.int64)
#dp[文字列の長さ][3文字前][2文字前][1文字前]
#0:dummy A:1, C:2, G:3, T:4
p = 10**9 + 7
dp[0, 0, 0, 0] = 1
for n in range(N):
  for i in range(5):#3文字前
    for j in range(5):
      for k in range(5):
        for l in range(1, 5):#今回追加する文字#0 : dummmyは初期条件の為なので回さない
          if j == 1 and k == 3 and l == 2:continue #AGC
          if j == 3 and k == 1 and l == 2:continue #GAC
          if j == 1 and k == 2 and l == 3:continue #ACG
          if i == 1 and k == 3 and l == 2:continue #A?GC
          if i == 1 and j == 3 and l == 2:continue #AG?C
          dp[n+1, j, k, l] += dp[n, i, j, k]
          dp[n+1, j, k, l] %= p
ans = 0
for i in range(1, 5):
  for j in range(1, 5):
    for k in range(1, 5):
      ans += dp[N, i, j, k]
      ans %=  p
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()

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 == 0 and j == 2 and k == 1 or \
                i == 0 and j == 1 and k == 2 or \
                i == 2 and j == 0 and k == 1:
                dp[3][i][j][k] = 0
            else:
                dp[3][i][j][k] = 1

for x 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 dp[x-1][i][j][k] == 0: continue
                    if j == 0 and k == 2 and l == 1 or \
                        j == 0 and k == 1 and l == 2 or \
                        j == 2 and k == 0 and l == 1: continue
                    if i == 0 and k == 2 and l == 1 or \
                        i == 0 and j == 2 and l == 1: continue
                    dp[x][j][k][l] = (dp[x][j][k][l] + dp[x-1][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)

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+=dfs(cur+1,last3[1:]+c)
            ret%=mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,'TTT'))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def like_agc3(www):
	lkagc=['AGC','ACG','GAC']
	return  not (www in lkagc)

def like_agc(www,w):
	if www[0]+www[2]+w =='AGC':
		return False
	if www[0]+www[1]+w == 'AGC':
		return False
	return like_agc3(www[1]+www[2]+w)
	

def main():
	ll=['AAA','AAC','AAG','AAT','ACA',       'ACC', 'ACG', 'ACT',"AGA", "AGC",     "AGG", "AGT", "ATA", "ATC" ,"ATG",     "ATT", "CAA", "CAC", "CAG", "CAT",     "CCA", "CCC", "CCG", "CCT", "CGA" , "CGC" ,"CGG" ,"CGT" ,"CTA" ,"CTC" , "CTG" ,"CTT" ,"GAA" ,"GAC" ,"GAG" , "GAT" ,"GCA" ,"GCC" ,"GCG" ,"GCT" , "GGA" ,"GGC" ,"GGG" ,"GGT" ,"GTA" , "GTC" ,"GTG" ,"GTT" ,"TAA" ,"TAC" , "TAG" ,"TAT" ,"TCA" ,"TCC" ,"TCG" , "TCT" ,"TGA" ,"TGC" ,"TGG" ,"TGT" , "TTA" ,"TTC" ,"TTG" ,"TTT"]
	dll={}
	for i,w in enumerate(ll):
		dll[w]=i
	
	n = int(input())
	#b , c = IN()
	#s = input()
	#cc=[1]*64
	#cc[6]=0#ACG
	#cc[9]=0#AGC
	#cc[18]=0#CAG
	cll='AGCT'
	cc = [1 if like_agc3(w) else 0 for w in ll]
	for i in range(4,n+1):
		#print(i)
		ncc=[0]*64
		for word in ll:
			for c in cll:
				if like_agc(word, c):
					next_word=word[1:]+c
					ncc[dll[next_word]]+=cc[dll[word]]
					ncc[dll[next_word]] %= mod
		cc=ncc
	ret = sum(cc) % mod
	print(ret)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import copy
def main():
    N = int(input())
    if N == 3:
        return 61
    mod = 10**9 + 7
    d = {'A':0, 'C':1, 'G':2, 'T':3}
    AGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    AGC[d['A']][d['G']][d['C']] = 0
    AGC[d['A']][d['C']][d['G']] = 0
    AGC[d['G']][d['A']][d['C']] = 0
    NAGC = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    for i in range(3, N):
        for i1 in range(4):
            for i2 in range(4):
                for i3 in range(4):
                    t = 0
                    if (i2 == d['G'] or i1 == d['G']) and i3 == d['C']:
                        for i4 in range(1, 4):
                            t += AGC[i4][i1][i2]
                    else:
                        for i4 in range(4):
                            t += AGC[i4][i1][i2]
                    if i1 == d['A'] and i2 == d['G'] and i3 == d['C']:
                        t = 0
                    if i1 == d['A'] and i2 == d['C'] and i3 == d['G']:
                        t = 0
                    if i1 == d['G'] and i2 == d['A'] and i3 == d['C']:
                        t = 0
                    t %= mod
                    NAGC[i1][i2][i3] = t
        AGC = copy.deepcopy(NAGC)
    return sum(sum(sum(j) for j in i) for i in AGC) % mod
print(main())

Submission status: Accepted

Solution code:
#ABC122-D We Like AGC
"""
条件を満たす文字列は、
xをACGTのいずれかとして
AGC
GAC
ACG
AxGC
AGxC
のいずれも文字列内に無い状態のことを言う。
上の条件から、末尾に文字を付け足そうとした時に、それに関与する文字列は
末尾3文字のみであり、それより前の状態は関係ない。
つまり、前3文字の結果を保存し続ければ3**4のdpテーブルを用いて求めることができる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n = int(readline())

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

#dp[i][j][k][l]:i文字目に3文字前がjで2文字前がkで1文字前がlである時のそこまでにあり得る通り数
#j,k,lにおいて、A,G,C,T=0,1,2,3と対応させる
dp = [[[[0]*4 for b in range(4)] for a in range(4)]for _ 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 == dic1["A"] and l == dic1["G"] and m == dic1["C"]: #AGC
                        continue
                    if k == dic1["G"] and l == dic1["A"] and m == dic1["C"]: #GAC
                        continue
                    if k == dic1["A"] and l == dic1["C"] and m == dic1["G"]: #ACG
                        continue
                    if j == dic1["A"] and l == dic1["G"] and m == dic1["C"]: #AxGC
                        continue
                    if j == dic1["A"] and k == dic1["G"] and m == dic1["C"]: #AGxC
                        continue
                    
                    dp[i+1][k][l][m] += dp[i][j][k][l] #次の状態に今を足す
                    dp[i+1][k][l][m] %= mod
                    


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

print(ans%mod)

Submission status: Accepted

Solution code:
# solution

data=int(input())
M=10**9+7

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
memo = [{} for _ in range(N+1)]

def ok(last4):
    if last4.find('AGC') != -1:
        return False
    for i in range(3):
        s = list(last4)
        s[i], s[i+1] = s[i+1], s[i]
        if ''.join(s).find('AGC') != -1:
            return False
    return True

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

answer = dfs(0, 'TTT')
print(answer % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()

def ok(last4):
    if last4.find('AGC') != -1:
        return False
    for i in range(3):
        s = list(last4)
        s[i], s[i+1] = s[i+1], s[i]
        if ''.join(s).find('AGC') != -1:
            return False
    return True

@lru_cache(None)
def dfs(i, last3):
    if i == N:
        return 1
    ret = 0
    for la in 'AGCT':
        if ok(last3+la):
            ret += dfs(i+1, last3[1:]+la)
    return ret % MOD

answer = dfs(0, 'TTT')
print(answer % MOD)

Submission status: Accepted

Solution code:
n=int(input())
dp=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n)]
mod=10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      if (i,j,k) in ((1,2,3),(1,3,2),(2,1,3)):
        continue
      dp[2][i][j][k]+=1
#t→0 a→1 g→2 c→3
for i in range(1,n):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        for m in range(4):
          if (k,l,m) in ((1,2,3),(2,1,3),(1,3,2)):
            continue
          if (j,l,m)==(1,2,3) or (j,k,m)==(1,2,3):
            continue
          dp[i][k][l][m]+=dp[i-1][j][k][l]
          dp[i][k][l][m]%=mod
ans=0
#print(dp)
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=dp[n-1][i][j][k]
      ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
dp=[[0]*4 for i in range(N)]
for i in range(4):
  dp[0][i]=1
  dp[1][i]=4
dic={'AG':1,'AC':1,'GA':1,'AGA':0,'AGG':0,'AGT':0,'AAG':0,'ATG':0,'AA':1,'AT':1}
def chk(i,j):
  global dp,dic
  if j==0:
    return 0
  elif j==1:
    return dic['AGG']+dic['AGT']+dic['ATG']+dic['AG']+dic['GA']
  elif j==2:
    return dic['AC']
  else:
    return 0
dp[2][0]=sum(dp[1])
dp[2][1]=sum(dp[1])-dp[0][0]-dp[0][2]
dp[2][2]=sum(dp[1])-dp[0][0]
dp[2][3]=sum(dp[1])
#dic['AGA']=dic['AG']
dic['AGG']=dic['AG']
dic['AGT']=dic['AG']
#dic['AAG']=dic['AA']
dic['ATG']=dic['AT']
dic['AG']=dp[1][0]
dic['AC']=dp[1][0]-dic['GA']
dic['GA']=dp[1][2]
dic['AT']=dp[1][0]
for i in range(3,N):
  _=sum(dp[i-1])
  for j in range(4):
    dp[i][j]=_-chk(i,j)
  dic['AGG']=dic['AG']
  dic['AGT']=dic['AG']
  dic['ATG']=dic['AT']
  dic['AG']=dp[i-1][0]
  dic['AC']=dp[i-1][0]-dic['GA']
  dic['GA']=dp[i-1][2]
  dic['AT']=dp[i-1][0]
print(sum(dp[-1])%MOD)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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

# q = deque([(0, "TTT")])
ans = 0
memo = [{} for i in range(N+1)]
def dfs(idx, last3):
    # idx, last3 = q.popleft()
    if last3 in memo[idx]:
        return memo[idx][last3]

    if idx == N:
        return 1
    ret = 0
    for c in "AGCT":
        if no_agc(last3 + c):
            last3_new = (last3 + c)[1:]
            idx_new = idx + 1
            ret = (ret + dfs(idx_new, last3_new)) % mod
    memo[idx][last3] = ret

    return ret
print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
n=int(input())
d={}
drev={}
a=["A","C","G","T"]
judge=["AGC","ACG","GAC"]
ans=[[1 for i in range(61)]]+[[0 for i in range(61)] for j in range(n-3)]
cnt=0
mod=10**9+7
for i in range(4):
    for j in range(4):
        for k in range(4):
            s=a[i]+a[j]+a[k]
            if s == "AGC" or s =="ACG" or s == "GAC":continue
            d[s]=cnt
            drev[cnt]=s
            cnt+=1
for i in range(1,n-2):
    for j in range(61):
        for k in range(4):
            h=drev[j]+a[k]
            if h[1:] in judge or h[0]+h[2:]=="AGC" or h[:2]+h[3]=="AGC":continue
            ans[i][d[h[1:]]]+=ans[i-1][j]
            ans[i][d[h[1:]]]%=mod
print(sum(ans[-1])%mod)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

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

ans = 0
memo = [{} for i in range(N+1)]
def dfs(idx, last3):
    if last3 in memo[idx]:
        return memo[idx][last3]
    if idx == N:
        return 1
    ret = 0
    for c in "AGCT":
        if no_agc(last3 + c):
            ret = (ret + dfs(idx + 1, (last3 + c)[1:])) % mod
    memo[idx][last3] = ret
    # print(memo[idx], last3)

    return ret

print(dfs(0, "TTT"))

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+2)]
banc = [(i,0,2) for i in range(4)] + [(0,2,i) for i in range(4)] + [(i,2,0) for i in range(4)] + [(0,i,2) for i in range(4)]
bang = [(i,0,1) for i in range(4)]
if N == 3:
    print(61)

else:

    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in ((0,2,1),(0,1,2),(2,0,1)):
                    continue
                dp[3][i][j][k] += 1
    
    for n in range(4,N+2):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        if (i,j,k) in ((0,2,1),(0,1,2),(2,0,1)):
                            continue
                        if (l,i,j) in ((0,2,1),(0,1,2),(2,0,1)):
                            continue
                        if (l,i,j) in banc:
                            if k==1:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= mod
                        elif (l,i,j) in bang:
                            if k==2:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= mod
                        else:
                            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[N][i][j][k]
                ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())

mod = 10**9+7
# dp[i][a][b][c] : 左からi番目まで文字を決めたときの右端から3文字をc,b,aとしたときの場合の数
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
# a,b,cについて : 0 -> "T", 1 -> "A", 2 -> "G", 3 -> "C"
# 初期値はTTTが左にあると考えても影響はない
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):
                    # AG*C or A*CG
                    if (a==1 and b==2 and d==3) or (a==1 and c==2 and d==3):
                        continue
                    # *AGC
                    if (b==1 and c==2 and d==3):
                        continue
                    # *GAC or *ACG
                    if (b==2 and c==1 and d==3) or (b==1 and c==3 and d==2):
                        continue
                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d] %= mod

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:
def main():
    n=int(input())
    MOD=10**9+7
    memo = [{} for i in range(n+1)]

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce

MOD = 1000000000 + 7
LETTERS = ["A", "C", "G", "T"]
PROHIBIT = ["AGC", "ACG", "GAC", "AGGC", "AGTC", "ATGC"]

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

    table = {}

    for first in LETTERS:
        for second in LETTERS:
            for third in LETTERS:
                codon = first+second+third
                if not codon in PROHIBIT:
                    table[codon] = [1]

    for i in range(n-3):
        for codon in table.keys():
            table[codon].append(0)

        for codon in table.keys():
            for append in LETTERS:
                three_letters = codon[1:] + append
                four_letters = codon + append

                if (not four_letters in PROHIBIT) and (not three_letters in PROHIBIT):
                    table[three_letters][i+1] = (table[three_letters][i+1] + table[codon][i]) % MOD

    print(reduce(lambda acc, x: (acc + x[-1]) % MOD, table.values(), 0))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 直前数文字しか影響しないと思えばDPと見当つく
MOD = 10**9 + 7
N = int(input())
dp = [[[[0]*5 for i in range(5)] for i in range(5)] for i in range(N+1)]

dp[0][0][0][0] = 1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if j == 1 and k == 2 and l == 3: continue  # AGC
                    if j == 2 and k == 1 and l == 3: continue  # GAC
                    if j == 1 and k == 3 and l == 2: continue  # ACG
                    if i == 1 and k == 2 and l == 3: continue  # A?GC
                    if i == 1 and j == 2 and l == 3: continue  # AG?C
                    dp[n+1][j][k][l] += dp[n][i][j][k]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())

from functools import lru_cache
@lru_cache(None)
def dfs(v=0, parent=-1):# どこからきたかの情報を入れとく

    if v == n:
        return 1

    if parent[-3] == 'A' and parent[-1] == 'G':
        return sum([dfs(v+1, parent[-2:]+'A'), dfs(v+1, parent[-2:]+'G'), dfs(v+1,parent[-2:]+'T')])%p
    elif parent[-3:-1] == 'AG':
        return sum([dfs(v+1,parent[-2:]+'A'), dfs(v+1,parent[-2:]+'G'), dfs(v+1,parent[-2:]+'T')])%p
    elif parent[-2:] == 'AC':
        return sum([dfs(v+1,'ACA'), dfs(v+1,'ACC'), dfs(v+1,'ACT')])%p
    elif parent[-2:] == 'GA':
        return sum([dfs(v+1,'GAG'), dfs(v+1,'GAA'), dfs(v+1,'GAT')])%p
    elif parent[-2:] == 'AG':
        return sum([dfs(v+1,'AGA'), dfs(v+1,'AGG'), dfs(v+1,'AGT')])%p
    else:
        return sum([dfs(v+1, parent[-2:]+'A')%p, dfs(v+1,parent[-2:]+'G')%p, dfs(v+1,parent[-2:]+'C')%p, dfs(v+1,parent[-2:]+'T')%p])%p


ans = 0

agc = 'AGCT'

for i in range(4):
    for j in range(4):
        word = 'T' +agc[i] + agc[j]
        ans += dfs(2,word)%p

print(ans%p)

Submission status: Accepted

Solution code:
#conding utf-8
N=int(input())
MOD=10**9+7
dp =[[[[0 for i in range(4)] for i in range(4)] for i in range(4)]for i in range(N+1)]
dp[0][0][0][0]=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 k==1 and l==2 and m==3:
            continue
          if k==2 and l==1 and m==3:
            continue
          if k==1 and l==3 and m==2:
            continue
          if j==1 and l==2 and m==3:
            continue
          if j==1 and k==2 and m==3:
            continue
          dp[i][k][l][m] += dp[i-1][j][k][l]
          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)