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 pprint
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7

for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0

dp[0]["TTT"] = 1

for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M

ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dp={}
def f(i,last4):
    if i==n:
        return 1
    else:
        if (i,last4) in dp:
            return dp[(i,last4)]
        else:
            addA=f(i+1,last4[1:4]+'A')
            addT=f(i+1,last4[1:4]+'T')
            if not last4[2:4]=='AC':
                addG=f(i+1,last4[1:4]+'G')
            else:
                addG=0
            if not (last4[2:4]=='AG' or last4[2:4]=='GA' or last4[1:4]=='ATG' or last4[1:4]=='AGG' or last4[1:4]=='AGT'):
                addC=f(i+1,last4[1:4]+'C')
            else:
                addC=0
            answer=addA+addT+addG+addC
            dp[(i,last4)]=answer
            return answer
print(f(0,'SSSS')%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
ans = [61, 230, 865, 3247, 12185, 45719, 171531, 643550, 2414454, 9058467, 33985227, 127504505, 478366600, 794717734, 733354121, 261943303, 776803305, 580025381, 51688048, 44657419, 737209731, 604119499, 159693437, 858533109, 639056669, 549054109, 996291083, 531294469, 23314687, 783022045, 855462856, 649970414, 68697295, 409213624, 604356692, 88638656, 978442997, 534833116, 763737161, 785892908, 123883652, 639213333, 181836645, 998121103, 124885216, 501575626, 39816123, 113468411, 799008836, 775465589, 256852905, 664630886, 971550783, 751629411, 51018086, 702530485, 725438992, 696683714, 792638194, 221791721, 149602322, 414054379, 986519078, 981760191, 305799096, 515140586, 406959393, 975058685, 245601370, 324759692, 673385295, 191483611, 570246669, 427196161, 781042769, 569725155, 842176273, 25328739, 847501730, 206282374, 353770801, 323137024, 371653459, 940737264, 123820509, 915711339, 847205021, 252858375, 718889563, 866398347, 738390145, 133009077, 333099663, 170591295, 329869205, 616680192, 597534442, 388130742]
print(ans[n - 3])

Submission status: Accepted

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

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

    """
    AGCTをそれぞれ、
    0123と置き換えて考える
    
    条件は
    ・文字0~3のみで構成される
    ・012を含まない
    ・隣同士をswapしても012を含まない

    出ちゃダメなパターンを考えると、
    ・012
    ・102
    ・021
    ・0?12
    ・01?2

    条件を満たしている部分文字列Sに対して、
    ・S+0 をしたときは大丈夫
    ・S+1 をしたとき、最後が021になるとダメ
    ・S+2 をしたとき、最後が012, 102, 0?12, 01?2になるとダメ
    ・S+3 をしたときは大丈夫
    
    と考えると、部分文字列の最後の3文字を見ると条件を満たしているかを判定できる

    dp[i][c1][c2][c3] := 部分文字列の長さiのときで、部分文字列の最後の文字列がc1c2c3のときの、条件を満たす個数
    """

    dp = [[[[0 for _ in range(4)] for __ in range(4)] for ___ in range(4)] for ____ in range(N+1)]

    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                dp[0][c1][c2][c3] = 0
                dp[1][c1][c2][c3] = 0
                dp[2][c1][c2][c3] = 0
                dp[3][c1][c2][c3] = 1
    dp[3][0][2][1] = 0
    dp[3][0][1][2] = 0
    dp[3][1][0][2] = 0

    for i in range(3, N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    if dp[i][c1][c2][c3] == 0:
                        # 0のやつは、何を足しても0
                        dp[i+1][c1][c2][c3] = 0
                        continue

                    for a in range(4):
                        # aは次に足す文字(0~3)
                        if ((c2==0 and c3==2 and a==1) or
                            (c2==0 and c3==1 and a==2) or
                            (c2==1 and c3==0 and a==2) or
                            (c1==0 and c3==1 and a==2) or
                            (c1==0 and c2==1 and a==2)):
                            # 021, 012, 102, 0?12, 01?2 になるとダメ
                            dp[i+1][c2][c3][a] = 0
                            continue

                        # それ以外の場合
                        dp[i+1][c2][c3][a] += dp[i][c1][c2][c3]
                        dp[i+1][c2][c3][a] %= MOD
    
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]
                ans %= MOD
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

b = {i+j+k:1 for i in "AGCT" for j in "AGCT" for k in "AGCT" if i+j+k not in ("AGC", "ACG", "GAC")}
t = {}

def isOk(last4):
    if last4[1:] in ("AGC", "ACG", "GAC"):
        return False
    if last4[0] == 'A' and "G" in (last4[1], last4[2]) and last4[3] == "C":
        return False
    return True

for _ in range(N-3):
    t = {}
    for w, j in b.items():
        for a in "AGCT":
            x = w + a
            if isOk(x):
                if x[1:] not in t:
                    t[x[1:]] = j
                else:
                    t[x[1:]] += j
    b = t

a = 0
for i, j in b.items():
    a += j
print(a % mod)

Submission status: Accepted

Solution code:
N = int(input())
mod = 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 'ATCG':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:]+c)) % mod
    memo[cur][last3] = ret
    #print(memo, cur)
    return ret


print(dfs(0, 'TTT'))

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=np.int64)

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

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

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:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

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

mod = 10**9+7
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[n][i][j][k] == 0:
                    continue
                for now in range(4):
                    if now == 0 and i == 1 and j == 2:
                        continue
                    if now == 0 and i == 2 and j == 1:
                        continue
                    if now == 1 and i == 0 and j == 2:
                        continue
                    if now == 0 and j == 1 and k==2:
                        continue
                    if now == 0 and i == 1 and k==2:
                        continue
                    dp[n+1][now][i][j] += dp[n][i][j][k]
                    dp[n+1][now][i][j] %= mod

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

print(int(res))

Submission status: Accepted

Solution code:
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7
 
for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][c1 + c2 + c3] = 0
 
dp[0]["TTT"] = 1
 
for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M
 
ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
#?AGC,?ACG,A?GC,AG?C,?GAC

A, G, C, T = 0, 1, 2, 3
#[[[],[]],]
#dp[i][A][T][C] += dp[i - 1][][][]
dp = [[] for i in range(n + 1)]
for i in range(n + 1):
    for j in range(4):
        dp[i].append([])
for i in range(n + 1):
    for j in range(4):
        for k in range(4):
            dp[i][j].append([])
for i in range(n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k].append(0)
dp[0][T][T][T] = 1

for leng in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[leng][c1][c2][c3] == 0:
                    continue
                for x in range(4):
                    if x == C and c1 == G and c2 == A:
                        continue
                    if x == G and c1 == C and c2 == A:
                        continue
                    if x == C and c1 == G and c3 == A:
                        continue
                    if x == C and c2 == G and c3 == A:
                        continue
                    if x == C and c1 == A and c2 == G:
                        continue
                    dp[leng + 1][x][c1][c2] += dp[leng][c1][c2][c3]
                    dp[leng + 1][x][c1][c2] %= 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())
ng = ["agc", "aagc", "acgc", "aggc", "atgc", "agac", "agcc", "aggc", "agtc", "acg", "gac"]

x = {"a": 1, "g": 1, "c": 1, "t": 1}

for _ in range(1,N):
    y = dict()
    for let,num in x.items():
        for a in ["a", "c", "g", "t"]:
            if let[-3:] + a in ng or (let[-3:] + a)[-3:] in ng:
                continue
            else:
                if let[-3:] + a in y.keys():
                    y[let[-3:] + a] += num
                else:
                    y[let[-3:]+a] = num
    x = y

print(sum(x.values()) % (10**9+7))

Submission status: Accepted

Solution code:
def solve():
  n = int(input())
  mod = 10**9+7
  dp = [[[[0 for i in range(4)]for j in range(4)]for k in range(4)]for t in range(105)]
  dp[0][2][2][2] = 1
  
  for i in range(n):
    for c1 in range(4):
      for c2 in range(4):
        for c3 in range(4):
          for a4 in range(4):
            if [c2,c3,a4] == [0,1,2] or [c2,c3,a4] == [0,2,1] or [c2,c3,a4] == [1,0,2] or [c1,c2,a4] == [0,1,2] or [c1,c3,a4] == [0,1,2]:
              continue
            else:
              dp[i+1][c2][c3][a4] += dp[i][c1][c2][c3]
              dp[i+1][c2][c3][a4] %= mod
  ans = 0
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        ans += dp[n][c1][c2][c3]
        ans %= mod
  print(ans)
solve()

Submission status: Accepted

Solution code:
def resolve():
    # 入力
    N = int(input())

    # 次の文字列のいずれかが登場したら条件にあわない
    ng_list_3 = [
        'AGC',
        'GAC',
        'ACG'
    ]
    ng_list_4 = [
        #'AAGC',
        #'ACGC',
        'AGGC',
        'ATGC',
        #'AGAC',
        #'AGCC',
        #'AGGC',
        'AGTC'
    ]

    # 文字列の先頭から探索
    
    memo = dict()
    # 文字列sの後ろにn文字をつなげるパターンの個数
    def count(s, n):
        # Sが条件に当てはまるか
        if len(s) >= 4:
            l4 = s[-4:]
            if l4 in ng_list_4:
                return 0
        
        if len(s) >= 3:
            l3 = s[-3:]
            if l3 in ng_list_3:
                return 0

        # 短縮
        if len(s) >= 4 and (s[-4:], n) in memo:
            return memo[(s[-4:], n)]
        
        # 最後までいったら
        if n == 0:
            return 1
        
        x = [
            count(s + 'A', n - 1),
            count(s + 'C', n - 1),
            count(s + 'G', n - 1),
            count(s + 'T', n - 1),
        ]
        x = sum(x) % (10**9 + 7)

        if len(s) >= 4:
            memo[(s[-4:], n)] = x
        
        return x

    print(count('', N))
    
resolve()

Submission status: Accepted

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

dp={b:1 for b in "ACGT"}

for _ in range(N-1):
  dp_new={}
  for k in dp:
    for b in "ACGT":
      new=k[-3:]+b
      if new[-3:] in ("AGC","GAC","ACG") or new in ("AGGC","ATGC","ACGC","AGTC","AGGC"):
        continue
      else:
        dp_new.setdefault(new,0)
        dp_new[new]+=dp[k]
  dp=dp_new

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

Submission status: Accepted

Solution code:
def solve(string):
    n = int(string)
    dp = [[0] * 4 for _ in range(n)]
    dp[0] = [1] * 4
    for i in range(1, n):
        base = sum(dp[i - 1])
        for j in range(4):
            dp[i][j] = base
        # "AGC", "ACG", "GAC"
        if i >= 2:
            dp[i][1] -= dp[i - 2][0] + dp[i - 2][2]
            dp[i][2] -= dp[i - 2][0]
        # "AG{}C", "A{}GC"
        if i >= 3:
            dp[i][1] -= dp[i - 3][0] * 3
            dp[i][2] += dp[i - 3][2]

    return str(sum(dp[n - 1]) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())
MOD = 10**9 + 7
A = 'A'
T = 'T'
G = 'G'
C = 'C'
ATGC = [A, T, G, C]

dp = {i: {c1: {c2: {c3: 0 for c3 in ATGC} for c2 in ATGC} for c1 in ATGC} for i in range(N+1)}
dp[0][T][T][T] = 1

for i, c1, c2, c3 in product(range(N), ATGC, ATGC, ATGC):
    if dp[i][c1][c2][c3] == 0:
        continue
    for c in ATGC:
        if (c1, c2, c) == (A, G, C) or (c1, c3, c) == (A, G, C):
            continue
        elif (c2, c3, c) == (A, G, C) or (c2, c3, c) == (A, C, G) or (c2, c3, c) == (G, A, C):
            continue
        dp[i+1][c2][c3][c] += dp[i][c1][c2][c3]
        dp[i+1][c2][c3][c] %= MOD

ans = 0
for c1, c2, c3 in product(ATGC, ATGC, ATGC):
    ans += dp[N][c1][c2][c3]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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, l1, l2, l3 in product(range(N), range(4), range(4), range(4)):
    if dp[i][l1][l2][l3] == 0:
        continue

    for a in range(4):
        if (0, 1, 2) == (l2, l1, a):
            continue
        if (1, 0, 2) == (l2, l1, a):
            continue
        if (0, 2, 1) == (l2, l1, a):
            continue
        if (0, 1, 2) == (l3, l1, a):
            continue
        if (0, 1, 2) == (l3, l2, a):
            continue

        dp[i + 1][a][l1][l2] += dp[i][l1][l2][l3]
        dp[i + 1][a][l1][l2] %= mod

ans = 0
for l1, l2, l3 in product(range(4), range(4), range(4)):
    ans += dp[N][l1][l2][l3]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache


def check(s):
    bads = ["AGC", "ACG", "GAC"] + [b.format(_s) for b in ["AG{}C", "A{}GC"] for _s in "ACGT"]
    return not any(map(lambda x: x in s, bads))


def solve(string):
    n = int(string)

    @lru_cache(n * 4**3)
    def dfs(pos, last3):
        if pos == n:
            return 1
        ans = 0
        for _s in "ACGT":
            ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
        return ans % (10**9 + 7)

    return str(dfs(0, "TTT"))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from functools import lru_cache


def check(s):
    bads = ["AGC", "ACG", "GAC"] + ["AG{}C".format(_s) for _s in "ACGT"
                                   ] + ["A{}GC".format(_s) for _s in "ACGT"]
    return not any(map(lambda x: x in s, bads))


def solve(string):
    n = int(string)

    @lru_cache(n * 4**3)
    def dfs(pos, last3):
        if pos == n:
            return 1
        ans = 0
        for _s in "ACGT":
            ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
        return ans % (10**9 + 7)

    return str(dfs(0, "TTT"))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits


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


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


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

N = INT()

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

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

def swap_ok(last4):
	# print(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(current, last3):
	if last3 in dp[current]:
		return dp[current][last3]
	if current == N:
		return 1
	ret = 0
	for c in 'AGCT':
		if swap_ok(last3 + c):
			ret = (ret + dfs(current + 1, last3[1:] + c)) % MOD
	dp[current][last3] = ret
	return ret

print(dfs(0, 'ATC'))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n = int(input())
mod,x,y,ans = 10**9+7,{"TTT":1},dd(int),0
def f(s):
    if s[1:]=="AG" or s[1:]=="GA" or s[:2]=="AG" or (s[0]=="A" and s[2]=="G"): return True
    else: return False
def make(s):
    global y
    for i in "ATGC":
        if (s[1:]=="AC" and i=="G") or (f(s) and i=="C"): pass
        else: y[s[1:]+i] = (y[s[1:]+i]+x[s])%mod
for i in range(n):
    for j in x.keys(): make(j)
    x,y = y,dd(int)
for i in x.values(): ans = (ans+i)%mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

if N == 3:
	print(61)

else:
	chars = "ACGT"
	invalid = [c+"AGC" for c in chars] + [c+"GAC" for c in chars] + [c+"ACG" for c in chars] + ["A"+c+"GC" for c in chars] + ["AG"+c+"C" for c in chars] + ["AGC"+c for c in chars] + ["GAC"+c for c in chars] + ["ACG"+c for c in chars]

	now={}
	for w in chars:
		for x in chars:
			for y in chars:
				for z in chars:
					s=w+x+y+z
					if s not in invalid:
						now[s] = 1

	for _ in range(N-4):
		new={}
		for s in now.keys():
			for c in chars:
				ns=s[1:]+c
				if ns not in invalid:
					if ns not in new:
						new[ns] = 0
					new[ns] += now[s]
					new[ns] %= 10**9+7
		now=new

	print(sum(now.values()) % (10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

memoCou = {}

n = int(input())


def cou(n, s):
    if(memoCou.get((n, s)) != None):
        return memoCou.get((n, s))
    if(not ok(s)):
        return 0
    #print(n, s)
    if(n == 0):
        return 1
    memoCou.update({(n, s): cou(
        n-1, s[1:]+"A")+cou(n-1, s[1:]+"C")+cou(n-1, s[1:]+"G")+cou(n-1, s[1:]+"T")})
    return memoCou.get((n, s))


def ok(s):
    for i in range(4):
        t = list(s)
        if(i < 3):
            t[i], t[i+1] = t[i+1], t[i]
        if("".join(t).count("AGC") >= 1):
            return False
    return True


print(cou(n, "TTTT") % 1000000007)

Submission status: Accepted

Solution code:
n=int(input())
a=3
b=4
c=4
d=1
e=1
f=1
g=4
h=9
i=12
j=22
for x in range(3,n):
    anew=i
    bnew=c+d+e+h
    cnew=b+i
    dnew=c
    enew=g
    fnew=c
    gnew=b+i
    hnew=d+e+f+h+j
    inew=a+b+f+g+i+j
    jnew=a*2+d+e+f+(g+h+j)*2
    a=anew
    b=bnew
    c=cnew
    d=dnew
    e=enew
    f=fnew
    g=gnew
    h=hnew
    i=inew
    j=jnew
Sum=a+b+c+d+e+f+g+h+i+j
print(Sum%(10**9+7))

Submission status: Accepted

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

N = int(input())

dp = {b: 1 for b in "ACGT"}
for _ in range(N - 1):
    dp_new = {}
    for k in dp:
        for b in "ACGT":
            n = k[-3:] + b
            if n[-3:] in ("AGC", "ACG", "GAC") or n in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                if n in dp_new:
                    dp_new[n] += dp[k]
                else:
                    dp_new[n] = dp[k]
    dp = dp_new

print(sum(dp.values()) % (10 ** 9 + 7))

Submission status: Accepted

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

import itertools
comb = list(map(''.join, itertools.product("ACGT", repeat=4)))

N = int(input())

dp = {c: [0, 0] for c in comb}
dp["TTTT"] = [1, 0]

for _ in range(N):
    dp_new = {c: [0, 0] for c in comb}
    for k in dp:
        for b in "ACGT":
            if k[2:4] + b in ("AGC", "ACG", "GAC") or k[1:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                dp_new[k[1:4] + b][1] += dp[k][0] + dp[k][1]
            else:
                dp_new[k[1:4] + b][0] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
    dp = dp_new

mod = int(1e9) + 7
print((4 ** N - sum([dp[k][1] for k in dp])) % mod)

Submission status: Accepted

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

import itertools
comb = list(map(''.join, itertools.product("ACGT", repeat=4)))

mod = int(1e9) + 7

N = int(input())

dp = {c: [0, 0] for c in comb}
dp["TTTT"] = [1, 0]

for _ in range(N):
    dp_new = {c: [0, 0] for c in comb}
    for k in dp:
        for b in "ACGT":
            if k[2:4] + b in ("AGC", "ACG", "GAC") or k[1:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                dp_new[k[1:4] + b][1] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
            else:
                dp_new[k[1:4] + b][0] += dp[k][0]
                dp_new[k[1:4] + b][1] += dp[k][1]
    dp = dp_new


print((4 ** N - sum([dp[k][1] for k in dp])) % mod)

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10**9+7
memo = [{} for i in range(N+1)]
# Keyが直前の三文字、Valueが作れる文字列の数
# ↑これを文字列の今の長さごとにメモする
# memo[6]['TTT']には直前の三文字がTTTで、
# 6文字目以降の条件に合う文字列の総数が入ってる


# めも化再帰
def dfs(index,last3):
	if last3 in memo[index]:
		return memo[index][last3]
	if index == N:
		return 1
	c_next = 'AT'
	if last3[1:] != 'AC':
		c_next += 'G'
	if ('AG' in last3) == False:
		if  last3[1:] != 'GA':
			if last3[0]+last3[2] != 'AG':
				c_next += 'C'
	count = 0
	for c in c_next:
		count += dfs(index+1,last3[1:]+c)
		count %= MOD

	memo[index][last3] = count
	return count

print(dfs(0,'TTT'))

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:
N = int(input())
ng = ["agc", "aagc", "acgc", "aggc", "atgc", "agac", "agcc", "aggc", "agtc", "acg", "gac"]
c = 0

x = {"a": 1, "g": 1, "c": 1, "t": 1}
for _ in range(N - 1):
    y = {}
    for k, v in x.items():
        n = k[-3:]
        for s in ["a", "c", "g", "t"]:
            if n + s in ng or (n + s)[-3:] in ng:
                continue
            if n + s in y.keys():
                y[n + s] += v
            else:
                y[n + s] = v
    x = y

print(sum(x.values()) % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())

# badX[n] == 条件を満たさない長さnのACGT列のうち接尾辞がXであるものの個数
bad   = [0]
badA  = [0]
badG  = [0]
badAC = [0]

def nall(n):
    """長さnのACGT列の総数"""
    return 4 ** n if n >= 0 else 0

def good(n):
    """条件を満たす長さnのACGT列の個数"""
    return nall(n) - bad[n] if n >= 0 else 0
def goodG(n):
    """条件を満たす長さnのACGT列のうち接尾辞がGであるものの個数"""
    return nall(n - 1) - badG[n] if n >= 0 else 0
def goodAC(n):
    """条件を満たす長さnのACGT列のうち接尾辞がACであるものの個数"""
    return nall(n - 2) - badAC[n] if n >= 0 else 0

for n in range(1, N + 1):
    b  = bad [n - 1] * 4              # 前半(n-1)文字が条件を満たさない
    b += good(n - 3)                  # 末尾が AGC
    b += good(n - 3) - goodG (n - 3)  # 末尾が ACG
    b += good(n - 3) - goodAC(n - 3)  # 末尾が GAC
    b += good(n - 4) * 3              # 末尾が ATGC, AGGC, AGTC
    bad.append(b)
    bA   = bad [n - 1]  # 前半(n-1)文字が条件を満たさない (+ 末尾A)
    bG   = bad [n - 1]  # 前半(n-1)文字が条件を満たさない (+ 末尾G)
    bAC  = badA[n - 1]  # 前半(n-1)文字が条件を満たさず末尾がA (+ 末尾C)
    bG  += good(n - 3) - goodG (n - 3)  # 末尾がACG
    bAC += good(n - 3) - goodAC(n - 3)  # 末尾がGAC
    badA.append(bA)
    badG.append(bG)
    badAC.append(bAC)

print(good(N) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
a = "$ACGT"
mod = 10**9 + 7
N = int(input())
dp = [[[[0 for l in range(5)] for k in range(5)] for j in range(5)]
      for i in range(N + 1)]

dp[0][0][0][0] = 1
ans = 0
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 (m == 2):
                        if (j == 1) and (k == 3):
                            continue
                        if (j == 1) and (l == 3):
                            continue
                        if (k == 1) and (l == 3):
                            continue
                        if (k == 3) and (l == 1):
                            continue
                    elif (m == 3):
                        if (k == 1) and (l == 2):
                            continue

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

                    if i + 1 == N:
                        ans += dp[i][j][k][l]
                        ans %= mod

print(ans)