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())
memo = [dict() for i in range(n + 1)]


def ok(last4):
    for i in range(4):
        t = list(last4)

        if i >= 1:
            t[i - 1], t[i] = t[i], t[i - 1]

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

    return True


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


print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    div = pow(10, 9) + 7
    # AGC, A#GC, AG#C, GAC, ACG
    # #AG (-> C not allowed) done
    # A#G (-> C not allowed)
    # AG# (-> C not allowed) done
    # #GA (-> C not allowed) done
    # #AC (-> G not allowed)
    three = [""]
    for _ in range(3):
        temp = []
        for s in three:
            for c in "ACGT":
                temp.append(s + c)
        three = temp
    d = dict()
    for s in three:
        if s not in ["AGC", "GAC", "ACG"]:
            d[s] = 1
    for _ in range(3, N):
        temp = dict()
        for s in d:
            NotAllowed = forbidden(s)
            for c in "ACGT":
                if c not in NotAllowed:
                    temp[s[1:]+c] = temp.get(s[1:]+c, 0) + d[s]
        d = temp
    ans = 0
    for s in d:
        ans += d[s] % div
    return ans % div

def forbidden(s):
    if s[1:] == "AG" or s[1:]=="GA" or s[:2] == "AG" or (s[0]== "A" and s[2]== "G"):
        return ["C"]
    if s[1:] == "AC":
        return ["G"]
    else:
        return []


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

Submission status: Accepted

Solution code:
import copy

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


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
ans = check("TTT", 0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
law = 10 ** 9 + 7

dp = {'TTT': 1}
def check(s):
    if 'AGC' in s or 'GAC' in s or 'ACG' in s:
        return False
    if s[0] + s[2:] == 'AGC':
        return False
    if s[:2] + s[3] == 'AGC':
        return False
    return True
for _ in range(n):
    # print(dp)
    new = {}
    for i, c in dp.items():
        for add in 'ACGT':
            s = i + add
            if check(s):
                s = s[1:]
                if s not in new:
                    new[s] = c % law
                else:
                    new[s] += c
                    new[s] %= law
    dp = new
print(sum(dp.values()) % law)

Submission status: Accepted

Solution code:
N = int(input())
MOD = int(1e9+7)
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
# T = 0 A = 1 G = 2 C = 3
dp[0][0][0][0] = 1
for n in range(N):
    for i in range(4):
        for j in range(4):
            if dp[n][i][j] == 0:
                continue
            for k in range(4):
                for a in range(4):
                    if j == 1 and i == 2 and a == 3: # AGC
                        continue
                    if j == 2 and i == 1 and a == 3: # GAC
                        continue
                    if j == 1 and i == 3 and a == 2: # ACG
                        continue
                    if k == 1 and i == 2 and a == 3: # A*GC
                        continue
                    if k == 1 and j == 2 and a == 3: # AG*C
                        continue
                    dp[n+1][a][i][j] += dp[n][i][j][k]
                    dp[n + 1][a][i][j] %= MOD
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,x = [int(i) for i in readline().split()]
n = int(input())
MOD = 10**9+7

dp = [[[0]*4 for j in range(4)] for i in range(4)]
dp[3][3][3] = 1
for _ in range(n):
    ndp = [[[0]*4 for j in range(4)] for i in range(4)]

    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if j == 0 and k == 1 and l == 2: continue
                    if i == 0 and k == 1 and l == 2: continue
                    if j == 1 and k == 0 and l == 2: continue
                    if j == 0 and k == 2 and l == 1: continue
                    if i == 0 and j == 1 and l == 2: continue
                    ndp[j][k][l] += dp[i][j][k]
                    ndp[j][k][l] %= MOD
                
    dp = ndp
#    print(dp)

print(sum(sum(sum(j) for j in i) for i in dp)%MOD)

Submission status: Accepted

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v
    return [nlist(n[1:], v) for _ in range(n[0])]
import random

# エントリーポイント
def main():
    N = input(int)

    dp = nlist([N + 1, 5, 5, 5], 0)
    dp[0][0][0][0] = 1
    for n in range(1, N + 1):
        for i in range(5):  # ["", "A", "C", "G", "T"]:
            for j in range(5):  # ["", "A", "C", "G", "T"]:
                for k in range(5):  # ["", "A", "C", "G", "T"]:
                    for l in range(1, 5):  # ["A", "C", "G", "T"]:
                        if j == 1 and k == 3 and l == 2: continue
                        if j == 3 and k == 1 and l == 2: continue
                        if j == 1 and k == 2 and l == 3: continue
                        if i == 1 and k == 3 and l == 2: continue
                        if i == 1 and j == 3 and l == 2: continue
                        dp[n][j][k][l] += dp[n - 1][i][j][k]
                        dp[n][j][k][l] %= MOD
    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)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
mod=1000000007

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

@lru_cache(maxsize=None)
def dfs(cur,last3):
    if cur==0:
        return 1
    ret=0
    for c in 'ACGT':
        if judge(last3+c):
            ret+=dfs(cur-1,last3[1:]+c)
            ret%=mod
    return ret

n=int(input())
print(dfs(n,'TTT'))

Submission status: Accepted

Solution code:



from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

num = [4,4,4,4,4,4,4,4,3,4,4,4,3,4,3,4,1,1,1]

for i in range(N - 3):
	num2 = [0]*19
	num2[0] = num[0] + num[1] + num[2] + num[3]
	num2[4] = num2[0]
	num2[5] = num2[0] - num[17]
	num2[6] = num2[0]
	num2[1] = num[4] + num[7] + num[10] + num[13]
	num2[7] = num2[1]
	num2[8] = num2[1] - num[13]
	num2[9] = num2[1]
	num2[2] = num[5] + num[8] + num[11] + num[14]
	num2[10] = num2[2]
	num2[11] = num2[2]
	num2[12] = num2[2] - num[8]
	num2[3] = num[6] + num[9] + num[12] + num[15]
	num2[13] = num2[3]
	num2[14] = num2[3] - num[9] - num[16] - num[18]
	num2[15] = num2[3]
	num2[16] = num[9]
	num2[17] = num[9]
	num2[18] = num[1]
	for i in range(19):
		num2[i] = num2[i] % 1000000007
	num = copy.deepcopy(num2)

print(sum(num[0:16]) % 1000000007)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A_1 = np.zeros((4,4), dtype='int64')
A_2 = np.ones((4,4), dtype='int64')
B = np.ones((4,4), dtype='int64')
for _ in range(n-2):
    A_3 = np.dot(B, A_2).T
    A_3 %= 10**9+7
    A_3[2,1] -= A_2[0,2]+A_1[0,2]+A_1[0,3]
    A_3[1,2] -= A_2[0,1]
    A_3[0,1] -= A_2[2,0]
    A_3[3,1] -= A_1[0,2]
    A_1, A_2 = A_2, A_3
print(np.sum(A_3)%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
 
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
#長さ0の文字列は1
#0,1,2(A,G,C)に関する制約しかないため
#Sは、TTTSと考えてもよい
dp[0][3][3][3] = 1
 
#swapしてAGCが発生しない文字列:=AGC,ACG,GAC,A?GC,AG?Cを含まない文字列
#A:=0,G:=1,C:=2,T:=3
 
#文字列の文字数
for i in range(n):
    #最後から1文字目
    for j in range(4):
        #最後から2文字目
        for k in range(4):
            #条件に当てはまるものがない場合
            if dp[i][j][k] == 0:
                continue
            #最後から3文字目
            for l in range(4):
                #新たに追加する文字
                for a in range(4):
                    #ダメな5条件をカット
 
                    #AGCの場合
                    if a == 2 and j == 1 and k == 0:continue
                    #GACの場合
                    if a == 2 and j == 0 and k == 1:continue
                    #ACGの場合
                    if a == 1 and j == 2 and k == 0:continue
                    #A?GCの場合
                    if a == 2 and j == 1 and l == 0:continue
                    #AG?Cの場合
                    if a == 2 and k == 1 and l == 0:continue
 
                    #ダメの条件を抜けると、aを足した文字列が作れる
                    dp[i+1][a][j][k] += dp[i][j][k][l]
                    dp[i+1][a][j][k] %= mod
 
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            #長さnの全通り回収
            ans += dp[n][j][k][l]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

k = 2
f = [1,4,16]
r = [{"AG":0,"GA":0,"AC":0,"AGG":0,"A":0,"G":0},
     {"AG":0,"GA":0,"AC":0,"AGG":0,"A":1,"G":1},
     {"AG":1,"GA":1,"AC":1,"AGG":0,"A":4,"G":4,"ATG":0,"AGT":0,"AT":1}]
while k < n:
    k += 1
    r.append({})
    r[k]["AC"] = r[k-1]["A"]-r[k-1]["GA"]
    r[k]["GA"] = r[k-1]["G"]
    r[k]["AG"] = r[k-1]["A"]
    r[k]["AGG"] = r[k-1]["AG"]
    r[k]["A"] = f[k-1]
    r[k]["G"] = f[k-1]-r[k-1]["AC"]
    r[k]["ATG"] = r[k-1]["AT"]
    r[k]["AT"] = r[k-1]["A"]
    r[k]["AGT"] = r[k-1]["AG"]
    f.append(0)
    f[k] = f[k-1]*4 - r[k-1]["AG"] - r[k-1]["GA"] - r[k-1]["AC"] - r[k-1]["AGG"] - r[k-1]["ATG"] - r[k-1]["AGT"]
print(f[n]%(10**9+7))

Submission status: Accepted

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

dp[0] = [1,1,1,1]
dp[1] = [4,4,4,4]
#AGC, ACG, GAC, A?GC,AG?C -> AGGC, ATGC,AGTC

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    MOD = 10**9 + 7
    # ?AGC, ?GAC, ?ACG, 
    # AG?C = (AGAC), (AGCC), AGGC, AGTC
    # A?GC = (AAGC)(ACGC)(AGGC), ATGC

    # AG?C,A?GC,?GAC,?ACG
    dp =[1] * 64
    A = 0
    C = 1
    G = 2
    T = 3
    #GAC
    dp[G * 4**2 + A * 4**1 + C * 4**0] = 0
    #ACG
    dp[A * 4**2 + C * 4**1 + G * 4**0] = 0
    #AGC
    dp[A * 4**2 + G * 4**1 + C * 4**0] = 0

    N = II()
    pre = dp
    for _ in range(N-3):
        #?AA →AAA,AAC,AAG,AAT
        pre = dp
        dp = [0] * 64
        for i in range(64):
            #GA
            # if i == (3 * 4**2 + 0 * 4**1 + 2 * 4**0)\
            # or i == (0 * 4**2 + 2 * 4**1 + 3 * 4**0):
            #     continue
            for j in range(4):
                #pre==?GA and j==C
                if i % 16 == G*4+A and j == C:
                    #print('GAC')
                    continue
                #pre == ?AC and j==G
                elif i % 16 == A*4+C and j == G:
                    #print('ACG')
                    continue
                #pre == ?AG and j == C
                elif i % 16 == A*4+G and j== C:
                    continue 
                #AG?C pre==AG? and j==C
                elif i // 4 == A*4+G and j == C:
                    continue
                #A?GC pre==A?G j==C
                elif i//16 == A and i%4 ==G and j == C:
                    continue

                dp[i%16*4+j] += pre[i]
        dp = list(map(lambda x:x%MOD, dp))

        
        

    print(sum(dp)%MOD)

    






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

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

Submission status: Accepted

Solution code:
import copy
def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]
    ans = sum(dp_list)%mod

print(ans)

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
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret
        

if __name__ == "__main__":
    n, mod = int(input()), 10 ** 9 + 7
    memo = [{} for i in range(n + 1)]
    print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:

N = int(input())

now = 4 # 4文字目から開始

lis = [1] * (4**3)

lis[2 * (4**1) + 1] = 0 #AGCはだめ
lis[1 * (4**1) + 2] = 0 #ACGはだめ
lis[2 * (4**2) + 1] = 0 #GACはだめ


while now <= N:

    nlis = [0] * (4**3)
    
    for i in range(4**3):

        #Aを追加(4で割って桁下げ)

        nlis[ ( i * 4 ) % 64 ] += lis[i]

        #Tを追加(4で割ったのち、3を加える)

        nlis[ (i * 4) % 64 + 3 ] += lis[i]

        #Gを追加(16で割ったあまりが1の時のみ不可)

        if i % 16 != 1:
            nlis[ (i * 4) % 64 + 2 ] += lis[i]

        #Cを追加(16で割ったあまりが2,8は不可/16で割った商が0かつ4で割ったあまり2不可/16で割った商が0かつ4で割った商2不可)

        if (i % 16 not in [2,8] ) and (not( i // 16 == 0 and i % 4 == 2)) and (not(i // 16 == 0 and i // 4 == 2)):

            nlis[ (i * 4) % 64 + 1 ] += lis[i]

    for j in range(4**3):

        lis[j] = nlis[j] % (10 ** 9 + 7)

    #print (lis)
        
    now += 1

print (sum(lis) % (10**9 + 7))

Submission status: Accepted

Solution code:
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# データ構造：ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)
# グラフ
class graph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def append(self, v1, v2, cost=1):
        self.graph[v1].append((v2, cost))
    # 最短経路：ダイクストラ法(Dijkstra's Algorithm)
    def dks(self, v):
        costs = [INF] * self.n
        costs[v] = 0
        done = [False] * self.n
        heap = heapque((0, v))
        while heap.que:
            c_cost, c_index = heap.pop()
            if done[c_index]:
                continue
            done[c_index] = True
            for n_index, n_cost in self.graph[c_index]:
                if c_cost + n_cost < costs[n_index]:
                    costs[n_index] = c_cost + n_cost
                    heap.push((costs[n_index], n_index))
        return costs

def main():
    N = int(input())
    dp = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]
    dp[0][0][0][0] = 1
    for i in range(N):
        for j in range(5):
            for k in range(5):
                for l in range(5):
                    for m in range(1, 5):
                        if k == 1 and l == 3 and m == 2: continue
                        if k == 1 and l == 2 and m == 3: continue
                        if k == 3 and l == 1 and m == 2: continue
                        if j == 1 and l == 3 and m == 2: continue
                        if j == 1 and k == 3 and m == 2: continue
                        dp[i + 1][k][l][m] += dp[i][j][k][l]
                        dp[i + 1][k][l][m] %= MOD
    r = 0
    for i in range(1, 5):
        for j in range(1, 5):
            for k in range(1, 5):
                r += dp[-1][i][j][k]
                r %= MOD
    print(r)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

MOD = 1000000007  # type: int
memo = []

def ok(last4: str):
    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(N: int, cur: int, last3: str):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret  = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(N, cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

def solve(N: int):
    print(dfs(N, 0, 'TTT'))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    global memo
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    memo = [{} for i in range(N+1)]
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

dp = {}
chars = ['A', 'G', 'C', 'T']

for cs in itertools.product(chars, repeat = 3):
    word = ''.join(cs)
    if word == 'AGC' or word == 'ACG' or word == 'GAC':
      dp[(3, word)] = 0
    else:
      dp[(3, word)] = 1
      
def includeagc(word):
  return 'AGC' in word

for i in range(4, N + 1):
  for cs in itertools.product(chars, repeat = 4):
    cs = list(cs)
    word = ''.join(cs)
    words = [word]
    for j in range(3):
      cs[j], cs[j + 1] = cs[j + 1], cs[j]
      words.append(''.join(cs))
      cs[j], cs[j + 1] = cs[j + 1], cs[j]
    if not any(includeagc(word) for word in words):
      dp[(i, word[1:4])] = (dp.get((i, word[1:4]), 0) + dp.get((i - 1, word[0:3]), 0)) % MOD
      
ans = sum([k[1] for k in dp.items() if k[0][0] == N]) % MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
dp = [[[[0]*4 for _ in [0]*4] for _ in [0]*4] for _ in [0]*(n+1)]
dp[0][3][3][3] = 1
for i in range(1, n+1):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for k in range(4):
          if (c2, c3, k) == (0, 1, 2) : continue
          if (c2, c3, k) == (1, 0, 2) : continue
          if (c2, c3, k) == (0, 2, 1) : continue
          if (c1, c3, k) == (0, 1, 2) : continue
          if (c1, c2, k) == (0, 1, 2) : continue
          dp[i][c2][c3][k] += dp[i-1][c1][c2][c3]
ans = 0
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      ans += dp[-1][c1][c2][c3]
      ans %= mod
print(ans)

Submission status: Accepted

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

for i in range(n):
    for b1 in range(4):
        for b2 in range(4):
            for b3 in range(4):
                for now in range(4):
                    if counter[i][b1][b2][b3] == 0:
                        continue
                    elif b1 == 0 and b3 == 1 and now == 2:
                        continue
                    elif b2 == 1 and b3 == 0 and now == 2:
                        continue
                    elif b2 == 0 and b3 == 2 and now == 1:
                        continue
                    elif b1 == 0 and b2 == 1 and now == 2:
                        continue
                    elif b2 == 0 and b3 == 1 and now == 2:
                        continue
                    else:
                        counter[i+1][b2][b3][now] += counter[i][b1][b2][b3]
                        counter[i+1][b2][b3][now] = counter[i+1][b2][b3][now] % mod

answer = 0
for b1 in range(4):
    for b2 in range(4):
        for b3 in range(4):
            answer += counter[n][b1][b2][b3]

print(answer % mod)

Submission status: Accepted

Solution code:
import sys
n=int(input())
if n==3:
  print(61)
  sys.exit()
mod=10**9+7
l=['A','C','G','T']
NG=['AGC','GAC','ACG']
NG2=['AAGC','ACGC','AGGC','ATGC','AGAC','AGCC','AGTC']
L=[]
for i1 in range(4):
  for i2 in range(4):
    for i3 in range(4):
      for i4 in range(4):
        L.append(l[i1]+l[i2]+l[i3]+l[i4])
dp=[[0 for i in range(256)] for j in range(n+1)]
for i in range(256):
  if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
    dp[4][i]=0
  else:
    dp[4][i]=1
for j in range(5,n+1):
  for i in range(256):
    if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
      dp[j][i]=0
    else:
      for i2 in range(256):
        if L[i2][1:4]==L[i][0:3]:
          dp[j][i]+=dp[j-1][i2]
    dp[j][i]%=mod
print(sum(dp[n])%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dp = [defaultdict(int) for _ in range(N+1)]
MOD = 10**9 + 7
dp[0]['TTT'] = 1


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


for n in range(N):
    for s, cnt in dp[n].items():
        for c in 'AGCT':
            ns = s+c
            if ok(ns):
                dp[n+1][ns[-3:]] = (dp[n+1][ns[-3:]]+cnt) % MOD

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

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
M = (10**9)+7
dic = {}
pdic = {}
pdic['AAA'] = 1
pdic['AAC'] = 1
pdic['AAG'] = 1
pdic['AAT'] = 1
pdic['ACA'] = 1
pdic['ACC'] = 1
pdic['ACG'] = 0
pdic['ACT'] = 1
pdic['AGA'] = 1
pdic['AGC'] = 0
pdic['AGG'] = 1
pdic['AGT'] = 1
pdic['ATA'] = 1
pdic['ATC'] = 1
pdic['ATG'] = 1
pdic['ATT'] = 1
pdic['CAA'] = 1
pdic['CAC'] = 1
pdic['CAG'] = 1
pdic['CAT'] = 1
pdic['CCA'] = 1
pdic['CCC'] = 1
pdic['CCG'] = 1
pdic['CCT'] = 1
pdic['CGA'] = 1
pdic['CGC'] = 1
pdic['CGG'] = 1
pdic['CGT'] = 1
pdic['CTA'] = 1
pdic['CTC'] = 1
pdic['CTG'] = 1
pdic['CTT'] = 1
pdic['GAA'] = 1
pdic['GAC'] = 0
pdic['GAG'] = 1
pdic['GAT'] = 1
pdic['GCA'] = 1
pdic['GCC'] = 1
pdic['GCG'] = 1
pdic['GCT'] = 1
pdic['GGA'] = 1
pdic['GGC'] = 1
pdic['GGG'] = 1
pdic['GGT'] = 1
pdic['GTA'] = 1
pdic['GTC'] = 1
pdic['GTG'] = 1
pdic['GTT'] = 1
pdic['TAA'] = 1
pdic['TAC'] = 1
pdic['TAG'] = 1
pdic['TAT'] = 1
pdic['TCA'] = 1
pdic['TCC'] = 1
pdic['TCG'] = 1
pdic['TCT'] = 1
pdic['TGA'] = 1
pdic['TGC'] = 1
pdic['TGG'] = 1
pdic['TGT'] = 1
pdic['TTA'] = 1
pdic['TTC'] = 1
pdic['TTG'] = 1
pdic['TTT'] = 1
for i in range(N-3):
  for k in pdic.keys():
    k = str(k)
    if k=='ACG' or k=='AGC' or k=='GAC':
      dic[k] = 0
    elif k[1:]=='GC':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    elif k[0]=='G' and k[2]=='C':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    else:
      dic[k] = pdic['A'+k[:-1]]+pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
  for k in pdic.keys():
    pdic[k] = dic[k]
if N==3:
  print(61)
else:
  for v in dic.values():
    ans += v
    ans = ans % M
  print(ans)

Submission status: Accepted

Solution code:
N = int(input())
mod = int(1E9+7)

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[2][i][j][k] = 1
dp[2][2][1][0] = 0
dp[2][1][2][0] = 0
dp[2][2][0][1] = 0

for i in range(3, N):
    for x in range(4):
        for y in range(4):
            dp[i][0][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][1][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][2][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][3][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
    
    dp[i][2][3][1] -= dp[i-1][3][1][0]
    dp[i][2][1][3] -= dp[i-1][1][3][0]
    dp[i][2][0][1] -= dp[i-1][0][1][0]
    dp[i][2][1][0] -= dp[i-1][1][0][0]
    dp[i][2][1][1] -= dp[i-1][1][1][0]
    
    dp[i][1][2][0] = 0
    dp[i][2][0][1] = 0
    dp[i][2][1][0] = 0
    
    


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

Submission status: Accepted

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

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

dp = [[[[0 for p in range(4)] for q in range(4)] for r in range(4)] for s in range(n)]
dp[0] = [[[1 for p in range(4)] for q in range(4)] for r in range(4)]  # n=3ですべて１
dp[0][0][1][2] = 0  # AGC
dp[0][0][2][1] = 0  # ACG
dp[0][1][0][2] = 0  # CAG

for i in range(n-3):
    for j in range(4):  # 3文字前
        for k in range(4):  # 2文字前
            for l in range(4):  # 1文字前
                for m in range(4):  # 次の文字
                    if j==0 and k==1 and m==2:  # AG_C
                        continue
                    if j==0 and l==1 and m==2:  # A_GC
                        continue
                    dp[i+1][k][l][m] += dp[i][j][k][l]  # 次の文字を足す
                    dp[i+1][k][l][m] %= MOD
                dp[i+1][0][1][2] = 0  # AGC
                dp[i+1][0][2][1] = 0  # ACG
                dp[i+1][1][0][2] = 0  # CAG

ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[n-3][j][k][l]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import itertools

# AGC
# ACG
# GAC
# A*GC
# AG*C
mod = 10 ** 9 + 7
N = int(input())
keys = [i + j + k for i, j, k in itertools.product('ACGT', repeat=3)]
dp = [dict() for _ in range(N)]
for i in range(N):
    for key in keys:
        dp[i][key] = 0

for key in keys:
    if key in ['AGC', 'ACG', 'GAC']:
        val = 0
    else:
        val = 1
    dp[2][key] = val

for i in range(2, N - 1):
    for key, val in dp[i].items():
        nexts = {'A', 'C', 'G', 'T'}
        if key[1:] == 'AG':
            nexts.discard('C')
        elif key[1:] == 'AC':
            nexts.discard('G')
        elif key[1:] == 'GA':
            nexts.discard('C')
        if key[0] == 'A' and (key[1] == 'G' or key[2] == 'G'):
            nexts.discard('C')
        for ne in nexts:
            next_key = key[1:] + ne
            dp[i + 1].setdefault(next_key, 0)
            dp[i + 1][next_key] += val
print(sum(dp[N - 1].values()) % mod)