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


def check(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        l = list(last4)
        l[i],l[i+1] = l[i+1], l[i]
        if "AGC" in "".join(l):
            return False
    return True

memo = [{} for i in range(n)]
# 再帰
def dfs(depth=0, last3="TTT"):
    if depth == n:
        # 遷移できる前提だから↓は必ず1になるはず
        #return int(last3 in ["AGC", "ACG", "GAC"])
        return 1
    if last3 in memo[depth]:
        return memo[depth][last3]

    res = 0
    for c in "ACGT":
        if check(last3+c):
            res += dfs(depth+1, last3[1:]+c)
            res %= mod
    memo[depth][last3] = res
    return res

print(dfs())

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
if n < 3:
    print(4**n)
    exit()

ind = 0
d = {}
# A:0, G:1, C:2, T:3とする
from itertools import product
for i, j, k in product(range(4), repeat=3):
    if any(a==0 and b==1 and c==2 for a,b,c in [[i,j,k], [j,i,k], [i,k,j]]):
        continue
    d[(i,j,k)] = ind
    d[ind] = (i,j,k)
    ind += 1

# 使える文字列→使える文字列への写像
edge = [[] for i in range(ind)]
for i, j, k in product(range(4), repeat=3):
    if any((a,b,c)==(0,1,2) for a,b,c in [(i,j,k), (j,i,k), (i,k,j)]):
        continue
    for l in range(4):
        if (j,k,l) in d and (i,k,l) != (0,1,2) and (i,j,l) != (0,1,2):
            edge[d[i,j,k]].append(d[j,k,l])

dp = [1]*ind
for i in range(n-3):
    dp_next = [0]*ind
    for from_ in range(ind):
        for to in edge[from_]:
            dp_next[to] += dp[from_]
            dp_next[to] %= mod
    dp = dp_next
print(sum(dp)%mod)

Submission status: Accepted

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

def check(string):
    if re.match(".*(AGC|GAC|ACG|A.?GC|AG.?C).*", string):
        return False
    return True


def dfs(string="", depth=0): # return ok count
    if depth == n:
        return 1

    if string in memo[depth]:
        return memo[depth][string]

    cnt = 0
    for i in "AGCT":
        next_string = string + i
        if check(next_string):
            cnt += dfs(string[-3:] + i, depth + 1)
            cnt %= MOD
    memo[depth][string] = cnt
    return cnt

print(dfs())

Submission status: Accepted

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

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


# 前3つのアルファベットをもとに、OKなアルファベットを生成する
def genLegalChars(last3):

    if len(last3) != 3:
        print('Error! variable "last3" is not a string of length 3. None is returned in this function.')
        return None

    if last3[1:] == 'AG':
        return ['A','T','G']
    elif last3[1:] == 'GA':
        return ['A','T','G']
    elif last3[1:] == 'AC':
        return ['A','T','C']
    elif last3[0] == 'A' and last3[2] =='G':
        return ['A','G','T']
    elif last3[0:2] == 'AG':
        return ['A','G','T']
    else:
        return ['A','T','G','C']


def DFS(length, last3):

    # その長さで、その直前3つの場合の、そのノードの値が分かっている場合はそれを返す
    if last3 in memo[length]:
        return memo[length][last3]

    # 末端の（長さが既に求められている長さに等しい）場合は1を返す
    if length == N:
        return 1

    curNodeVal = 0
    # 次のノードに来ても良いアルファベットを列挙する
    # それぞれのアルファベットからノードを分岐させ、再帰呼び出し
    for char in genLegalChars(last3):
        curNodeVal = (curNodeVal + DFS(length+1, last3[1:]+char)) % MOD

    # メモ化してからreturnする
    memo[length][last3] = curNodeVal

    return curNodeVal

print(DFS(0,'TTT'))

Submission status: Accepted

Solution code:
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
    res =0
    for c in "ACGT":
        if ok(last3+c):
            res += dfs(cur+1,last3[1:]+c)
            res = res%mod
    memo[cur][last3]=res
    return res
mod = 10**9+7
N = int(input())
memo=[{} for _ in range(N+1)]

print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
# D - We Like AGC
# https://atcoder.jp/contests/abc122/tasks/abc122_d

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

MODULO = 10**9 + 7

def legal(prev4):
    for i in range(len(prev4)):
        check = list(prev4)
        if i >= 1:
            check[i], check[i-1] = check[i-1], check[i]
        if ''.join(check).count('AGC') >= 1:
            return False
    return True

def dfs(cur, prev3):

    if prev3 in memo[cur]:
        return memo[cur][prev3]
    if cur == N:
        return 1

    cnt = 0
    for c in 'ACGT':
        prev4 = prev3 + c
        if legal(prev4):
            cnt = (cnt + dfs(cur + 1, prev4[1:])) % MODULO

    memo[cur][prev3] = cnt
    return cnt

print '{}'.format(dfs(0, '___'))

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
ch = ["A", "C", "G", "T"]
dic = {}
for i in range(4):
    for j in range(4):
        for k in range(4):
            dic[ch[i]+ch[j]+ch[k]] = 1
dic["AGC"] = 0
dic["GAC"] = 0
dic["ACG"] = 0

err = ["AGAC", "AGCC", "AGGC", "AGTC", "AAGC", "ACGC", "AGGC", "ATGC", ]

l = [dic]
for i in range(n-3):
    _dic = defaultdict(lambda: 0)
    for k, v in l[i].items():
        for j in range(4):
            s = k+ch[j]
            if s not in err:
                _dic[k[1:]+ch[j]] = (_dic[k[1:]+ch[j]]+v)%(10**9+7)
    _dic["AGC"] = 0
    _dic["GAC"] = 0
    _dic["ACG"] = 0
    l.append(_dic)

ans = 0
for v in l[n-3].values():
    ans = (ans+v)%(10**9+7)

print(ans)

Submission status: Accepted

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


def ng(a: int, b: int, c: int):
    return (a == 1 and b == 2 and c == 3)


# 初期状態の直近3文字は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):
                    # 3文字パターン
                    if (ng(b, c, d) or ng(c, b, d) or ng(b, d, c)):
                        continue
                    # 4文字パターン
                    if ng(a, c, d) or ng(a, b, d):
                        continue
                    # NGパターンがなければ遷移先に足す
                    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[N][a][b][c] % mod


print(ans % mod)

Submission status: Accepted

Solution code:
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

Submission status: Accepted

Solution code:
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]

ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]

i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())

ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]

# NG: 021, 201, 012, 0x21, 02x1
def check(c0, c1, c2, c3):
    if c0 == 1 and c1 == 2 and c2 == 0:
        return False
    if c0 == 1 and c1 == 0 and c2 == 2:
        return False
    if c0 == 2 and c1 == 1 and c2 == 0:
        return False
    if c0 == 1 and c1 == 2 and c3 == 0:
        return False
    if c0 == 1 and c2 == 2 and c3 == 0:
        return False
    return True

def main(N):
    mod = int(1e+9) + 7
    
    dp1 = [0 for _ in range(4)]
    for c0 in range(4):
        if check(c0, -1, -1, -1) == False:
            continue
        dp1[c0] = 1
    if N == 1:
        ans = 0
        for c1 in range(4):
            ans += dp1[c1]
            ans %= mod
        print(ans)
        return
    
    dp2 = [[0 for _ in range(4)] for _ in range(4)]
    for c1 in range(4):
        for c0 in range(4):
            if check(c0, c1, -1, -1) == False:
                continue
            dp2[c0][c1] += dp1[c1]
            dp2[c0][c1] %= mod
    if N == 2:
        ans = 0
        for c1 in range(4):
            for c2 in range(4):
                ans += dp2[c1][c2]
                ans %= mod
        print(ans)
        return
    
    dp3 = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
    for c1 in range(4):
        for c2 in range(4):
            for c0 in range(4):
                if check(c0, c1, c2, -1) == False:
                    continue
                dp3[c0][c1][c2] += dp2[c1][c2]
                dp3[c0][c1][c2] %= mod
    if N == 3:
        ans = 0
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    ans += dp3[c1][c2][c3]
                    ans %= mod
        print(ans)
        return
    
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                dp[3][c1][c2][c3] = dp3[c1][c2][c3]
    
    for l in range(3, N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    for c0 in range(4):
                        if check(c0, c1, c2, c3) == False:
                            continue
                        dp[l+1][c0][c1][c2] += dp[l][c1][c2][c3]
                        dp[l+1][c0][c1][c2] %= mod
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= mod
    print(ans)

main(i2n())

Submission status: Accepted

Solution code:
import itertools
N = int(input())
AGCs = [
    'AGC',
    'GAC',
    'ACG',
    'AGAC',
    'AGGC',
    'AGTC',
    'ACGC',
    'ATGC',
]
seq = ["A", "G", "C", "T"]
from collections import Counter
memo = Counter()

count = 0
new_S = []
def memo_saiki(n, start_memo):
    if n==1:
        print(4)
        exit()
    if n==2:
        print(16)
        exit()
    memo = start_memo
    new_memo = Counter()
    for _ in range(n-3):
        for k, v in memo.items():
            for char in 'AGCT':
                target = k+char
                if any([agc in target for agc in AGCs]):
                    continue
                new_memo.update({target[-3:]: v})
        memo = new_memo
        new_memo = Counter()
    print(sum([v for v in memo.values()]) % (10**9 + 7))

def saiki(n=6):
    S = ['']
    new_S = []
    memo = {}
    for _ in range(n):
        for i, s in enumerate(S):
            for c in 'AGCT':
                memo[s[-3:]] = 1
                hoge = s[-3:] + c
                if any([agc in hoge for agc in AGCs]):
                    continue
                new_S.append(hoge)
        S = new_S
        new_S = []
    #S = new_S.copy()
    return S
memo_saiki(n=N, start_memo = Counter(saiki(3)))

Submission status: Accepted

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

for i in range(4, n+1):
	for j in range(4):
		for k in range(4):
			for l in range(4):
				dp[i][j][k][l] = 0
				for h in range(4):
					if l == C:
						if h == A and k == G:
							continue
						if h == A and j == G:
							continue
					dp[i][j][k][l] += dp[i-1][h][j][k]

				dp[i][j][k][l] %= MOD

	dp[i][A][G][C] = 0
	dp[i][A][C][G] = 0
	dp[i][G][A][C] = 0

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
acg
gac
axgc
agxc
"""

n = int(input())
MOD = 10**9 + 7
dpa = [0, 0, 1]
dpc = [0, 0, 1]
dpg = [0, 0, 1]
dpt = [0, 0, 1]

for i in range(2, n+2):
    dpa.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    dpc.append(dpa[i]-dpg[i-1] + dpc[i] + dpg[i]-dpa[i-1]-2*dpa[i-2] + dpt[i]-dpa[i-2])
    dpg.append(dpa[i] + dpc[i]-dpa[i-1]+dpg[i-2] + dpg[i] + dpt[i])
    dpt.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    
print((dpa[n+1]+dpg[n+1]+dpc[n+1]+dpt[n+1]) % MOD)

Submission status: Accepted

Solution code:
N , MOD = int(input()), int(1e9+7)

all_suffix = []
base = ['A', 'C', 'G', 'T']

for char1 in base:
    for char2 in base:
        for char3 in base:
            all_suffix.append(char1+char2+char3)

len_all_suffix = len(all_suffix)

def judge(last4):
    for i in range(4):
        tmp = list(last4)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]
        if ''.join(tmp).find('AGC') >= 0:
            return False
    return True

dp = [[0 for i in range(len_all_suffix)] for i in range(N-2)]

for i in range(len_all_suffix):
    if all_suffix[i]!='AGC' and all_suffix[i]!='GAC' and all_suffix[i]!='ACG':
        dp[0][all_suffix.index(all_suffix[i])] += 1

for i in range(1, N-2):
    for j in range(len_all_suffix):
        for char in base:
            if judge(all_suffix[j]+char):
                k = all_suffix.index(all_suffix[j][1:]+char)
                dp[i][k] += dp[i-1][j] % MOD

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

Submission status: Accepted

Solution code:
N = int(input())

MOD = int(1e9+7)

tokens = ['A','C','G','T']

suffixes = []
for suffix_1 in tokens:
    for suffix_2 in tokens:
        for suffix_3 in tokens:
            suffixes.append(suffix_1+suffix_2+suffix_3)

dp = [[0 for _ in suffixes] for _ in range(N+1)]

reverse_index = {}
for i,s in enumerate(suffixes):
    reverse_index[s] = i

def pprint(dp):
    N = len(dp)
    M = len(dp[0])

    for i in dp:
        st = ""
        for j in i:
            st += str(j)
            st += " "
        print(st)

for i,s in enumerate(suffixes):
    if not s in ['AGC', 'ACG', 'GAC']:
        dp[3][i]  = 1

valid_str_4 = set()

def swap(s, i ,j):
    s_new = list(s)
    s_new[i], s_new[j] = s[j], s[i]
    return ''.join(s_new)

def valid(str4):
    if 'AGC' in str4:
        return False
    for i in range(3):
        s_new = swap(str4, i, i+1)
        if 'AGC' in s_new:
            return False
    return True

for s in suffixes:
    for c in tokens:
        ss = s+c
        if valid(ss):
            valid_str_4.add(ss)

for n in range(4, N+1):
    for s in suffixes:
        for c in tokens:
            ss = s+c
            if ss in valid_str_4:
                dp[n][reverse_index[ss[1:]]] += dp[n-1][reverse_index[s]]

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

Submission status: Accepted

Solution code:
#4
N=int(input())
memo = [{} for i in range(N)]

def check(last3,way,add,num):
    if num == 1:
        memo[num][last3+add] = way
    if num == 2:
        new_last3 = last3[-2:]+add
        if (new_last3!="AGC")&(new_last3!="GAC")&(new_last3!="ACG"):
            if new_last3 in memo[num]:
                memo[num][new_last3]+=way
            else:
                memo[num][new_last3]=way
    if num > 2:
        new_last3 = last3[-2:]+add
        new_last4 = last3[-3:]+add
        if (new_last3!="AGC")&(new_last3!="GAC")&(new_last3!="ACG"):
            if (new_last4!="AGAC")&(new_last4!="AGGC")&(new_last4!="AGTC")&(new_last4!="ATGC"):     
                if new_last3 in memo[num]:
                    memo[num][new_last3]+=way
                else:
                    memo[num][new_last3]=way

for c in "ATGC":
    memo[0][c] = 1

for i in range(1,N):
    for cj in memo[i-1]:
        last3 = cj
        way = memo[i-1][cj]
        for new_c in "ATCG":
            check(last3,way,new_c,i)
su = 0
for i in memo[N-1]:
    su += memo[N-1][i]
print(su%(10**9+7))

Submission status: Accepted

Solution code:
from collections import Counter
mod = 10**9+7
def check(s):
    ban = ["AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC"]
    for b in ban:
        if b in s:
            return False
    return True

n = int(input())
dp = [Counter() for i in range(n+1)]
dp[0]["RAN"] = 1

for i in range(n):
    for key, value in dp[i].items():
        for c in "ACTG":
            if check(key+c):
                dp[i+1][key[1:]+c]+=value % mod

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

Submission status: Accepted

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]


n = readInt()
M = 10 ** 9 + 7


dp = np.zeros((n + 1, 256), dtype=np.uint32)
dp[0, 255] = 1


for i in range(n):
    for j4 in [0, 64, 128, 192]:
        for j3 in [0, 16, 32, 48]:
            j43 = j4 + j3
            for j2 in [0, 4, 8, 12]:
                j432 = j43 + j2
                for j1 in range(4):
                    j = j432 + j1
                    l321 = 4 * (j3 + j2 + j1)
                    for l0 in range(4):
                        if (6 == (j3 + 4 * j1 + l0)) or (6 == (j3 + j2 + l0)) or (6 == (4 * j2 + 4 * j1 + l0)) or (6 == (16 * j1 + j2 + l0)) or (6 == (4 * j2 + 4 * l0 + j1)):
                            continue
                        l = l321  + l0
                        dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % M

ret = 0
for v in dp[-1]:
    ret = (ret + v) % M
print(ret)

Submission status: Accepted

Solution code:
from collections import Counter

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

dp = [Counter() for i in range(N+1)]
dp[0]["TTT"] = 1


def ok(last4):
    bad = ["AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC"]
    for b in bad:
        if b in last4:
            return False
    return True

for i in range(N):
    for key, value in dp[i].items():
        for c in "AGCT":
            if ok(key+c):
                dp[i+1][key[1:]+c] += value % MOD

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

Submission status: Accepted

Solution code:
# ラスト三文字を状態として保持してDPする
n = int(input())

# dp[len][i][j][k] := 長さ len 文字で, 末尾が i, 末尾-1 が j,
#                   末尾-2 が k, となる文字列の総数
dp = [[[[0]*4 for k in range(4)] for j in range(4)] for i in range(n+1)]

# 長さ 0 の文字列は 1通りしかない!
dp[0][3][3][3] = 1
mod = 1000000007

# 文字列の長さ 
for lens in range(n):
    # 最後から1文字目の文字
    for c1 in range(4):
        # 最後から2文字目の文字
        for c2 in range(4):
            # 最後から3文字目の文字
            for c3 in range(4):
                # 条件に当てはまるものがない場合は continue
                if dp[lens][c1][c2][c3] == 0:
                    continue
                # 新しく追加する文字
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue

                    # だめな条件を抜けたら, a を足した文字列を作れる.
                    dp[lens+1][a][c1][c2] += dp[lens][c1][c2][c3]
                    dp[lens+1][a][c1][c2] %= mod
 
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[n][c1][c2][c3]
            ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
mod = 1000000007
data = dict([(i+j+k, 1) for i in 'ACGT' for j in 'AGCT' for k in 'ACGT'])
data['AGC'] = 0
data['ACG'] = 0
data['GAC'] = 0
 
def check(text):
    if 'AGC' in text:
        return False
    if 'AGC' in text[1] + text[0] + text[2] + text[3]:
        return False
    if 'AGC' in text[0] + text[2] + text[1] + text[3]:
        return False
    if 'AGC' in text[0] + text[1] + text[3] + text[2]:
        return False
    else:
        return True

for x in range(0,N-3):
    new_data = dict([(i+j+k, 0) for i in 'ACGT' for j in 'AGCT' for k in 'ACGT'])
    for y in data.keys():
        for z in 'ACGT':
            if check(y+z):
                new_data[y[1:]+z] += data[y]%mod
    data = new_data.copy()

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
memo = {}

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

def dfs(d, last3):
    if d < 0:
        return 1
    if not (d, last3) in memo:
        res = 0
        for c in "ACGT":
            last4 = last3 + c
            if ok(last4):
                res = (res + dfs(d-1, last4[-3:])) % MOD
        memo[d, last3] = res
    return memo[d, last3]

def solve(n):
    return dfs(n-1, "###")

n = int(input())
print(solve(n))

Submission status: Accepted

Solution code:
MOD = 10**9+7

N = int(input())

countA = 4
countG = 4
countAG = 1
countGA = 1
countAC = 1
countAGX = 0
countAXG = 0
countAT = 1
ans = 16
nextnums = [0 for _ in range(7)]
for i in range(N-2):
    nextans = ans*4 - countAG - countGA - countAC - countAXG - countAGX
    nextA = ans
    nextG = ans - countAC
    nextAG = countA
    nextGA = countG
    nextAC = countA - countGA
    nextAGX = 2 * countAG
    nextAXG = countAT
    nextAT = countA

    ans = nextans % MOD
    countA = nextA % MOD
    countAC = nextAC % MOD
    countAG = nextAG % MOD
    countAGX = nextAGX % MOD
    countAT = nextAT % MOD
    countAXG = nextAXG % MOD
    countG = nextG % MOD
    countGA = nextGA % MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
data = dict([(i+j+k, 1) for i in "ACGT" for j in "ACGT" for k in "ACGT"])
data["AGC"] = 0
data["ACG"] = 0
data["GAC"] = 0

def check(text):
    one = text[0]
    two = text[1]
    three = text[2]
    four = text[3]
    if "AGC" in text:
        return False
    if "AGC" in two + one + three + four:
        return False
    if "AGC" in one + three + two + four:
        return False
    if "AGC" in one + two + four + three:
        return False
    return True


for i in range(N-3):
    new_data = dict([(i+j+k, 0) for i in "ACGT" for j in "ACGT" for k in "ACGT"])
    for s in data.keys():
        for c in "ACGT":
            if(not check(s+c)):
                continue
            new_data[s[1:]+c] += data[s]%mod
    data = new_data.copy()
print(sum(data.values())%mod)

Submission status: Accepted

Solution code:
n = int(input())

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

dp[0][3][3][3] = 1
mod = 1000000007

for lens in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                #print(lens,c1,c2,c3,dp[lens][c1][c2][c3])
                if dp[lens][c1][c2][c3] == 0:
                    continue
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[lens+1][a][c1][c2] += dp[lens][c1][c2][c3]
                    dp[lens+1][a][c1][c2] %= mod

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

print(ans)

Submission status: Accepted

Solution code:
import itertools, math

N = int(input())

ACGTList = ["A", "G", "C", "T"]
AGCList = ["ATGC", "AGTC", "AGGC"]
for ACGT in ACGTList:
    for AGC in ["AGC", "ACG", "GAC"]:
        AGCList.append(ACGT + AGC)
        AGCList.append(AGC + ACGT)

patternObj = itertools.product(ACGTList, repeat=3)
patternDict = {}
for i, pattern in enumerate(patternObj):
    strPattern = "".join(pattern)
    patternDict[strPattern] = 0 if strPattern in ["AGC", "ACG", "GAC"] else 1

for i in range(N - 3):
    nextPatternDict = dict.fromkeys(patternDict, 0)
    for pattern in patternDict:
        for ACGT in ACGTList:
            newPattern = pattern + ACGT
            if newPattern in AGCList:
                continue
            nextPatternDict[newPattern[1:]] += patternDict[newPattern[:3]]
    patternDict = nextPatternDict.copy()

ans = 0
devide = int(math.pow(10, 9)) + 7
for pattern in patternDict:
    ans += patternDict[pattern]
    ans %= devide

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [[[[0 for i in range(0, 4)] for j in range(0, 4)] for k in range(0, 4)] for l in range(0, 101)]

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

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

Submission status: Accepted

Solution code:
import itertools

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

ng_patterns3 = ['AGC', 'ACG', 'GAC']
ng_patterns4 = ['AAGC', 'AACG', 'ATGC', 'AGAC', 'AGTC', 'AGGC', 'AGCA', 'AGCT', 'AGCG', 'AGCC', 'ACGA', 'ACGT', 'ACGG',
                'ACGC', 'TAGC', 'TACG', 'TGAC', 'GAGC', 'GACA', 'GACT', 'GACG', 'GACC', 'GGAC', 'CAGC', 'CACG', 'CGAC']


# 最後の3文字が決まれば次の文字の数も決まるので、
# 最後の3文字をキーに文字列の数をカウントする
def main():
    # 初期化
    counts = {}
    for li in itertools.product('ATGC', repeat=3):
        s = ''.join(li)
        if s not in ng_patterns3:
            counts[s] = 1

    # 1文字ずつ増やす
    for _ in range(3, n):
        new_counts = {s: 0 for s in counts.keys()}
        for s3, count in counts.items():
            for c in 'ATGC':
                s4 = s3 + c
                if s4 not in ng_patterns4:
                    new_counts[s4[-3:]] += count % MOD
        counts = new_counts

    print(sum([c for c in counts.values()]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9+7
n = int(input())

basis = ['A', 'C', 'G', 'T']
cands = {}
for i in basis:
    for j in basis:
        for k in basis:
            ijk = i+j+k
            if ijk in ['AGC', 'GAC', 'ACG']:
                cands[ijk] = 0
            else:
                cands[ijk] = 1
for i in range(3, n):
    cands_tmp = {ijk:0 for ijk in cands.keys()}
    for k, v in cands.items():
        for l in basis:
            k_new = k+l
            if k_new[1:] in ['AGC', 'GAC', 'ACG']:
                pass
            elif k_new[0] == 'A' and 'G' in k_new[1:3] and k_new[3] == 'C':
                pass
            else:
               cands_tmp[k_new[1:]] += v
               cands_tmp[k_new[1:]] %= MOD
    cands = cands_tmp
    
print(sum(cands.values())%MOD)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())

dp = np.zeros((N+1,4,4,4),dtype="int")

dp[0,3,3,3] = 1
mod = 10**9+7


for l in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[l,c3,c2,c1] == 0:
                    continue
                for c0 in range(4):
                    if c0 == 1 and c1 == 2 and c2 == 0:
                        continue
                    if c0 == 2 and c1 == 1 and c2 == 0:
                        continue
                    if c0 == 2 and c1 == 0 and c2 == 1:
                        continue
                    if c0 == 2 and c1 == 1 and c3 == 0:
                        continue
                    if c0 == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l+1,c2,c1,c0] += dp[l,c3,c2,c1]
                    dp[l + 1, c2, c1, c0] %= mod
                    
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[N,c3,c2,c1]
            ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())

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

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
import re
import itertools
chars = ["A","G","T","C"]
avoid = ["AGC","GAC","ACG",]
avoid_pattern = r"(.AGC|AGC.|.GAC|GAC.|.ACG|ACG.|A.GC|AG.C)"
MOD = (10**9) + 7
states = [ "".join([c1,c2,c3]) for  c1,c2,c3 in itertools.product(chars,chars,chars)]
states = [state for state in states if state not in avoid ]
def forward(states_num):
    update = dict([ (state,0) for state in  states_num.keys()])
    for current_state,current_num in states_num.items():
        for char in chars:
            if re.search(avoid_pattern,current_state + char) :
                pass
            else:
                new_state = current_state[1:]+char
                update[new_state] += current_num %MOD
    return update

def get_number(N):
    if N ==1 :
        return 4
    elif N ==2:
        return 16
    else:
        states_num = dict([ (state, 1)for state in states])
        for i in range(N-3):
            states_num = forward(states_num)
        return sum([  v for k,v in states_num.items()])%MOD

N = int(input())
#strings = ["".join(_) for _ in itertools.product(*([chars]*N)) ]
#strings = [string for string in strings if not re.search(avoid_pattern,string)]
#print(len(strings))
print(get_number(N))

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
a=[{} for i in range(n+1)]
def C(last4):
    if last4[:3]=='AGC' or last4[1:]=='AGC':
        return False
    for i in range(3):
        tmp=list(last4)
        tmp[i], tmp[i+1]=tmp[i+1], tmp[i]
        if ''.join(tmp).count('AGC')>0:
            return False
    return True
a[0]['TTT']=1
for i in range(1, n+1):
    for k, v in a[i-1].items():
        for c in 'ACGT':
            if C(k+c):
                if k[1:]+c in a[i]:
                    a[i][k[1:]+c]+=v
                else:
                    a[i][k[1:]+c]=v
print(sum(a[n].values())%mod)