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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    b = S()
    b = b[0]
    if b == "A":
        print("T")
    elif b == "T":
        print("A")
    elif b == "C":
        print("G")
    elif b == "G":
        print("C")
    return

#B
def B():
    s = S()
    agct = ["A", "G", "C", "T"]
    ans = 0
    for num, i in enumerate(s):
        ansb = 0
        if i in agct:
            ansb += 1
            for k in range(num+1, len(s)):
                if s[k] in agct:
                    ansb += 1
                else:
                    break
        ans = max(ans, ansb)
    print(ans)
    return

#C
def C():
    n, q = LI()
    s = S()
    ans = [0 for i in range(n+1)]
    ac = 0
    for num, ss in enumerate(s):
        if (not ac) and ss == "A":
            ac = 1
            ans[num] = ans[num - 1]
        elif ac and ss == "C":
            ac = 0
            ans[num] = ans[num - 1] + 1
        else:
            if ss == "A":
                ac = 1
            else:
                ac = 0
            ans[num] = ans[num - 1]
    lr = LIR_(q)
    for l,r in lr:
        print(ans[r]-ans[l])

    return

#D
def D():
    def check(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("012") >= 1:
                return False
        return True

    n = II()
    ans = [[[[0 for i in range(4)] for k in range(4)] for l in range(4)] for m in range(n+1)]
    ans[0][3][3][3] = 1
    for l in range(n):
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    if ans[l][a][b][c] == 0:
                        continue
                    for new in range(4):
                        if check(str(a) + str(b) + str(c) + str(new)):
                            ans[l + 1][b][c][new] += ans[l][a][b][c]
                            ans[l + 1][b][c][new] %= mod
    num_ans = 0
    for a in range(4):
        for b in range(4):
            for c in range(4):
                num_ans += ans[n][a][b][c]
                num_ans %= mod
    print(num_ans)                            
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = [defaultdict(int) for i in range(N + 1)]
dp[0]['TTT'] = 1
for length in range(N):
    for c1 in 'ACGT':
        for c2 in 'ACGT':
            for c3 in 'ACGT':
                if dp[length][c3 + c2 + c1] == 0:
                    continue
                for c0 in 'ACGT':
                    if c2 + c1 + c0 in ['AGC', 'ACG', 'GAC']:
                        continue
                    if c3 + c1 + c0 == 'AGC':
                        continue
                    if c3 + c2 + c0 == 'AGC':
                        continue
                    dp[length + 1][c2 + c1 + c0] += dp[length][c3 + c2 + c1]

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()

    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
    # 初期状態は直近3文字がTTTと見なせる
    dp[0][3][3][3] = 1

    A, C, G, T = 0, 1, 2, 3
    for i in range(n):
        for a, b, c, d in itertools.product(range(4), repeat=4):
            if b == A and c == G and d == C: continue
            if b == A and c == C and d == G: continue
            if b == G and c == A and d == C: continue
            if a == A and b == G and d == C: continue
            if a == A and c == G and d == C: continue
            dp[i + 1][b][c][d] = (dp[i + 1][b][c][d] + dp[i][a][b][c]) % MOD

    ans = 0
    for a, b, c in itertools.product(range(4), repeat=3):
        ans = (ans + dp[n][a][b][c]) % MOD

    return ans


print(main())

Submission status: Accepted

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

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

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

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
N = int(input())
MOD = int(1e9+7)
A = [[[ [0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(102)]

A[0][3][3][3] = 1
# AGCT 0123
# x012
# x021
# x102
# 0x12
# 01X2
for x in range(N+1):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if A[x][i][j][k] == 0:
          continue
        for a in range(4):
          if (a == 2 and i == 1 and j == 0): continue
          if (a == 1 and i == 2 and j == 0): continue
          if (a == 2 and i == 0 and j == 1): continue
          if (a == 2 and i == 1 and k == 0): continue
          if (a == 2 and j == 1 and k == 0): continue
          A[x+1][a][i][j] = (A[x+1][a][i][j] + A[x][i][j][k]) % MOD
          
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans = (ans + A[N][i][j][k]) % MOD
      
print(ans)

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][3][3][3]=1
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 k==0 and l==2 and m==1: continue
                    elif k==2 and l==0 and m==1: continue
                    elif k==0 and l==1 and m==2: continue
                    elif j==0 and l==2 and m==1: continue
                    elif j==0 and k==2 and m==1: continue
                    else: dp[i+1][k][l][m]+=dp[i][j][k][l]
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%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())

mod = 10 ** 9 + 7

# dp[N][4][4][4]
dp = []
for _ in range(N):
    n = []
    for _ in range(4):
        l = []
        for _ in range(4):
            c = [0] * 4
            l.append(c)
        n.append(l)
    dp.append(n)

CHAR_A = 0
CHAR_C = 1
CHAR_G = 2
CHAR_T = 3

for c in range(4):
    for r in range(4):
        dp[1][CHAR_T][c][r] = 1

for i in range(2, N):
    for l in range(4):
        for c in range(4):
            for r in range(4):
                for a in range(4):
                    if c == CHAR_A and r == CHAR_G and a == CHAR_C:
                        continue
                    if c == CHAR_A and r == CHAR_C and a == CHAR_G:
                        continue
                    if c == CHAR_G and r == CHAR_A and a == CHAR_C:
                        continue
                    if l == CHAR_A and c == CHAR_G and a == CHAR_C:
                        continue
                    if l == CHAR_A and r == CHAR_G and a == CHAR_C:
                        continue
                    dp[i][c][r][a] += dp[i-1][l][c][r]

ans = 0
for l in range(4):
    for c in range(4):
        for r in range(4):
            ans += dp[N-1][l][c][r]

print(ans%mod)

Submission status: Accepted

Solution code:
import collections, itertools
N = int(input())
mod = 10**9 + 7
# cd = collections.defaultdict
# dp = cd(lambda: cd(lambda: cd(lambda: cd(int))))
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
      for _ in range(N + 1)]
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(range(4), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)
# https://www.youtube.com/watch?v=w2AEXSloYk8

Submission status: Accepted

Solution code:
import itertools

MOD = 10**9 + 7


def is_ok(p, c):
    if c == "C":
        if p[1:] == "AG" or p[1:] == "GA" or p[:2] == "AG" or (p[0] == "A" and p[2] == "G"):
            return False
    if c == "G" and p[1:] == "AC":
        return False
    return True


def main():
    N = int(input())
    ans = {"".join(x): 1 for x in itertools.product("ACGT", repeat=3)}
    for p in ["AGC", "ACG", "GAC"]:
        ans[p] = 0
    for _ in range(3, N):
        prev = ans
        ans = {"".join(x): 0 for x in itertools.product("ACGT", repeat=3)}
        for c in "ACGT":
            for p in prev:
                if is_ok(p, c):
                    nxt = p[1:] + c
                    ans[nxt] = (ans[nxt] + prev[p]) % MOD
    print(sum(ans.values()) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    atgc = ["A", "T", "G", "C"]
    mod = 10 ** 9 + 7
    n = int(input())

    dp = [[[[0 for i3 in range(4)] for i2 in range(4)] for i1 in range(4)] for i0 in range(n)]

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

    for t in range(n-3):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    dp[t+1][i][j][k] = dp[t][0][i][j] + dp[t][1][i][j] + dp[t][2][i][j] + dp[t][3][i][j]

        for i in range(4):
            dp[t+1][i][2][3] -= dp[t][0][i][2]
        for i in range(4):
            dp[t+1][2][i][3] -= dp[t][0][2][i]
        #AGG→GGC
        dp[t + 1][2][2][3] += dp[t][0][2][2]


        dp[t+1][0][2][3] = 0
        dp[t+1][0][3][2] = 0
        dp[t+1][2][0][3] = 0

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

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+1)]
dp[0][3][3][3] = 1

for n in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                if dp[n][a][b][c] == 0:
                    continue
                
                for l in range(4):
                    if l == 2 and a == 1 and b == 0:
                        continue
                    if l == 2 and a == 0 and b == 1:
                        continue
                    if l == 1 and a == 2 and b == 0:
                        continue
                    if l == 2 and a == 1 and c == 0:
                        continue
                    if l == 2 and b == 1 and c == 0:
                        continue

                    dp[n+1][l][a][b] += dp[n][a][b][c]
                    dp[n+1][l][a][b] %= MOD

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

Submission status: Accepted

Solution code:
import collections, itertools
N = int(input())
mod = 10**9 + 7
cd = collections.defaultdict
dp = cd(lambda: cd(lambda: cd(lambda: cd(int))))
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(range(4), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)
# https://www.youtube.com/watch?v=w2AEXSloYk8

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import defaultdict
from itertools import  product
def main():
    N=input()

    dp = [defaultdict(int) for i in range(101)]
    def ok(s):
        if s[:-1] in ("agc", "acg", "gac"):
            return False        
        if s[1:] in ("agc", "acg", "gac"):
            return False
        if s[0:2] == "ag" and s[3] == "c":
            return False
        if s[0] == "a" and s[2:4] == "gc": 
            return False
        return True

    if N==3:
        print(61)
        return

    for s in product("atgc", repeat=4):
        s="".join(s)
        if ok(s):
            dp[4][s]=1
        else:
            dp[4][s]=0
    
    i=5
    while i<=N:
        for k,v in dp[i-1].iteritems():
            for c in "atgc":
                n=k[1:]+c
                if ok(n):
                    dp[i][n] += dp[i-1][k]
        i+=1
    print(sum(dp[N].values()) % (10**9+7))
main()

Submission status: Accepted

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

chars = "ACGT"
cache = dict()

def is_valid(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        s = last4[:i] + last4[i + 1] + last4[i] + last4[i + 2:]
        if "AGC" in s:
            return False
    return True

def calc2(idx, last3):
    key = str(idx) + last3
    if key in cache:
        return cache[key]
    if idx == N:
        return 1
    ret = 0
    for c in chars:
        ns = last3 + c
        if is_valid(ns):
            ret = (ret + calc2(idx + 1, ns[1:])) % MOD
    ret = ret % MOD
    cache[key] = ret
    return ret
print(calc2(0, "   "))

Submission status: Accepted

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

for 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 a in range(4):
                    if(a == 2 and l == 1 and k == 0): continue
                    if(a == 1 and l == 2 and k == 0): continue
                    if(a == 2 and l == 0 and k == 1): continue
                    if(a == 2 and l == 1 and j == 0): continue
                    if(a == 2 and k == 1 and j == 0): continue
                    dp[i+1][k][l][a] += dp[i][j][k][l]
                    dp[i+1][k][l][a] %= 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:
import re,functools as f;d=f.lru_cache(999)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print(d(int(input()),'TTT'))

Submission status: Accepted

Solution code:
from itertools import product
import re

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

dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'.*AGC|.*ACG|.*GAC|A.GC|AG.C|'

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for next_s in 'AGCT':
            if re.match(NG_pattern, last_3 + next_s).group():
                continue
            else:
                dp[i + 1][last_3[1:] + next_s] += dp[i][last_3]
                dp[i + 1][last_3[1:] + next_s] %= MOD

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

Submission status: Accepted

Solution code:
from itertools import product
import re
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'.*AGC|.*ACG|.*GAC|A.GC|AG.C|'


for i in range(1, N + 1):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for pre_s in 'AGCT':
            if re.match(NG_pattern, pre_s + last_3).group():
                continue
            else:
                dp[i][pre_s + last_3[:-1]] += dp[i - 1][last_3]
                dp[i][pre_s + last_3[:-1]] %= MOD

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

Submission status: Accepted

Solution code:
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
mod = 7 + 10 ** 9
#A:1, C:2, G:3, T:4
#132, 123, 312, 1x32, 13x2は不可

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

def agc(ppp, pp, p, i, memo):
    if i == N: return 1
    try:
        return memo[(ppp, pp, p, i)]
    except KeyError:
        Ans = 0
        if ppp == 1:
            if pp == 3:
                Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif pp == 1:
                if p == 2:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 4, i+1, memo)
                elif p == 3:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif p == 3:
                Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
        else:
            if pp == 1:
                if p == 2:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 4, i+1, memo)
                elif p == 3:
                    Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            elif pp == 3:
                if p == 1: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
                else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
            else: Ans = agc(pp, p, 1, i+1, memo) + agc(pp, p, 2, i+1, memo) + agc(pp, p, 3, i+1, memo) + agc(pp, p, 4, i+1, memo)
        Ans %= mod
        memo[(ppp, pp, p, i)] = Ans
        return Ans

print(agc(0, 0, 0, 0, memo))

Submission status: Accepted

Solution code:
from itertools import product
import re
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'AGC.*|ACG.*|GAC.*|A.GC|AG.C|'

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for next_s in 'AGCT':
            if re.match(NG_pattern, last_3 + next_s).group():
                continue
            else:
                dp[i + 1][last_3[1:] + next_s] += dp[i][last_3]
                dp[i + 1][last_3[1:] + next_s] %= MOD


ans = 0
for key, value in dp[-1].items():
    if re.match(NG_pattern, key).group():
        continue
    ans += value
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# # # coding=utf-8
# # # Author: lee215

get = lambda: int(raw_input().strip())

import collections


def valid(S):
    if "AGC" in S:
        return False
    for i in xrange(len(S)):
        S2 = S[:i] + S[i:i + 2][::-1] + S[i + 2:]
        if "AGC" in S2:
            return False
    return True


N = get()
# N = 100
mod = 10**9 + 7
count = collections.Counter({"": 1})
for _ in xrange(N):
    count2 = collections.Counter({"": 0})
    for pre in count:
        for X in "AGCT":
            cur = pre + X
            if valid(cur):
                count2[cur[-3:]] += count[pre] % mod
    count = count2


print sum(count.values()) % mod

Submission status: Accepted

Solution code:

dp = []
mod = 10 ** 9 + 7

def check(pre_3, pre_2, pre_1, now_num):
    if pre_2 == 0 and pre_1 == 2 and now_num == 1:
        return 1
    if pre_2 == 2 and pre_1 == 0 and now_num == 1:
        return 1
    if pre_2 == 0 and pre_1 == 1 and now_num == 2:
        return 1
    if pre_3 == 0 and pre_2 == 2 and now_num == 1:
        return 1
    if pre_3 == 0 and pre_1 == 2 and now_num == 1:
        return 1
    return 0

def print_ans(num):
    global dp, mod
    count = 0
    for pre_3 in range(4):
        for pre_2 in range(4):
            for pre_1 in range(4):
                count += dp[num][pre_3][pre_2][pre_1]
    print(count % mod)

# 0:'A', 1:'C', 2:'G', 3:'T'
def start_process(num):
    global dp, mod
    dp = [[[[0, 0, 0, 0] for k in range(4)] for j in range(4)] for i in range(num + 1)]
    dp[0][3][3][3] = 1
    for char_num in range(num):
        for pre_3 in range(4):
            for pre_2 in range(4):
                for pre_1 in range(4):
                    for now_num in range(4):
                        if check(pre_3, pre_2, pre_1, now_num):
                            continue
                        dp[char_num + 1][pre_2][pre_1][now_num] += dp[char_num][pre_3][pre_2][pre_1]
                        dp[char_num + 1][pre_2][pre_1][now_num] %= mod
    print_ans(num)

def main():
    num = int(input())
    start_process(num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG = {'AGC', 'ACG', 'GAC', 'AGGC', 'ACGC', 'ATGC', 'AGAC', 'AGTC'}

for i in range(N):
    for last_3 in product('AGCT', repeat=3):
        # 3文字out
        if ''.join(last_3) in NG:
            continue

        for next_s in 'AGCT':
            X = ''.join(last_3) + next_s
            # 4文字目out
            if X in NG:
                continue
            else:
                dp[i + 1][X[1:]] += dp[i][X[:-1]]
                dp[i + 1][X[1:]] %= MOD

ans = 0
for key, value in dp[-1].items():
    if key not in NG:
        ans += value
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
s = 'ACGT'
bad = ['AGC', 'ACG', 'GAC', 'ACGC', 'AGGC', 'ATGC', 'AGAC', 'AGGC', 'AGTC']

def valid(a):
    if a[0:3] in bad:
        return False
    if a[1:] in bad:
        return False
    if a in bad:
        return False
    return True

n = int(input())

dp = [[[1 for k in range(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):
            t = s[k]+s[j]+s[i]
            if t in ['AGC', 'ACG', 'GAC']:
                dp[i][j][k] = 0

for pos in range(3,n):
    nx = [[[0 for k in range(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):
                    t = s[k]+s[j]+s[i]+s[l]

                    if valid(t):
                        nx[l][i][j] += dp[i][j][k]
                        nx[l][i][j] %= mod
    dp = nx

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

Submission status: Accepted

Solution code:
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする
import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
#AGCT
#0123
dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3]=1
mod=1000000007
for c in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for a in range(4):
          if a==1 and i==2 and j==0:continue
          if a==2 and i==1 and j==0:continue
          if a==2 and i==0 and j==1:continue
          if a==2 and j==1 and k==0:continue
          if a==2 and i==1 and k==0:continue
          dp[c+1][a][i][j]+=dp[c][i][j][k]
          dp[c+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(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
mod = 10**9+7
 
dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3] = 1
 
for i in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):        
        for new in range(4):
          if new == 2 and c1 == 1 and c2 == 0:
            continue
          if new == 2 and c1 == 0 and c2 == 1:
            continue
          if new == 1 and c1 == 2 and c2 == 0:
            continue
          if new == 2 and c1 == 1 and c3 == 0:
            continue
          if new == 2 and c2 == 1 and c3 == 0:
            continue
          dp[i+1][new][c1][c2] += dp[i][c1][c2][c3]
          dp[i+1][new][c1][c2] %= mod


res = 0

for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):        
      res += dp[N][c1][c2][c3]
 
print(int(res%mod))

Submission status: Accepted

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

D[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):
                for x in range(4):
                    if k == 0 and l == 1 and x == 2:
                        continue
                    if k == 0 and l == 2 and x == 1:
                        continue
                    if k == 1 and l == 0 and x == 2:
                        continue
                    if j == 0 and l == 1 and x == 2:
                        continue
                    if j == 0 and k == 1 and x == 2:
                        continue
                    D[i + 1][k][l][x] += D[i][j][k][l] % mod
                    D[i + 1][k][l][x] %= mod
                    
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += D[N][j][k][l]
            ans %= mod
                    
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)