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:
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):
    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 = 1e9 + 7

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

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

def sol(cur, s):
    if s in memo[cur]:
        return memo[cur][s]
    if cur == n:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(s + c):
            ret = int(ret + sol(cur + 1, s[1:] + c)) % MOD
    memo[cur][s] = int(ret)
    return int(ret)

print(sol(0, 'TTT'))

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(n: int):
    def is_valid(i, j, k, l):
        if ((j == 0 and k == 1 and l == 2) or
            (j == 0 and k == 2 and l == 1) or
            (j == 2 and k == 0 and l == 1) or
            (i == 0 and k == 2 and l == 1) or
            (i == 0 and j == 2 and l == 1)):
            return False
        return True
    dp = [[[1] * 4 for _ in range(4)] for _ in range(4)]
    dp[0][1][2] = 0
    dp[0][2][1] = 0
    dp[2][0][1] = 0
    for i in range(3, n):
        next_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):
                    for l in range(4):
                        if is_valid(i, j, k, l):
                            next_dp[j][k][l] += dp[i][j][k]
        dp = next_dp
    ret = sum([sum([sum(e) for e in d ]) for d in dp]) % MOD

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

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)]
P=10**9+7

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

for len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for a in range(4):
                    if j==0 and k==2 and a==1:continue
                    if j==0 and k==1 and a==2:continue
                    if j==2 and k==0 and a==1:continue
                    if i==0 and k==2 and a==1:continue
                    if i==0 and j==2 and a==1:continue
                    dp[len+1][j][k][a]+=dp[len][i][j][k]
                    dp[len+1][j][k][a]%=P

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
"""

import sys
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

# dp[i][j] := 全部でi文字の時、最後の3文字がjとなる文字列の数
dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]
# 3文字での初期値
for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1

keys = [''.join(key) for key in product('ACGT', repeat=4)]
for i in range(4, N+1):
    for key in keys:
        for j in range(4):
            tmp=list(key)
            if j>=1:
                # 隣同士をスワップさせる
                tmp[j],tmp[j-1]=tmp[j-1],tmp[j]
            if ''.join(tmp).count('AGC'):
                break
        else:
            # 4パターンいずれもAGCを含まないものだけ遷移させる
            cur,nxt=key[:3],key[1:]
            dp[i][nxt]=(dp[i][nxt]+dp[i-1][cur])%MOD
print((sum(dp[N].values()))%MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
・正規表現
"""

import sys, re
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

# NGパターン一覧
patterns = [
    # 任意の0か1文字
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    # 任意の1文字
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]

# dp[i][j] := 全部でi文字の時、最後の3文字がjとなる文字列の数
dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]
# 3文字での初期値
for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1

keys = [''.join(key) for key in product('ACGT', repeat=4)]
for i in range(4, N+1):
    for key in keys:
        # NGパターンのいずれにもマッチしないものだけ遷移させる
        if not any([ptn.match(key) for ptn in patterns]):
            cur,nxt=key[:3],key[1:]
            dp[i][nxt]=(dp[i][nxt]+dp[i-1][cur])%MOD
print((sum(dp[N].values()))%MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc122/editorial.pdf
・数え上げDP
・正規表現
"""

import sys, re
from itertools import product
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

# NGパターン一覧
patterns = [
    # 任意の0か1文字
    re.compile(r'^(.?)AGC(.?)$'),
    re.compile(r'^(.?)GAC(.?)$'),
    re.compile(r'^(.?)ACG(.?)$'),
    # 任意の1文字
    re.compile(r'^A.GC$'),
    re.compile(r'^AG.C$'),
]

# dp[i][j] := 全部でi文字の時、最後の3文字がjとなる文字列の数
dp=[Counter() for i in range(N+1)]
keys = [''.join(key) for key in product('ACGT', repeat=3)]
# 3文字での初期値
for key in keys:
    if key not in ['AGC', 'GAC', 'ACG']:
        dp[3][key]=1
    else:
        dp[3][key]=0

for i in range(4, N+1):
    for key in keys:
        for nxt in 'ACGT':
            # NGパターンのいずれにもマッチしないものだけ遷移させる
            if not any([ptn.match(key+nxt) for ptn in patterns]):
                dp[i][key[1:]+nxt]=(dp[i][key[1:]+nxt]+dp[i-1][key])%MOD
print((sum(dp[N].values()))%MOD)

Submission status: Accepted

Solution code:
#! /usr/bin/python 
# -*- coding: utf-8 -*- 
#===============================================================================
# Date created  : 2019-03-28T20:56:32+09:00
# Date modified : 2019-03-28T21:27:00+09:00
# Author        : awk
# Description   : unanswered
#===============================================================================

# dp[len][last3][last2][last1] :=  
#String -> *. + last3 + last2 + last1 を満たすような String の個数
# "ACGT" -> [0,1,2,3]
#NG:  AGC,ACG,GAC,AG?C,A?GC
#initialization
MOD = 10**9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] \
    for _ in range(101) ]
dp[0][3][3][3] = 1
for l in range(100):
    for last3 in range(4):
        for last2 in range(4):
            for last1 in range(4):
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1:
                        continue
                    if last2 == 0 and last1 == 1 and now == 2:
                        continue
                    if last2 == 2 and last1 == 0 and now == 1:
                        continue
                    if last3 == 0 and last2 == 2 and now == 1:
                        continue
                    if last3 == 0 and last1 == 2 and now == 1:
                        continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD
N = int(input())
ans = 0
for last3 in range(4):
    for last2 in range(4):
        for last1 in range(4):
            ans += dp[N][last3][last2][last1]
print(ans%MOD)

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):
    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:
class DP:

    def __init__(self, n):
        self.memo = [{} for _ in range(n+1)]
        self.end = n
        self.mod = 10 ** 9 + 7

    def dp(self, cur, last3):
    
        if last3 in self.memo[cur]:
            return self.memo[cur][last3]
        if cur == self.end:
            return 1
        
        ret = 0
        for c in 'ACTG':
            if self.is_ok(last3 + c):
                ret = (ret + self.dp(cur + 1, last3[1:] + c)) % self.mod

        self.memo[cur][last3] = ret
        return ret

    def is_ok(self, last4):
        
        for i in range(4):
            t = list(last4)
            if i < 3:
                t[i], t[i+1] = t[i+1], t[i]
            if ''.join(t).count('AGC') > 0:
                return False
        return True


def main():

    n = int(input())
    solver = DP(n)

    print(solver.dp(0, 'CCC'))


main()

Submission status: Accepted

Solution code:
n = int(input())
mod = int(1e9+7)
dp = [[0 for i in range(4)]for k in range(n+1)] #ACGTの順
for i in range(4):
    dp[1][i] = 1
    dp[2][i] = 4
dp[3][0] = 16
dp[3][1] = 14
dp[3][2] = 15
dp[3][3] = 16
for i in range(4,n+1):
    for k in range(4):
        dp[i][k] = sum(dp[i-1])%mod
    dp[i][1] = dp[i][1] - (dp[i-2][0] + dp[i-2][2]) - dp[i-3][0]*3
    dp[i][2] = dp[i][2] - dp[i-2][0] + dp[i-3][2]
print(sum(dp[n])%mod)

Submission status: Accepted

Solution code:
n = int(input())

m = 10**9 + 7

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

# A,C,G,T の順


for i in range(4):
    for j in range(4):
        for k in range(4):
            A[3][i][j][k] = 1

A[3][0][2][1] = 0
A[3][0][1][2] = 0
A[3][2][0][1] = 0

for i in range(4, n+1):
    

    for j in range(4):
        for k in range(4):
            for p in range(4):
                for q in range(4):
                    A[i][j][k][p] += A[i-1][q][j][k]
                    A[i][j][k][p] %= m


    for j in range(4) :
        hiku0 = A[i-1][0][j][2]
        A[i][j][2][1] -= hiku0
        hiku1 = A[i-1][0][2][j]
        A[i][2][j][1] -= hiku1

    A[i][2][2][1] += A[i-1][0][2][2]
    
    A[i][0][2][1] = 0
    A[i][0][1][2] = 0
    A[i][2][0][1] = 0
        

ans = 0
for j in range(4):
    for k in range(4):
        ans += sum(A[n][j][k]) % m
print(ans % m)

#print(A)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    d = collections.defaultdict(int)
    d[''] = 1
    t = [
            'AGC',
            'ACG',
            'GAC',
            'AGAC',
            'AGCC',
            'AGTC',
            'ACGC',
            'AGGC',
            'ATGC'
        ]
    for i in range(n):
        e = collections.defaultdict(int)
        for c,v in d.items():
            v %= mod
            for g in 'ACGT':
                if c + g in t or (c + g)[-3:] in t:
                    continue
                e[(c + g)[-3:]] += v
        d = e

    return sum(d.values()) % mod


print(main())

Submission status: Accepted

Solution code:
n = int(input())

m = int(1e9 + 7)
s = "AGCT"
ng = ["AGC", "ACG", "GAC"]
dp = [[0 for _ in range(64)] for _ in range(2)]
for j in range(64):
    t = s[j // 16] + s[(j // 4) % 4] + s[j % 4]
    if t not in ng:
        dp[1][j] = 1
for i in range(4, n + 1):
    for j in range(64):
        dp[i % 2][j] = 0
    for j in range(64):
        for k in range(4):
            t = s[j // 16] + s[(j // 4) % 4] + s[j % 4] + s[k]
            if t[1:] not in ng and t[0] + t[2:] != ng[0] and t[:2] + t[3] != ng[0]:
                dp[i % 2][4 * (j % 16) + k] += dp[1 - i % 2][j]
                dp[i % 2][4 * (j % 16) + k] %= m
ans = sum(dp[n % 2]) % m
print(ans)

Submission status: Accepted

Solution code:
MAX_NUM = 10 ** 9 + 7

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

def ok(last4):
  if 'AGC' in last4 or \
  'GAC' in last4 or \
  'ACG' in last4 or \
  last4[0] == 'A' and last4[2:] == 'GC' or \
  last4[:2] == 'AG' and last4[-1] == 'C':
    return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res += dfs(cur + 1, last4[1:])
      res %= MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Submission status: Accepted

Solution code:
MAX_NUM = 10 ** 9 + 7

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

def ok(last4):
  if 'AGC' in last4 or \
  'GAC' in last4 or \
  'ACG' in last4 or \
  last4[0] == 'A' and last4[2:] == 'GC' or \
  last4[:2] == 'AG' and last4[-1] == 'C':
    return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res = (res + dfs(cur + 1, last4[1:])) % MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Submission status: Accepted

Solution code:
MAX_NUM = 10 ** 9 + 7

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

# def ok(last4):
#   if 'AGC' in last4 or \
#   'GAC' in last4 or \
#   'ACG' in last4 or \
#   last4[0] == 'A' and last4[2:] == 'GC' or \
#   last4[:2] == 'AG' and last4[-1] == 'C':
#     return False
#   return True

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 dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res = (res + dfs(cur + 1, last4[1:])) % MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')

Submission status: Accepted

Solution code:
dame=['AAGC', 'AACG', 'AGAC', 'AGAC', 'AGGC',
      'AGGC', 'AGTC', 'ATGC', 'GAGC', 'GGAC',
      'CAGC', 'CACG', 'CGAC', 'TAGC', 'TACG', 'TGAC']
memo={"TTT":1}

n=int(input())
for i in range(n):
    nmemo={}
    for c in ["A","G","C","T"]:
        for mk,mv in memo.items():
            nk=mk+c
            if nk not in dame:
                nk=nk[1:]
                if nk in nmemo:
                    nmemo[nk]+=mv
                else:
                    nmemo[nk]=mv
    memo=nmemo
print(sum(memo.values())%(10**9+7))

Submission status: Accepted

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


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


DP = [{} for i in range(N+1)]
for i in range(0, N+1):
    # 1-origin
    if i == 0:
        DP[i]['TTT'] = 1
    else:
        for c in 'AGCT':
            for last3, count in DP[i-1].items():
                if ok(last3+c):
                    ret = count % MOD
                    if last3[1:]+c in DP[i]:
                        DP[i][last3[1:]+c] += ret
                    else:
                        DP[i][last3[1:]+c] = ret
print(sum(DP[i].values()) % MOD)

Submission status: Accepted

Solution code:
#encoding: utf-8

n, mod = int(input()), 10 ** 9 + 7


memo = [{} for i in range(n + 1)]

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

def dfs(cnt, last):
    if last in memo[cnt]:
        return memo[cnt][last]
    if cnt == n:
        return 1
    ret = 0
    for c in "ACGT":
        if check(last + c):
            ret = (ret + dfs(cnt + 1, last[1:] + c)) % (10 ** 9 + 7)
    memo[cnt][last] = ret 
    return ret 

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*input());print g%(10**9+7)

Submission status: Accepted

Solution code:
from collections import defaultdict
import re
from itertools import product

atcg = ['A', 'T', 'C', 'G']
num = int(input())

def validate(tpl):
    string = tpl[0] + tpl[1] + tpl[2] + tpl[3]
    for pat in [r'A.GC', r'AG.C', 'ACG', 'AGC', 'GAC']:
         if re.search(pat, string):
                return False
    return True

def transition(dic):
    new_dic = defaultdict(int)
    for k, v in dic.items():
        for c in atcg:
            tpl = k[1], k[2], k[3], c
            if validate(tpl):
                new_dic[tpl] += v
    return new_dic

it = product(atcg, atcg, atcg, atcg)
dic = {}
for s in it:
    if validate(s):
        dic[s] = 1

if num == 3:
    print(61)
elif num == 4:
    print(230)
else:
    for n in range(num - 4):
        dic = transition(dic)
    print(sum(dic.values()) % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())
memo = [{} for _ in range(N+1)]
def isOk(last4):
  for i in range(4):
    t = list(last4)
    if i < 3:
      t[i],t[i+1] = t[i+1],t[i]
    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 isOk(last3+c):
      ret = (dfs(cur+1,last3[1:]+c)+ret)%(10**9+7)
  memo[cur][last3] = ret
  return ret

print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
N = int(input())

DENOM = 10 ** 9 + 7

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

BASE = "ACGT"
AGC = "AGC"


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


def dfs(cur, last3):
  ret = 0
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == N:
    return 1
  for c in BASE:
    if check(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % DENOM

  memo[cur][last3] = ret
  return ret

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N = int(input())

STT = [
    [1,0,2,0],[1,3,4,5],[6,0,2,0],[1,0,10,0],[6,10,7,8],
    [1,0,9,0],[1,10,4,5],[6,10,2,0],[1,10,2,0],[6,10,2,0]
]

dp = [[0]*(11) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for st in range(10):
        for ch in range(4):
            dp[i+1][STT[st][ch]] += dp[i][st]
            dp[i+1][STT[st][ch]] %= MOD

print(sum(dp[-1][:-1]) % MOD)

Submission status: Accepted

Solution code:
N = int(input())

mod = 10 ** 9 + 7

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

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

for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= mod

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

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
dp = [[[[0 for k in range(4)] for j in range(4)] for i in range(4)] for length in range(N+1)]
dp[0][3][3][3] = 1
#文字列の長さ
for length in range(N):
    #後ろから1文字目
    for c1 in range(4):
        #後ろから2文字目
        for c2 in range(4):
            #後ろから3文字目
            for c3 in range(4):
                if dp[length][c1][c2][c3]==0:
                    continue
                #追加する文字
                for a in range(4):
                    #ダメな条件
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    elif a == 2 and c1 == 0 and c2 ==1:
                        continue
                    elif a == 1 and c1 == 2 and c2 ==0:
                        continue
                    elif a == 2 and c1 == 1 and c3 == 0:
                        continue
                    elif a == 2 and c2 == 1 and c3 == 0:
                        continue
                    else:
                        dp[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                        dp[length][c2][c3][a] %= mod
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%mod)

Submission status: Accepted

Solution code:
from functools import lru_cache
from itertools import product

# 入力
N = int(input())

# 3文字のACGT文字列のリスト
T = [''.join(t) for t in product(('A', 'C', 'G', 'T'), repeat=3)]


# ACGT文字列が問題の条件にマッチするならば真となる述語
@lru_cache(maxsize=None)
def p(s):
    return all(
        'AGC' not in s[:i] + s[i + 1:i + 2] + s[i] + s[i + 2:]
        for i in range(len(s))
    )


# 長さがi、かつ、末尾3文字がs、かつ、問題の条件にマッチする文字列の個数を返す
@lru_cache(maxsize=None)
def f(i, s):
    return (
        0 if i == 3 and not p(s) else
        1 if i == 3 and p(s) else
        sum(f(i - 1, t) for t in T if t[1:] == s[:2] and p(t + s[-1]))
    )


# 解は、すべての長さ3のACGT文字列tに対して、f(N, t) の和である。
ans = sum(f(N, t) for t in T) % (10**9 + 7)

# 出力
print(ans)

Submission status: Accepted

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*int(input()));print(g%(10**9+7))

Submission status: Accepted

Solution code:
mod = 10**9 + 7

N = int(input())

# NG = {AGC,GAC,ACG,ATGC,AGGC,AGTC}
# (A,C,G,T) = (0,1,2,3)
# dp[i][j]: 長さiの条件を満たす文字列のうち、末尾がjとなるものの場合の数
# 初期条件:dp[1] = [1,1,1,1]
# 答え: dp[N][0] + dp[N][1] + dp[N][2] + dp[N][3]

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

# A,C,G,T それぞれ1通りずつ
dp[1] = [1]*4


for i in range(2,N+1):
    for j in range(4):
        # ひとまず長さi-1の文字列にjを足して良いとする　
        dp[i][j] += sum(dp[i-1])
        dp[i][j] %= mod
    # ダメなパターンを引いて補正する
    # 後ろ二文字が"AG","GA"の場合はCを付け足せない
    # ~AG, ~GA となる場合の数はそれぞれ dp[i-2][0]*1とdp[i-2][2]*1
    dp[i][1] -= dp[i-2][0] + dp[i-2][2]
     # 後ろ二文字が"AC"の場合はGを付け足せない
    # ~AC となる場合の数は dp[i-2][0] (- dp[i-3][2])
    dp[i][2] -= dp[i-2][0]
    if i >= 3:
        # 後ろ三文字が"ATG","AGG","AGT"となる場合はCを付け足せない
        # ~ATG, ~AGG, ~AGT となる場合の数は 合わせて dp[i-3][0]*3
        dp[i][1] -= dp[i-3][0]*3
        # ----------------------注意--------------------------
        # dp[i-2][0]は後ろから~ACとなる場合の数だから
        # これには~GACとなる場合の数も含まれている
        # しかし~GACというのは既に除外しているので
        # ~ACとなる場合の数は dp[i-2][0]-dp[i-3][2]
        # 余分に引いている分を+dp[i-3][2]することで補正
        dp[i][2] += dp[i-3][2]

ans = sum(dp[N]) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

N = int(input())

# NG = {AGC,GAC,ACG,ATGC,AGGC,AGTC}
# (A,C,G,T) = (0,1,2,3)
# dp[i][j]: 長さiの条件を満たす文字列のうち、末尾がjとなるものの場合の数
# 初期条件 dp[1] = [1,1,1,1]
# ans = dp[0] + dp[1] + dp[2] + dp[3]

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

# A,C,G,T それぞれ1通りずつ
dp[1] = [1]*4


for i in range(2,N+1):
    for j in range(4):
        # ひとまず長さi-1の文字列にjを足して良いとする
        dp[i][j] += sum(dp[i-1])
        dp[i][j] %= mod
    # ダメなパターンを引いて補正する
    # 後ろ二文字が"AG","GA"の場合はCを付け足せない
    # ~AG, ~GA となる場合の数はそれぞれ dp[i-2][0]*1とdp[i-2][2]*1
    dp[i][1] -= dp[i-2][0] + dp[i-2][2]
     # 後ろ二文字が"AC"の場合はGを付け足せない
    # ~AC となる場合の数は dp[i-2][0] (- dp[i-3][2])
    dp[i][2] -= dp[i-2][0]
    if i >= 3:
        # 後ろ三文字が"ATG","AGG","AGT"となる場合はCを付け足せない
        # ~ATG, ~AGG, ~AGT となる場合の数は 合わせて dp[i-3][0]*3
        dp[i][1] -= dp[i-3][0]*3
        # ----------------------注意--------------------------
        # dp[i-2][0]は後ろから~ACとなる場合の数だから
        # これには~GACとなる場合の数も含まれている
        # しかし~GACというのは既に除外しているので
        # ~ACとなる場合の数は dp[i-2][0]-dp[i-3][2]
        # 余分に引いている分を+dp[i-3][2]することで補正
        dp[i][2] += dp[i-3][2]

ans = sum(dp[N]) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

N = int(input())

# NG = {AGC,GAC,ACG,ATGC,AGGC,AGTC}
# (A,C,G,T) = (0,1,2,3)
# dp[i][j]: 長さiの条件を満たす文字列のうち、末尾がjとなるものの場合の数
# 初期条件 dp[1] = [1,1,1,1]
# ans = dp[0] + dp[1] + dp[2] + dp[3]

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

# A,C,G,T それぞれ1通りずつ
dp[1] = [1]*4


for i in range(2,N+1):
    for j in range(4):
        # ひとまず長さi-1の文字列にjを足して良いとする
        dp[i][j] += sum(dp[i-1])
        dp[i][j] %= mod
    # ダメなパターンを引いて補正する
    if i >= 2:
        # 後ろ二文字が"AG","GA"の場合はCを付け足せない
        # ~AG, ~GA となる場合の数はそれぞれ dp[i-2][0]*1とdp[i-2][2]*1
        dp[i][1] -= dp[i-2][0] + dp[i-2][2]
        # 後ろ二文字が"AC"の場合はGを付け足せない
        # ~AC となる場合の数は dp[i-2][0] (- dp[i-3][2])
        dp[i][2] -= dp[i-2][0]
    if i >= 3:
        # 後ろ三文字が"ATG","AGG","AGT"となる場合はCを付け足せない
        # ~ATG, ~AGG, ~AGT となる場合の数は 合わせて dp[i-3][0]*3
        dp[i][1] -= dp[i-3][0]*3
        # ----------------------注意--------------------------
        # dp[i-2][0]は後ろから~ACとなる場合の数だから
        # これには~GACとなる場合の数も含まれている
        # しかし~GACというのは既に除外しているので
        # ~ACとなる場合の数は dp[i-2][0]-dp[i-3][2]
        # 余分に引いている分を+dp[i-3][2]することで補正
        dp[i][2] += dp[i-3][2]

ans = sum(dp[N]) % mod
print(ans)

Submission status: Accepted

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,(g*4-b-c-d-a*3)%(10**9+7);'*int(input()));print(g)

Submission status: Accepted

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,(g*4-(b+c+d+a*3))%(10**9+7);'*int(input()));print(g)

Submission status: Accepted

Solution code:
a,b,c,d,e,f,g=[0]*6+[1]
for i in [0]*int(input()):d,c,e,f,a,b,g=c,a,a-f,b,g,g-e,(g*4-(c+e+f+d*3))%(10**9+7)
print(g)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

N = int(input())

dp = [[0]*4 for _ in range(N+1)]
dp[1] = [1]*4
for i in range(1,N+1):
    for j in range(4):
        dp[i][j] += sum(dp[i-1])
        dp[i][j] %= mod
    # AGC GAC ACG 
    if i >= 2:
        dp[i][1] -= dp[i-2][0] + dp[i-2][2]
        dp[i][2] -= dp[i-2][0]
    # A?GC AG?C (AGGC)
    if i >= 3:
        dp[i][1] -= dp[i-3][0]*3
        dp[i][2] += dp[i-3][2]

ans = sum(dp[N]) % mod
print(ans)

Submission status: Accepted

Solution code:
a,g,a_,a__,ac,ga,al=[0]*6+[1]
for i in range(int(input())):
    a__,a_,ac,ga,a,g,al=a_,a,a-ga,g,al,al-ac,(al*4-(a_+ac+ga+a__*3))%(pow(10,9)+7)
print(al)

Submission status: Accepted

Solution code:
N = int(input())

t=[1,4,16]
a=[0,1,4]
g=[0,1,4]
c=[0,0,1]
 
for i in range(3, N + 1):
    #print(i)
    t.append(t[i-1]*4 - a[i-2] - c[i-1] - g[i-2] - a[i-3]*3)
    a.append(t[i-1])
    g.append(t[i-1] - c[i-1])
    c.append(t[i-2] - g[i-2])
#print(t,a,g,c)
print(t[N] % (10**9 + 7))

Submission status: Accepted

Solution code:
import itertools
import functools
L = "ATGC"
MOD = 10 ** 9 + 7
@functools.lru_cache(maxsize = None)
def rec(s, k):
    if s.count("AGC"):
        return 0
    for i in range(3):
        t = list(s)
        t[i], t[i + 1] = t[i + 1], t[i]
        if ''.join(t).count("AGC"):
            return 0
    if k == 0:
        return 1
    ret = 0
    for x in L:
        ret = (ret + rec(x + s[:3], k - 1)) % MOD
    return ret

N = int(input())
if N == 3:
    print(61)
else:
    ret = 0
    for s in itertools.product(L, repeat = 4):
        ret = (ret + rec(''.join(s), N - 4)) % MOD
    print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections

def main():
	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 length in range(N):
		for c3 in range(4):
			for c2 in range(4):
				for c1 in range(4):
					if DP[length][c3][c2][c1] == 0:
						continue
					for a in range(4):
						if c2 == 0 and c1 == 1 and a == 2:
							continue
						if c2 == 0 and c1 == 2 and a == 1:
							continue
						if c2 == 1 and c1 == 0 and a == 2:
							continue
						if c3 == 0 and c1 == 1 and a == 2:
							continue
						if c3 == 0 and c2 == 1 and a == 2:
							continue
						DP[length+1][c2][c1][a] = (DP[length+1][c2][c1][a] + DP[length][c3][c2][c1]) % 1000000007
	
	ans = 0
	for c3 in range(4):
		for c2 in range(4):
			for c1 in range(4):
				ans = (ans + DP[N][c3][c2][c1]) % 1000000007
	print(ans)
			
if __name__ == "__main__":
	main()