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:

from collections import defaultdict


def submit():
    n = int(input())
    modp = 10 ** 9 + 7
    chars = ["A", "C", "G", "T"]
    modp = 10 ** 9 + 7
    # ACGTの4通りの遷移
    # 禁止は次の通り
    # AG -> C
    # A*G -> C
    # GA -> C
    # AC -> G
    # AG* -> C

    # このため,直前の三文字を覚えるようなdpをする
    dp = [defaultdict(int) for _ in range(n + 1)]

    for c1 in chars:
        for c2 in chars:
            for c3 in chars:
                k = c1 + c2 + c3
                if k == "AGC":
                    continue
                if k == "ACG":
                    continue
                if k == "GAC":
                    continue

                dp[3][k] = 1

    for i in range(4, n + 1):
        for k, v in dp[i - 1].items():
            for c in chars:
                # *AG -> C
                if k[1] == "A" and k[2] == "G" and c == "C":
                    continue
                # A*G -> C
                if k[0] == "A" and k[2] == "G" and c == "C":
                    continue
                # *GA -> C
                if k[1] == "G" and k[2] == "A" and c == "C":
                    continue
                # *AC -> G
                if k[1] == "A" and k[2] == "C" and c == "G":
                    continue
                # AG* -> C
                if k[0] == "A" and k[1] == "G" and c == "C":
                    continue

                new_k = k[1:] + c
                dp[i][new_k] += dp[i - 1][k]
                dp[i][new_k] %= modp

    ans = sum(v % modp for v in dp[n].values())
    print(ans % modp)
    

submit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def alpha_to_num(s):
        """
        >>> alpha_to_num('AAA')
        0
        >>> alpha_to_num('AGC')
        11
        >>> alpha_to_num('CCC')
        63
        """
        assert(len(s) == 3)
        d = {'A':0, 'T':1, 'G':2, 'C':3}
        num = 0
        for i in range(3):
            num += pow(4, 2 - i) * d[s[i]]
        return num
    
    def num_to_alpha(num):
        """
        >>> num_to_alpha(0)
        'AAA'
        >>> num_to_alpha(11)
        'AGC'
        >>> num_to_alpha(63)
        'CCC'
        """
        assert(0 <= num < 4 ** 3)
        d = {0:'A', 1:'T', 2:'G', 3:'C'}
        L = []
        for i in range(2, -1, -1):
            q = num // pow(4, i)
            L.append(d[q])
            num -= pow(4, i) * q
        return ''.join(L)
    

    def distribute(num, s, num_of_pattern, seq):
        """
        最後の 3 文字が s (数字に直すと num) であるようなものに対し、末尾に A T G C を追加することを考える
        valid pattern を数え上げ、seq の適切な位置にパターンを加算する
        """
        for char in ['A', 'T', 'G', 'C']:
            new_s = s[1:] + char
            new_num = alpha_to_num(new_s)
            if char == 'G':
                if new_s == 'ACG':
                    continue
            elif char == 'C':
                if s in ['AGT', 'AGG', 'ATG']:
                    continue
                if new_s in ['AGC', 'GAC']:
                    continue
            seq[new_num] = (seq[new_num] + num_of_pattern) % mod

    
    n = ii()
    # a:0, t:1, g:2, c:3 とする
    # dp[i][num] = (i 文字で末尾の 4 進数表記が num となる適切な文字列の数)
    dp = [[0] * (4 ** 3) for _ in range(n + 1)]
    
    for num in range(4 ** 3):
        dp[3][num] = 1 if num_to_alpha(num) not in ['AGC', 'ACG', 'GAC'] else 0
    
    for i in range(3, n):
        # dp[i] は既知。dp[i+1] に配る
        for num in range(4 ** 3):
            distribute(num, num_to_alpha(num), dp[i][num], dp[i+1])


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


if __name__ == "__main__":
    # import doctest
    # doctest.testmod()

    main()

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10 ** 9 + 7

total = 4 ** N

if N == 3:
    sub = 3
    ans = total - sub
    
elif N >= 4:
    last_three = [{} for _ in range(N - 3 + 1)]
    for n in range(N - 3 + 1):
        for i in ['A', 'G', 'C', 'T']:
            for j in ['A', 'G', 'C', 'T']:
                for k in ['A', 'G', 'C', 'T']:
                    if [i, j, k] != ['A', 'G', 'C'] and [i, j, k] != ['A', 'C', 'G'] and [i, j, k] != ['G', 'A', 'C']:
                        last_three[n]["".join([i, j, k])] = 0
    for k in last_three[0].keys():
        last_three[0][k] = 1
    for i in range(4, N + 1):
        for k in last_three[i - 4].keys():
            if k[1] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'A' and k[2] == 'C':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[1] == 'G' and k[2] == 'A':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[2] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            elif k[0] == 'A' and k[1] == 'G':
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD
            else:
                last_three[i - 3]["".join([k[1], k[2], 'A'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] += last_three[i - 4][k] % MOD
                last_three[i - 3]["".join([k[1], k[2], 'A'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'G'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'C'])] %= MOD
                last_three[i - 3]["".join([k[1], k[2], 'T'])] %= MOD

    ans = sum(last_three[N - 3].values()) % MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

N = int(input())


"""dp = dict()
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            for c4 in "ACGT":
                s = c1 + c2 + c3 + c4
                if s[0:3] in ("AGC", "ACG", "GAC"):
                    continue
                if s[1:4] in ("AGC", "ACG", "GAC"):
                    continue
                if s in ("AGGC", "AGTC", "ATGC"):
                    continue

                dp[s] = 1"""

dp = {"TTT": 1}
for _ in range(N):
    new_dp = defaultdict(int)
    for s, count in dp.items():
        new_dp[s[1:] + 'A'] += count
        new_dp[s[1:] + 'T'] += count
        if s[1:] != "AC":
            new_dp[s[1:] + 'G'] += count
        if s not in ("AGG", "AGT", "ATG") and s[1:] not in ("AG", "GA"):
            new_dp[s[1:] + 'C'] += count

    dp = dict()
    for k, v in new_dp.items():
        dp[k] = v % MOD

print(sum(dp.values()) % MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    MOD = 10**9+7
    N = int(input())
    I, J, K, L = N, 4, 4, 4
    # dpテーブル dp[i][j][k][l]:=i文字目までで末尾3桁が'ijk'のものの個数であるとき作れる，長さiの文字列の個数
    dp = [[[[0]*(L+1) for _ in range(K+1)] for _ in range(J+1)]
          for _ in range(I+1)]
    # 初期条件
    dp[0][0][0][0] = 1
    # ループ
    for i in range(1, I+1):
        for j in range(J+1):
            for k in range(K+1):
                for l in range(L+1):
                    for a in range(1, 5):

                        if [k, l, a] == [1, 3, 2]:
                            continue
                        if [k, l, a] == [1, 2, 3]:
                            continue
                        if [k, l, a] == [2, 1, 3]:
                            continue
                        if [j, l, a] == [1, 2, 3]:
                            continue
                        if [j, k, a] == [1, 2, 3]:
                            continue

                        dp[i][k][l][a] += dp[i-1][j][k][l]

    ans = 0
    for j in range(1, 5):
        for k in range(1, 5):
            for l in range(1, 5):
                ans += dp[I][j][k][l]

    print(ans % MOD)


resolve()

Submission status: Accepted

Solution code:
N = int(input())
mod = 10 ** 9 + 7
dp = [{} for i in range(N)]
forbid = set(['AGC', 'GAC', 'ACG'])


def search(i, prefix):
    if prefix in forbid:
        return 0
    elif i == N:
        return 1
    elif prefix in dp[i]:
        return dp[i][prefix]

    ret = 0
    for c in 'ACGT':
        if prefix[0] == 'A' and (prefix[1] == 'G' or prefix[2] == 'G') and c == 'C':
            continue
        ret += search(i + 1, prefix[1:] + c)
    dp[i][prefix] = ret % mod
    return ret % mod


print(search(0, 'BBB'))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    chars = "ACGT"

    if n == 3:
        print(61)
        sys.exit()
    elif n == 4:
        print(230)
        sys.exit()

    from collections import deque, Counter
    que = deque()

    for ch1 in chars:
        for ch2 in chars:
            que.append((ch1 + ch2, 2))

    ans = 0
    str_set = set()
    counter = Counter()

    while que:
        cur, length = que.popleft()
        length_next = length + 1
        for ch in chars:
            ok = True
            nx = cur + ch
            if length_next == 3:
                if "AGC" in nx:
                    continue
                for j in range(2):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    que.append((nx, length_next))
            if length_next == 4:
                if "AGC" in nx:
                    ok = False
                for j in range(3):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    counter[nx] += 1
                    str_set.add(nx)

    for _ in range(n - 4):
        counter_next = Counter()
        for st in str_set:
            for ch in chars:
                nx = st[1:] + ch
                if nx in str_set:
                    counter_next[nx] += counter[st]
                    counter_next[nx] %= MOD
        counter = counter_next

    ans = sum(counter.values())
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
#dp[i][x][y][z] i文字目、3つ前がx, 2つ前がy, 1つ前がz
#A->0, C->1, G->2, T->3
#だめなパターンはA-GC, AG-C, GAC, ACGのみ

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

for i in range(3, n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for w in range(4):
                    if (y, z, w) == (2, 0, 1):
                        continue
                    if (y, z, w) == (0, 1, 2):
                        continue
                    if (y, z, w) == (0, 2, 1):
                        continue
                    if (x, y, w) == (0, 2, 1):
                        continue
                    if (x, z, w) == (0, 2, 1):
                        continue
                    dp[i+1][y][z][w] += dp[i][x][y][z]
                    dp[i+1][y][z][w] %= 10**9+7
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:
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A, G, C, T = 0, 1, 2, 3
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for j in range(4):  # i - 2 文字目
        for k in range(4):  # i - 1 文字目
            for l in range(4):  # i 文字目
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    for i in range(4, N+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 6)
import math
from collections import Counter
from collections import deque
from operator import itemgetter
import time, random
MOD = 10 ** 9 + 7
from itertools import permutations

def dfs(s):
    if len(s) == N:
        return 1
    if (s[-2] == 'A' and s[-1] == 'G') or (s[-2] == 'G' and s[-1] == 'A'):
        return dfs(s+'A') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD
    elif s[-2] == 'A' and s[-1] == 'C':
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'T') % MOD
    else:
        return dfs(s+'A') % MOD + dfs(s+'C') % MOD + dfs(s+'G') % MOD + dfs(s+'T') % MOD

def main():
    N = int(readline())
    A, G, C, T = 0, 1, 2, 3
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for j in range(4):  # i - 2 文字目
        for k in range(4):  # i - 1 文字目
            for l in range(4):  # i 文字目
                if j == A and k == G and l == C:  continue
                if j == A and k == C and l == G:  continue
                if j == G and k == A and l == C:  continue
                dp[3][j][k][l] = 1
    
    for i in range(4, N+1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == A and k == G and l == C:  continue
                        if j == A and k == C and l == G:  continue
                        if j == G and k == A and l == C:  continue
                        if m == A and k == G and l == C:  continue
                        if m == A and j == G and l == C:  continue
                        dp[i][j][k][l] += dp[i-1][m][j][k]
                        dp[i][j][k][l] %= MOD
    
    res = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                res += dp[N][j][k][l]
                res %= MOD
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    # dp[i][j][k][l] := 長さiの文字において，後ろから3つ目の文字がj,
    # 後ろから2つ目の文字がk, 後ろから1つの文字がlの時の組み合わせ数
    dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(N + 1)]

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

    # 文字の意味は，0 => None, 1 => A, 2 => G, 3 => C, 4 => T
    dp[0][0][0][0] = 1
    for i in range(1, N + 1):
        for j in range(5):
            for k in range(5):
                for l in range(5):
                    for m in range(1, 5):
                        if k == A and l == G and m == C:
                            continue
                        if k == A and l == C and m == G:
                            continue
                        if k == G and l == A and m == C:
                            continue
                        if j == A and l == G and m == C:
                            continue
                        if j == A and k == G and m == C:
                            continue

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
mod = 10**9+7
dp = [{} for _ in range(n+1)]

moji = ['A','C','G','T']
for c1 in moji:
    for c2 in moji:
        for c3 in moji:
            mojis = c1+c2+c3
            if mojis in ['AGC','GAC','ACG']:continue
            if mojis in dp[3]:
                dp[3][mojis] += 1
            else:
                dp[3][mojis] = 1

for i in range(4,n+1):
    for c in moji:
        for c1 in moji:
            for c2 in moji:
                for c3 in moji:
                    mojis = c1+c2+c3
                    if mojis in ['AGC','GAC','ACG']:continue
                    nowmoji = c2+c3+c
                    if nowmoji in ['AGC','GAC','ACG']:continue
                    if c1 =='A' and c3 == 'G' and c == 'C':continue
                    if c1 =='A' and c2 == 'G' and c == 'C':continue
                    if nowmoji in dp[i]:
                        dp[i][nowmoji] += dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod
                    else:
                        dp[i][nowmoji] =  dp[i-1][mojis]%mod
                        dp[i][nowmoji] %=mod

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

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	#A:0 G:1 C:2 T:3
	DP = [[0] * 64 for i in range(N)]
	for i in range(64):
		DP[2][i] = 1
	DP[2][6] = 0
	DP[2][9] = 0
	DP[2][18] = 0

	for p in range(2, N - 1):
		for i in range(4):
			for j in range(4):
				for k in range(4):
					for s in range(4):
						if not ((i == 0 and k == 1 and s == 2) or (i == 0 and j == 1 and s == 2)):
							DP[p + 1][16 * j + 4 * k + s] += DP[p][16 * i + 4 * j + k]
							DP[p + 1][16 * j + 4 * k + s] %= con

		DP[p + 1][6] = 0
		DP[p + 1][9] = 0
		DP[p + 1][18] = 0

	ans = sum(DP[N - 1])
	print(ans % con)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
  
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] #AGC
  dp[i][1] -= dp[i-2][2] #GAC
  dp[i][1] -= dp[i-3][0]*3 #AGTC,AGGC,ATGC
  dp[i][2] -= dp[i-2][0] #ACG
  dp[i][2] += dp[i-3][2] #GACG
  
print(sum(dp[n-1])%mod)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N = int(input())

    """
    ダメワードは
        ACG, AGC, GAC, AxGC, AGxC (xはワイルドカード)
    なので、後ろ３文字を見ながらdpすればよさげ
    """

    char = ['A', 'C', 'G', 'T']
    NG1 = {"ACG", "AGC", "GAC"}
    NG2 = {"AAGC", "ACGC", "AGGC", "ATGC", "AGAC", "AGCG", "AGGC", "AGTC"}
    key = []
    for x in char:
        for y in char:
            for z in char:
                word = x + y + z
                if word not in NG1:
                    key.append(word)
    
    zeros = [0] * len(key)
    ones = [1] * len(key)
    d = dict(zip(key, ones))
    
    for _ in range(N - 3):
        d2 = dict(zip(key, zeros))
        for word in d:
            x, y, z = list(word)
            for w in char:
                if (y + z + w not in NG1) and (x + y + z + w not in NG2):
                    d2[y + z + w] += d[x + y + z]
                    d2[y + z + w] %= mod
        d = d2
    
    ans = 0
    for word in d:
        ans += d[word]
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
R=range(5)
dp=[[[[0,0,0,0,0] for i in R] for j in R] for k in range(N+1)]
dp[0][0][0][0]=1

#0:dammy 1:A 2:G 3:C 4:T
for x in range(N):
    for d in R:
        for c in R:
            for b in R:
                for a in range(1,5):
                    #a:X+1文字目、b:X-1文字目、...
                    if (c==1 and b==2 and a==3):
                        continue
                    if (c==2 and b==1 and a==3):
                        continue
                    if (c==1 and b==3 and a==2):
                        continue
                    if (d==1 and b==2 and a==3):
                        continue
                    if (d==1 and c==2 and a==3):
                        continue
                    dp[x+1][c][b][a]+=dp[x][d][c][b]
                    dp[x+1][c][b][a]%=MOD

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

print(ans)

Submission status: Accepted

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

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

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

for 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==2 and m==3) or (k==2 and l==1 and m==3) or (k==1 and l==3 and m==2):
                        continue
                    if (j==1 and k==2 and m==3) or (j==1 and l==2 and m==3):
                        continue
                    dp[i+1][k][l][m]=(dp[i+1][k][l][m]+dp[i][j][k][l])%MOD
ans=0
for k in range(5):
    for l in range(5):
        for m in range(5):
            ans=(ans+dp[N][k][l][m])%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 'AGC' in ''.join(t):
            return False
    return True


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

    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'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
dp=[[[[0]*5 for _ in range(5)] for _ in range(5)]for _ in range(N+1)]
ans=0
dp[0][0][0][0]=1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if j==1 and k==2 and l==3:continue
                    if j==1 and k==3 and l==2:continue
                    if j==3 and k==1 and l==2:continue
                    if i==1 and j==3 and l==2:continue
                    if i==1 and k==3 and l==2:continue
                    dp[n+1][j][k][l]+=dp[n][i][j][k]
for j in range(1,5):
    for k in range(1,5):
        for l in range(1,5):
            ans+=dp[N][j][k][l]
print(ans%MOD)

Submission status: Accepted

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

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


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in '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())
dp = [[[[1] * 4 for i in range(4)] for j in range(4)] for k in range(n+1)]
dp[3][1][2][0] = 0
dp[3][1][0][2] = 0
dp[3][2][1][0] = 0
if n > 3:
    for i in range(4,n + 1):
        for j in range(4):
            for k in range(4):
                dp[i][3][j][k] = sum(dp[i-1][j][k])
                dp[i][0][j][k] = sum(dp[i-1][j][k])
                if j == 1 and k == 0:
                    dp[i][2][j][k] = 0
                else:
                    dp[i][2][j][k] = sum(dp[i - 1][j][k])
                if j == 0 and k == 2:
                    dp[i][1][j][k] = 0
                elif j == 2 and k == 0:
                    dp[i][1][j][k] = 0
                elif k == 2:
                    dp[i][1][j][2] = sum(dp[i - 1][j][k]) - dp[i - 1][j][2][0]
                elif j == 2:
                    dp[i][1][2][k] = sum(dp[i - 1][j][k]) - dp[i-1][2][k][0]
                else:
                    dp[i][1][j][k] = sum(dp[i - 1][j][k])
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n][i][j][k] % (10**9 + 7)
print(ans % (10**9 + 7))