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:
import itertools

s=dict()
for i in itertools.product(["A","C","G","T"], repeat=3):
    s[i]=1
s[("A","G","C")]=0
s[("G","A","C")]=0
s[("A","C","G")]=0

n=int(input())

mod=10**9+7
nn=3
t=dict()
while nn<n:
    for i in itertools.product(["A","C","G","T"], repeat=3):
        t[i]=0
    nn+=1
    for ky in s.keys():
        if ky[0]=="G" and ky[1]=="C":
            t[("A",ky[0],ky[1])]=0
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="A" and ky[1]=="C":
            t[("A",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]=0
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="C" and ky[1]=="G":
            t[("A",ky[0],ky[1])]=0
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[0]=="G" and ky[2]=="C":
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        elif ky[1]=="G" and ky[2]=="C":
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
        else:
            t[("A",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("C",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("G",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
            t[("T",ky[0],ky[1])]+=s[(ky[0],ky[1],ky[2])]
    for ky in s.keys():
        s[ky]=t[ky]           

icnt=0
for i in s.values():
    icnt=(icnt+i)%mod
print(icnt)

Submission status: Accepted

Solution code:
n = int(input())

mod = 10**9 + 7

a = [0]*n
c = [0]*n
g = [0]*n
t = [0]*n

a[0] = c[0] = g[0] = t[0] = 1
a[1] = c[1] = g[1] = t[1] = 4
a[2], c[2], g[2], t[2] = 16, 14, 15, 16

for i in range(3, n):
    v = (a[i-1] + c[i-1] + g[i-1] + t[i-1]) % mod
    a[i] = v
    c[i] = (v - a[i-2] - g[i-2] - 3*a[i-3]) % mod
    g[i] = (v - a[i-2] + g[i-3]) % mod
    t[i] = v
print((a[n-1] + c[n-1] + g[n-1] + t[n-1]) % mod)

Submission status: Accepted

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N + 1)]
    dp[0].setdefault('TTT', 1)

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

    for i in range(1, N + 1):
        for last3, count in dp[i - 1].items():
            for c in 'AGCT':
                if check(last3 + c):
                    new_last3 = last3[1:] + c
                    dp[i].setdefault(last3[1:] + c, 0)
                    dp[i][new_last3] = (dp[i][new_last3] + count) % mod

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


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    mod = 10 ** 9 + 7
    memo = [{} for _ in range(N + 1)]

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

    def dfs(memo, digit, last3):
        # last3文字 + digit文字 で条件を満たす個数を再帰取得する
        if last3 in memo[digit]:
            return memo[digit][last3]  # 計算済みの場合はそれを使用
        if digit == 0:
            return 1  # +0文字なのであればパターンは1のみ
        re = 0
        for c in 'AGCT':
            if check(last3 + c):
                re = (re + dfs(memo, digit - 1, last3[1:] + c)) % mod
        memo[digit][last3] = re
        return re

    print(dfs(memo, N, 'TTT'))  # 最初の3文字は入れ替えてAGCになりうる4文字に干渉しないものにする


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D - We Like AGC
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
# dp[i][j][k][l] := i桁目 3文字前 ２文字前 1文字前
dp = [[[[0]*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 k == 0 and l == 1 and a == 2:
                        continue
                    if k == 1 and l == 0 and a == 2:
                        continue
                    if k == 0 and l == 2 and a == 1:
                        continue
                    if j == 0 and l == 1 and a == 2:
                        continue
                    if j == 0 and k == 1 and a == 2:
                        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:
n = int(input())
dp = [[0]*4 for i in range(n+1)]
mod = 10**9+7

dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 1
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = 4

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

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

Submission status: Accepted

Solution code:
def main():
    mod = 10**9 + 7
    n = int(input())

    # store last 3 characters
    # 'A':0, 'C':1, 'G':2, 'T':3
    dp = [[[0] * 4 for _ in range(4)] for _ in range(4)]
    dp[3][3][3] = 1
    for i in range(n):
        new_dp = [[[0] * 4 for _ in range(4)] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    num = dp[i][j][k]

                    # add all
                    for l in range(4):
                        new_dp[j][k][l] += num

                    # delete
                    # AG?C or ?AGC or A?GC or ?GAC
                    if (i == 0 and j == 2) or (j == 0 and k == 2) or (i == 0 and k == 2) or (j == 2 and k == 0):
                        new_dp[j][k][1] -= num
                    # ?ACG
                    if j == 0 and k == 1:
                        new_dp[j][k][2] -= num

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

        dp = new_dp

    for i in range(4):
        for j in range(4):
            dp[i][j] = sum(dp[i][j]) % mod
    for i in range(4):
        dp[i] = sum(dp[i]) % mod
    print(sum(dp) % mod)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import reduce

def main():
  m = 10 ** 9 + 7
  n = int(input())
  current = defaultdict(int)
  current['TTT'] = 1
  for i in range(n):
    wip = defaultdict(int)

    for c in 'AGCT':
      for k, v in current.items():
        if k + c in ['ATGC', 'AGTC', 'AGGC']:
          continue
        z = k[1:]+c
        if z in ['AGC', 'ACG', 'GAC']:
          continue
        wip[z] = (wip[z] + v) % m

    current = wip
  
  print(reduce(lambda acc, x: (acc + x) % m, wip.values()))

main()

Submission status: Accepted

Solution code:
def is_ok(s):
    if s[1:] in ['AGC', 'ACG', 'GAC']:
        return False
    if s[0] == 'A' and s[2:] == 'GC':
        return False
    if s[:2] == 'AG' and s[3] == 'C':
        return False
    return True


m = 1000000007

N = int(input())

d = {}
for i in 'ACGT':
    for j in 'ACGT':
        for k in 'ACGT':
            d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
    del d[k]

for i in range(N - 3):
    t = {}
    for k in d:
        for i in 'ACGT':
            s = k + i
            if is_ok(s):
                t.setdefault(s[1:], 0)
                t[s[1:]] += d[k]
                t[s[1:]] %= m
    d = t

print(sum(d.values()) % m)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
A = [1]+(N+3)*[0]
G = [1]+(N+3)*[0]
C = [1]+(N+3)*[0]

for n in range(1,N):
  T = (2*A[n-1]+G[n-1]+C[n-1])%mod
  A[n] = T
  G[n] = (T-A[n-2]+G[n-3])%mod
  C[n] = (T-A[n-2]-G[n-2]-3*A[n-3])%mod

print((2*A[N-1]+G[N-1]+C[N-1])%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
A=[1] + [0]*(n+3)
G=[1] + [0]*(n+3)
C=[1] + [0]*(n+3)
for i in range(1,n):
    t=(2*A[i-1]+G[i-1]+C[i-1])%mod
    A[i]=t
    G[i]=(t-A[i-2]+G[i-3])%mod
    C[i]=(t-A[i-2]-G[i-2]-3*A[i-3])%mod
print((2*A[n-1]+G[n-1]+C[n-1])%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
A=[1] + [0]*(n-1)
G=[1] + [0]*(n-1)
T=[1] + [0]*(n-1)
C=[1] + [0]*(n-1)
##NG:: AGC,GAC,ACG
AG =[0]*n
GA =[0]*n
AC =[0]*n
##NG:: AGGC,AGTC,ATGC
AGG=[0]*n
AGT=[0]*n
ATG=[0]*n
for i in range(1,n):
    tmp=A[i-1]+G[i-1]+C[i-1]+T[i-1]

    A[i]=tmp%mod
    T[i]=tmp%mod
    G[i]=(tmp - AC[i-1])%mod
    C[i]=(tmp -AG[i-1]-GA[i-1]-AGG[i-1] -AGT[i-1]-ATG[i-1])%mod

    AG[i]=A[i-1]
    GA[i]=G[i-1]
    AC[i]=(A[i-1]-GA[i-1])%mod

    AGG[i]=AG[i-1]
    AGT[i]=AG[i-1]
    ATG[i]=A[i-2]# == AT[i-1]


print((A[-1]+G[-1]+C[-1]+T[-1])%mod)
#print(A,G,C,T)
#print(AG,GA,AC)
#print(AGG,AGT,ATG)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
A = {}
B = {}
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":
            if a+b+c not in ["AGC", "ACG", "GAC"]:
                B[a+b+c] = 1
X=set()
for a in "ATGC":
    for b in "ATGC":
        for c in "ATGC":      
            for d in "ATGC":
                s=a+b+c+d
                t=b+a+c+d
                u=a+c+b+d
                v=a+b+d+c
                if any(["AGC" in x for x in [s,t,u,v]]):
                    X.add(s)

for _ in range(N-3):
    A = B
    B = defaultdict(int)
    for k in A:
        for l in "ATGC":
            if k+l not in X:
                B[k[1:]+l] += A[k]
    
print(sum(B.values())%(10**9+7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


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

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N):
    M = 10**9 + 7

    def gp(n):
        prohibit = []
        for c in product('AGCT', repeat=n):
            c = ''.join(c)
            if 'AGC' in c:
                prohibit.append(c)

            for i in range(n-1):
                j = i+1
                l = list(c)
                l[i], l[j] = l[j], l[i]
                if 'AGC' in ''.join(l):
                    prohibit.append(c)
        return set(prohibit)

    p3 = gp(3)
    p4 = gp(4)



    memo = {}
    for c in product('AGCT', repeat=3):
        c = ''.join(c)
        if c not in p3:
            memo[c] = 1

    for _ in range(N-3):
        nm = Counter()
        for c in 'AGCT':
            for k, v in memo.items():
                kk = k + c
                if kk not in p4:
                    nm[kk[1:]] += v
                    nm[kk[1:]] %= M

        memo = nm


    return sum(memo.values()) % M


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
# A→0,G→1,C→2,T→3
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i==0 and j==1 and k==2) or (i==0 and j==2 and k==1) or (i==2 and j==0 and k==1):
                pass
            else:
                dp[3][i][j][k] = 1

for a in range(3,n):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                # lは新しい桁
                for l in range(4):
                    if (j==0 and k==1):
                        if l==2:
                            continue
                    if (j==0 and k==2):
                        if l==1:
                            continue
                    if (j==2 and k==0):
                        if l==1:
                            continue

                    if (i==0 and k==2):
                        if l==1:
                            continue
                    if (i==0 and j==2):
                        if l==1:
                            continue
                    dp[a+1][j][k][l] += dp[a][i][j][k]
                    dp[a+1][j][k][l] %= 10**9+7
                    #print(i,j,k,l,dp[a+1][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]
            ans %= 10**9+7
print(ans)

Submission status: Accepted

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

# DP[n][a][b][c] := n-2文字目がa, n-1文字目がb, n文字目がcであるような長さnの文字列の数
DP = [[[[0 for _ in range(4)] for _ in range(4)]
       for _ in range(4)] for _ in range(N + 1)]

# T=0, A=1, G=2, C=3　とする

# DP初期化（3文字）
# AGC(123), GAC(213), ACG(132)を除外
for a in range(4):
    for b in range(4):
        for c in range(4):
            if (a, b, c) not in ((1, 2, 3), (2, 1, 3), (1, 3, 2)):
                DP[3][a][b][c] = 1

# 4~N文字の文字列について
# AGC(123), GAC(213), ACG(132)に加え、A*GC(1*23), AG*C(12*3)も除外
for i in range(4, N + 1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                # 末尾が T or A の場合は特に制限はない
                DP[i][b][c][0] += DP[i - 1][a][b][c]
                DP[i][b][c][1] += DP[i - 1][a][b][c]
                # 末尾が G の場合、ACGになってはならない
                if (b, c) != (1, 3):
                    DP[i][b][c][2] += DP[i - 1][a][b][c]
                # 末尾がCの場合、AGC, GAC, A*GC, AG*Cは不適
                if (b, c) != (1, 2) and (b, c) != (2, 1) and (a, c) != (1, 2) and (a, b) != (1, 2):
                    DP[i][b][c][3] += DP[i - 1][a][b][c]

ans = 0
# 末尾3文字（計64通り）の総和
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 % MOD)

Submission status: Accepted

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

# DP[n][a][b][c] n-2文字目がa, n-1文字目がb, n文字目がcであるような長さnの文字列の数
DP = [[[[0 for _ in range(4)] for _ in range(4)]
       for _ in range(4)] for _ in range(N + 1)]

# T=0, A=1, G=2, C=3　とする

# DP初期化（3文字）
# AGC(123), GAC(213), ACG(132)を除外
for a in range(4):
    for b in range(4):
        for c in range(4):
            if (a, b, c) not in ((1, 2, 3), (2, 1, 3), (1, 3, 2)):
                DP[3][a][b][c] = 1

# 4~N文字の文字列について
# AGC(123), GAC(213), ACG(132)に加え、A*GC(1*23), AG*C(12*3)も除外
for i in range(4, N + 1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                # 末尾が T or A の場合は特に制限はない
                DP[i][b][c][0] += DP[i - 1][a][b][c]
                DP[i][b][c][1] += DP[i - 1][a][b][c]
                # 末尾が G の場合、ACGになってはならない
                if (b, c) != (1, 3):
                    DP[i][b][c][2] += DP[i - 1][a][b][c]
                # 末尾がCの場合、AGC, GAC, A*GC, AG*Cは不適
                if (b, c) != (1, 2) and (b, c) != (2, 1) and (a, c) != (1, 2) and (a, b) != (1, 2):
                    DP[i][b][c][3] += DP[i - 1][a][b][c]

ans = 0
# 末尾3文字（計64通り）の総和
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 % MOD)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9+7

N = int(input())

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

def ok(last4):
    if "AGC" in last4 or "GAC" in last4 or "ACG" in last4 or last4 == "AGGC" or last4 == "ATGC" or last4 == "AGGC" or last4 == "AGTC":
        return False
    else:
        return True

def DFS(now,last3):
    if last3 in memo[now]:
        return memo[now][last3] 
    if now == N:
        return 1
    ret = 0
    for c in "AGCT":
        last4 = last3 + c
        if ok(last4):
            ret += DFS(now+1,last4[1:])
            ret %= MOD
    memo[now][last3] = ret
    return ret

print(DFS(0,"TTT"))

Submission status: Accepted

Solution code:
n = int(input())
mod = pow(10, 9) + 7
alph = list("AGCT")
ng1 = [list("AGC"), list("ACG"), list("GAC")]
dp = [0] * 64
for i in range(4):
    for j in range(4):
        for k in range(4):
            if not [alph[i], alph[j], alph[k]] in ng1:
                dp[16 * i + 4 * j + k] = 1
for _ in range(n - 3):
    dp0 = [0] * 64
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not [alph[j], alph[k], alph[l]] in ng1:
                        if not ([alph[i], alph[l]] == list("AC") and (alph[j] == "G" or alph[k] == "G")):
                            dp0[16 * j + 4 * k + l] += dp[16 * i + 4 * j + k]
                            dp0[16 * j + 4 * k + l] %= mod
    for i in range(64):
        dp[i] = dp0[i]
ans = sum(dp) % mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import itertools
L = [''.join(i) for i in itertools.product('0123', repeat=3)]
l = len(L)

mod = 10**9+7

AGC = '021'
ACG = '012'
GAC = '201'
nc3 = set([AGC, ACG, GAC])

AGGC = '0221'
AGTC = '0231'
ATGC = '0321'
nc4 = set([AGGC, AGTC, ATGC])

n = int(input())
dp = [[0]*l for _ in range(n+1)]
for i in L:
    if i in nc3: continue
    dp[3][int(i, 4)] = 1

for i in range(3, n):
    for jl in L:
        for k in "0123":
            nxt = jl[1:] + k
            if nxt in nc3: continue
            if jl+k in nc4: continue
            dp[i+1][int(nxt, 4)] += dp[i][int(jl, 4)]
print(sum(dp[n])%mod)

Submission status: Accepted

Solution code:
import itertools
L = [''.join(i) for i in itertools.product('0123', repeat=3)]
l = len(L)

mod = 10**9+7

AGC = '021'
ACG = '012'
GAC = '201'
nc3 = set([AGC, ACG, GAC])

AGGC = '0221'
AGTC = '0231'
ATGC = '0321'
nc4 = set([AGGC, AGTC, ATGC])

n = int(input())
dp = [[0]*l for _ in range(n+1)]
for i in L:
  if i in nc3: continue
  dp[3][int(i, 4)] = 1

for i in range(3, n):
  for jl in L:
    for k in "0123":
      nxt = jl[1:] + k
      if nxt in nc3: continue
      if jl+k in nc4: continue
      dp[i+1][int(nxt, 4)] += dp[i][int(jl, 4)]
print(sum(dp[n])%mod)

Submission status: Accepted

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

DP = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N)]
# DP[i][a][b][c] i-2からi文字目までがabcであるような文字列の数
Banned = {(1,2,3),(2,1,3),(1,3,2)}

for a in range(4):
  for b in range(4):
    for c in range(4):
      if (a,b,c) not in Banned:
        DP[2][a][b][c] = 1
      

for i in range(3,N):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        DP[i][b][c][0] += DP[i-1][a][b][c]
        DP[i][b][c][1] += DP[i-1][a][b][c]
        if not ((b,c) == (1,2) or (b,c) == (2,1) or (a,c) == (1,2) or (a,b) == (1,2)):
          DP[i][b][c][3] += DP[i-1][a][b][c]
        if not (b,c) == (1,3):
          DP[i][b][c][2] += DP[i-1][a][b][c]

ans = 0
for a in range(4):
  for b in range(4):
    for c in range(4):   
      ans += DP[N-1][a][b][c]
print(ans % MOD)
#print(DP[3])

Submission status: Accepted

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

options = ["A", "C", "G", "T"]
dp = [{options[i] + options[j] + options[k]: 0 for i in range(len(options)) for j in range(len(options)) for k in range(len(options))} for _ in range(N+1)]
keys = list(dp[0].keys())

dp[0]["TTT"] = 1

for i in range(N):
    for key in keys:
        for option in options:
            if key[1] == "A" and key[2] == "G" and option == "C":
                continue
            if key[0] == "A" and key[2] == "G" and option == "C":
                continue
            if key[1] == "G" and key[2] == "A" and option == "C":
                continue
            if key[1] == "A" and key[2] == "C" and option == "G":
                continue
            if key[0] == "A" and key[1] == "G" and option == "C":
                continue
            
            dp[i+1][key[1:3] + option] += dp[i][key]
            dp[i+1][key[1:3] + option] = dp[i+1][key[1:3] + option] % mod

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

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    dp = [1]*(4**3)
    dp[0*16+2*4+1] = 0
    dp[2*16+0*4+1] = 0
    dp[0*16+1*4+2] = 0
    for _ in range(n-3):
        ndp = [0]*(4**3)
        for i in range(4):
            ndp[0*16+2*4+1] -= dp[i*16+0*4+2]
            ndp[i*16+2*4+1] -= dp[0*16+i*4+2]
            ndp[2*16+i*4+1] -= dp[0*16+2*4+i]
        ndp[0*16+2*4+1] += dp[0*16+0*4+2]
        ndp[2*16+2*4+1] += dp[0*16+2*4+2]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for l in range(4):
                        ndp[i*16+j*4+k] += dp[l*16+i*4+j]
        # ndp[0*16+2*4+1] = 0
        ndp[2*16+0*4+1] = 0
        ndp[0*16+1*4+2] = 0
        for i in range(4**3):
            ndp[i] %= mod
        dp = ndp*1
#        print(dp)

    ans = 0
    for i in dp:
        ans += i
    print(ans%mod)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
DP=[[0]*256 for i in range(N+2)]
NO=[False]*256
S='AGCT'
T=0
for a in range(4):
  for b in range(4):
    for c in range(4):
      for d in range(4):
        T=list(S[a]+S[b]+S[c]+S[d])
        NO[a*64+b*16+c*4+d]=('AGC' in ''.join(T))
        for l in range(3):
          T[l],T[l+1]=T[l+1],T[l]
          NO[a*64+b*16+c*4+d]|=('AGC' in ''.join(T))
          T[l],T[l+1]=T[l+1],T[l]
DP[0][-1]=1
for i in range(N+1):
  for j in range(256):
    if NO[j]:
      DP[i][j]=0
      continue
    for k in range(4):
      DP[i+1][(j*4+k)&255]=(DP[i+1][(j*4+k)&255]+DP[i][j])%mod
P=0
for i in range(256):
  P+=DP[N][i]
print(P%mod)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n = getN()
    dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # Free(C/T), A, G, AG, AC, AT, GA, AGA, AGG, AGT, ATG, (OUT)
    #     0      1  2   3   4   5   6   7    8    9    10

    for i in range(n):
        tmp = [0] * 12

        tmp[3] = dp[1] + dp[6] + dp[7]
        tmp[4] = dp[1]
        tmp[5] = dp[1] + dp[6] + dp[7]
        tmp[6] = dp[2] + dp[8] + dp[10]
        tmp[7] = dp[3]
        tmp[8] = dp[3]
        tmp[9] = dp[3]
        tmp[10] = dp[5]
        tmp[11] = dp[3] + dp[4] + dp[6] + dp[7] + dp[8] + dp[9] + dp[10] + dp[11] * 4
        tmp[1] = dp[0] + dp[1] + dp[4] + dp[5] + dp[6] + dp[7] + dp[9]
        tmp[2] = dp[0] + dp[2] + dp[8] + dp[9] + dp[10]
        tmp[0] = dp[0] * 2 + dp[2] * 2 + dp[4] * 2 + dp[5] * 2 + dp[8] + dp[9] + dp[10]

        dp = [x % MOD for x in tmp]
    #     print(dp)
    # print(sum(dp)%MOD)
    # print(pow(4, n, MOD))
    print(sum(dp[:-1]) % MOD)

def gu(n=5):
    ban = ["AGC", "ACG", "GAC", "AGAC", "AGGC", "AGTC", "ATGC"]
    select = ["A", "G", "C", "T"]
    ans = 0
    space = [0] * 11
    sp = ["ATG", "AGT", "AGG", "AGA", "GA", "AT", "AC", "AG", "G", "A"]
    for i in range(4 ** n):
        lis = []
        for j in range(n):
            lis.append(select[i%4])
            i //= 4
        ji = "".join(lis)
        fl = True
        # print(ji)
        for b in ban:
            if b in ji:
                fl = False
        if fl:
            ans += 1
            en = False
            for dd, spp in enumerate(sp):
                if ji.endswith(spp):
                    space[dd] += 1
                    en = True
                    break
            if not en:
                space[-1] += 1

    space.reverse()

    print(space)
    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()
    # for i in range(1, 7):
    #     gu(i)

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros([N+1,4,4,4],dtype=int)
dp[0,-1,-1,-1] = 1

for i in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if not dp[i,c1,c2,c3]:continue
        for a in range(4):
          if c1 == 0 and c3 == 1 and a == 2:continue
          if c1 == 0 and c2 == 1 and a == 2:continue
          if c2 == 0 and c3 == 1 and a == 2:continue
          if c2 == 0 and c3 == 2 and a == 1:continue
          if c2 == 1 and c3 == 0 and a == 2:continue
          dp[i+1,c2,c3,a] += dp[i,c1,c2,c3]
          dp[i+1,c2,c3,a] %= mod

print(dp[-1].sum()%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
dp = [[0]*(4**3) for i in range(n)]
dic = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
agct_to_num = dict()
num_to_agct = dict()
for i in 'AGCT':
    for j in 'AGCT':
        for k in 'AGCT':
            num = dic[i]*16 + dic[j]*4 + dic[k]*1
            agct_to_num[i+j+k] = num
            num_to_agct[num] = i+j+k

dp[0] = [1] * (4**3)
dp[1] = [1] * (4**3)
dp[2] = [1] * (4**3)
dp[2][agct_to_num['AGC']] = 0
dp[2][agct_to_num['ACG']] = 0
dp[2][agct_to_num['GAC']] = 0


def is_ok(s):
    if 'AGC' in s:
        return False
    for i in range(len(s)-1):
        t = list(s)
        t[i], t[i+1] = t[i+1], t[i]
        if 'AGC' in ''.join(t):
            return False
    return True


for i in range(3, n):
    for j in range(64):
        for c in 'ACGT':
            tmp = num_to_agct[j] + c
            if is_ok(tmp):
                dp[i][agct_to_num[tmp[1:]]] += dp[i-1][j]

print(sum(dp[n-1]) % 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") > 0:
            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:
import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

# 文字を添え字に
def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

# 添え字を文字に
def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

# 部分文字列として含んではいけないものを正規表現で判定
def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

# 行列作成　各状態からの各遷移が有効か確かめる
A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1
A = np.array(A, dtype = "object")


# 行列の二分累乗
def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

# ベクトル作成　TTTのみ立てておく
x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)