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:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr  1 18:53:11 2019

@author: Yamazaki Kenichi
"""

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]
#        print(t)
        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':
#        print(last3 + c)
#        print(ok(last3 + c))
        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, M = int(input()), pow(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)) % M
  memo[cur][last3] = ret
  return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random

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

def check(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]

        if "".join(t).count("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 check(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())
N += 1
dp = []
for l in range(N):
  L = []
  for i in range(4):
    I = []
    for j in range(4):
      J = [0,0,0,0]
      I.append(J)
    L.append(I)
  dp.append(L)
dp[0][0][0][0] = 1
NGLIST_JKL = [[1,0,2],[1,1,2],[1,2,2],[1,3,2],[1,2,0],[1,2,1],[1,2,2],[1,2,3]]
NGLIST_KLM = [[1,2,3],[2,1,3],[1,3,2]]
for i in range(N-1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        if not [j,k,l] in NGLIST_JKL:
          for m in range(4):
            if not [k,l,m] in NGLIST_KLM:
              dp[i+1][k][l][m] += dp[i][j][k][l]
              dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
        else:
          if j == 1 and l == 2:
            for m in range(4):
              if m != 3:
                dp[i+1][k][l][m] += dp[i][j][k][l]
                dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
          elif j == 1 and k == 2:
            for m in range(4):
              if m != 3:
                dp[i+1][k][l][m] += dp[i][j][k][l]
                dp[i+1][k][l][m] = dp[i+1][k][l][m]%(10**9+7)
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += dp[N-1][i][j][k]%(10**9+7)
print(ans%(10**9+7))

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 ['A', 'C', 'G', 'T']:
        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

def is_valid(i, j, k, new):
    if (j, k, new) == (0, 1, 2) or (j, k, new) == (0, 2, 1) or (j, k, new) == (2, 0, 1):
        return False
    elif (i, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1):
        return False
    elif (i, j, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1) or (i, j, k, new) == (0, 2, 1):
        return False
    else:
        return True

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
dp[0][3][3][3] = 1
for n in range(1, N + 1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for new in range(4):
                    if is_valid(i, j, k, new):
                        dp[n][j][k][new] += dp[n - 1][i][j][k]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)

Submission status: Accepted

Solution code:
def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def ng(char1, char2, char3, new_char):
    if char2 == 0 and char3 == 1 and new_char == 2:
        return True
    if char2 == 0 and char3 == 2 and new_char == 1:
        return True
    if char2 == 1 and char3 == 0 and new_char == 2:
        return True
    if char1 == 0 and char2 == 1 and new_char == 2:
        return True
    if char1 == 0 and char3 == 1 and new_char == 2:
        return True
    return False


AGCT = ["A", "G", "C", "T"]
# ng=[[0,1,2],[0,2,1],[1,0,2],[0,1,?,2],[0,?,1,2]]


def main():
    modulo = 10**9+7
    N = int(input())
    dp = dp_table(N+1, 4, 4, 4)
    dp[0][3][3][3] = 1
    for i in range(N):
        for char_1 in range(4):
            for char_2 in range(4):
                for char_3 in range(4):
                    if dp[i][char_1][char_2][char_3] == 0:
                        continue
                    # (...char1,char2,char3)のあとにnewをつけた文字列が追加できるなら、
                    # (...char1,char2,char3)のバリエーション分だけ(バリエーションがある
                    for new in range(4):
                        if ng(char_1, char_2, char_3, new):
                            continue
                        else:
                            dp[i + 1][char_2][char_3][new] += dp[i][char_1][char_2][char_3]
                    dp[i + 1][char_2][char_3][new] %= modulo
    ans = 0
    for char_1 in range(4):
        for char_2 in range(4):
            for char_3 in range(4):
                ans += dp[N][char_1][char_2][char_3]
    # print(dp)
    print(ans % modulo)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
from itertools import product

N = int(input())
T = [''.join(t) for t in product(('A','C','G','T'),repeat = 3)]

def acg(s):
    return any(['ACG' in s[:i] + s[i+1:i+2] + s[i] + s[i+2:] for i in range(len(s))])

@lru_cache(maxsize=None)
def f(N,s):
    if N == 3 and acg(s):
        return 0
    elif N == 3 and not acg(s):
        return 1
    else: 
        return sum(f(N-1, c + s[:2]) for c in ('A','C','G','T') if not acg(c + s))

ans = sum(f(N,s) for s in T)
print(ans % 1000000007)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
A, G, C, T = 0, 1, 2, 3
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i == A and j == G and k == C)\
            or (i == A and j == C and k == G)\
            or (i == G and j == A and k == C):
                continue
            else:
                dp[3][i][j][k] += 1

for i in range(3, n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if (k == A and l == G and m == C)\
                    or (k == G and l == A and m == C)\
                    or (k == A and l == C and m == G)\
                    or (j == A and l == G and m == C)\
                    or (j == A and k == G and m == C):
                        continue
                    else:
                        dp[i+1][k][l][m] += dp[i][j][k][l]%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
from collections import defaultdict
dp = defaultdict(lambda:defaultdict(lambda:0))
def possible(last4):
    if 'AGC' in last4:
        return False
    for i in range(3):
        s = list(last4)
        s[i],s[i+1] = s[i+1],s[i]
        if 'AGC' in ''.join(s):
            return False
    return True
S = []
for s1 in 'AGCT':
    for s2 in 'AGCT':
        for s3 in 'AGCT':
            s = s1+s2+s3
            S.append(s)
for s in S:
    if s not in ['AGC','GAC','ACG']:
        dp[3][s] = 1

for n in range(3,N+3):
    for last in 'AGCT':
        for last3 in S:
            last4 = last3+last
            if possible(last4):
                dp[n+1][last4[1:]] += dp[n][last3]
                dp[n+1][last4[1:]] %= mod
print(dp[N+3]['TTT'])

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
from collections import defaultdict
dp = defaultdict(lambda:{})
def possible(last4):
    if 'AGC' in last4:
        return False
    for i in range(3):
        s = list(last4)
        s[i],s[i+1] = s[i+1],s[i]
        if 'AGC' in ''.join(s):
            return False
    return True
    
def rec(n,last3):
    if last3 in dp[n]:
        return dp[n][last3]
    if n == 3:
        if last3 not in ['AGC','GAC','ACG']:
            dp[n][last3] = 1
            return 1
        else:
            dp[n][last3] = 0
            return 0
    res = 0
    for s in 'AGCT':
        last4 = last3+s
        if possible(last4):
            res += rec(n-1,last4[1:])
            res %= mod
    dp[n][last3] = res
    return res

print(rec(N+3,'TTT'))

Submission status: Accepted

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

def is_valid(i, j, k, new):
    if (j, k, new) == (0, 1, 2) or (j, k, new) == (0, 2, 1) or (j, k, new) == (2, 0, 1):
        return False
    elif (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 1, 2, 1) or (i, j, k, new) == (0, 3, 2, 1):
        return False
    elif (i, j, k, new) == (0, 2, 0, 1) or (i, j, k, new) == (0, 2, 2, 1) or (i, j, k, new) == (0, 2, 3, 1):
        return False
    else:
        return True

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]
for n in range(3, N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for new in range(4):
                    if n ==3 and (i,j,k)!=(0,1,2) and (i,j,k)!=(1,2,1) and (i,j,k)!=(2,0,1):
                        dp[n][i][j][k]=1
                    elif is_valid(i, j, k, new):
                        dp[n][j][k][new] += dp[n-1][i][j][k]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N][i][j][k]) % mod
print(ans)

Submission status: Accepted

Solution code:
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

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

dna = ["A","C","G","T"]

def chk(last4):
    for i in range(len(last4)):
        l = list(last4)
        if i > 0:
            l[i],l[i-1] = l[i-1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

def rec(idx, last3):
    if idx == N:
        return 1
    elif last3 in memo[idx]:
        return memo[idx][last3]
    else:
        ret =0
        for d in dna:
            if chk(last3 + d):
                ret+= rec(idx+1,last3[1:]+d)
                ret = ret % (10**9+7)
        memo[idx][last3] = ret
        return ret


def ans():
    return rec(0,"TTT")

print(ans())

Submission status: Accepted

Solution code:
def dynamic_programming(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N+1)] 
    dp[0]['TTT'] = 1
    for n in range(N):
        for last3 in dp[n].keys():
            for c in 'ACTG':
                if is_ok(last3 + c):
                    if last3[1:] + c in dp[n+1].keys():
                        dp[n+1][last3[1:] + c] += dp[n][last3] % mod
                    else:
                        dp[n+1][last3[1:] + c] = dp[n][last3] % mod
    ret = sum(dp[N].values()) % mod
    return ret

def is_ok(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'))
    print(dynamic_programming(n))


main()

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], t[i - 1] = t[i - 1], t[i]
        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)
    memo[cur][last3] = ret
    return ret

print(dfs(0, "TTT") % MOD)

Submission status: Accepted

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

def ok(last4):
    
    
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        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)
    memo[cur][last3] = ret
    return ret

print(dfs(0, "TTT") % MOD)

Submission status: Accepted

Solution code:
import sys
N = int(input())
MOD = 10**9+7
ACGT = ['A', 'C', 'G', 'T']
# ?AGC
# ?GAC
# ?ACG
# A?GC
# AG?C

def ok(l4):
  l3 = l4[1:4]
  if l3 == 'AGC' or l3 =='GAC' or l3 == 'ACG':
    return False
  if l4[0] == 'A' and l4[2:4] == 'GC':
    return False
  if l4[0:2] == 'AG' and l4[3] == 'C':
    return False
  return True

# dp[i][l4] = i文字かつ末尾4文字がlast4な数
dp = [{} for _ in range(N+1)]

for c1 in ACGT:
  for c2 in ACGT:
    for c3 in ACGT:
      l4 = 'X' + c1 + c2 + c3
      if ok(l4):
        dp[3][l4] = 1
      else:
        dp[3][l4] = 0

for i in range(4, N+1):
  for l4 in dp[i-1].keys():
    for c in ACGT:
      next_l4 = l4[1:4] + c
      if not next_l4 in dp[i]:
        dp[i][next_l4] = 0
      if ok(next_l4):
        dp[i][next_l4] += dp[i-1][l4]

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

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
# memo[len][c1][c2][c3]
dp = [[[[0, 0, 0, 0] for k in range(4)] for j in range(4)] for i in range(n+1)]

# ACGT => 0123とする。
# 長さ0の文字数は1である。
# 0,1,2に関する制約しかないので文字列sは333sと考えても良い。
dp[0][3][3][3] = 1

for len in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0:
                    continue
                for add in range(4):
                    if c1 == 1 and c2 == 0 and add == 2:
                        continue
                    elif c1 == 0 and c2 == 1 and add == 2:
                        continue
                    elif c1 == 2 and c2 == 0 and add == 1:
                        continue
                    elif c1 == 1 and c3 == 0 and add == 2:
                        continue
                    elif c2 == 1 and c3 == 0 and add == 2:
                        continue
                    dp[len+1][add][c1][c2] += dp[len][c1][c2][c3]
                    dp[len+1][add][c1][c2] %= 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:
def valid(st):
    check_str = st[::-1]
    invalid_types = ["AGC", "A_GC", "GAC", "ACG", "AG_C"]
    for typ in invalid_types:
        typ = typ[::-1]
        i=0
        j=0
        if len(check_str) < len(typ):
            continue
        res = False
        for i in range(len(typ)):
            if typ[i] == '_':
                continue
            if typ[i] != check_str[i]:
                res = True
                break
        if res == False:
            return res
    return True

fsm = {}
index = 0
sigma = ["A", "C", "G", "T"]
for i in sigma:
    for j in sigma:
        for k in sigma:
            st = ''.join([i,j,k])
            if valid(st):
                fsm[st] = index
                index+=1
arr = [[],[]]
arr[0] = [0 for _ in range(len(fsm))]
arr[1] = [1 for _ in range(len(fsm))]
N = int(input())
for n in range(4, N+1):
    old = (n+1)%2
    nw = n%2
    visited = [False for x in range(len(fsm))]
    for state in fsm.keys():
        for y in sigma:
            if valid(state+y):
                if visited[fsm[state[1:]+y]]:
                    arr[nw][fsm[state[1:]+y]] = (arr[nw][fsm[state[1:]+y]]+arr[old][fsm[state]])%(10**9+7)
                else:
                    visited[fsm[state[1:]+y]] = True
                    arr[nw][fsm[state[1:]+y]] = arr[old][fsm[state]]
print(sum(arr[N%2])%(10**9+7))

Submission status: Accepted

Solution code:
import itertools

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

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

    for i, j, k in itertools.product(range(4), range(4), range(4)):
        dp[0][i][j][k] = 1
    dp[0][0][2][3] = 0 #AGC
    dp[0][0][3][2] = 0 #ACG
    dp[0][2][0][3] = 0 #GAC

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

        for i in range(4):
            dp[t+1][i][2][3] -= dp[t][0][i][2] #(A)*GC
        for i in range(4):
            dp[t+1][2][i][3] -= dp[t][0][2][i] #(A)G*C
        #(A)GGCが重複しているので
        dp[t+1][2][2][3] += dp[t][0][2][2]

        dp[t+1][0][2][3] = 0 #AGC
        dp[t+1][0][3][2] = 0 #ACG
        dp[t+1][2][0][3] = 0 #GAC

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - We Like AGC
https://atcoder.jp/contests/abc122/tasks/abc122_d

"""
import sys
import re

N = None
memo = None

def ok(last4):
    if re.search(r'AGC|GAC|ACG|A.GC|AG.C', last4):
        return False
    return True


def dfs(cur, last3):
    global memo
    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)) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret


def main(args):
    global N, memo
    N = int(input())
    memo = [dict() for i in range(N+1)]
    ans = dfs(0, 'TTT')
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def 解():
    N = int(input())
    iD = 10**9+7

    #3210
    #***A
    #***G
    #***C
    #***T
    #*ACG
    #*GAC
    #*AGC
    #AGGC #A*GC AG*C から重複を消したもの
    #AGTC
    #ATGC

    A = [0]*(N+1)
    G = [0]*(N+1)
    C = [0]*(N+1)
    T = [0]*(N+1)
    AC = [0]*(N+1)
    GA = [0]*(N+1)
    AG = [0]*(N+1)
    AGG = [0]*(N+1)
    AGT = [0]*(N+1)
    ATG = [0]*(N+1)

    A[1]=G[1]=C[1]=T[1]=1 #種
    for i in range(2,N+1):
        #前の桁の末尾に一文字足したものから条件を満たすものを消す
        A[i] = A[i-1] + G[i-1] + C[i-1] +T[i-1]
        G[i] = A[i] - AC[i-1]
        C[i] = A[i] - GA[i-1] - AG[i-1] - AGG[i-1] - AGT[i-1] - ATG[i-1]
        T[i] = A[i]

        #この桁の末尾の場合の数を計算
        AC[i] = A[i-1] - GA[i-1]  # **AC を計算するために**A*を使うが*GAC の分(*GA*)はこの桁で消えるので消す
        AG[i] = A[i-1]
        GA[i] = G[i-1]

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

        A[i] %= iD
        G[i] %= iD
        C[i] %= iD
        T[i] %= iD
        AC[i] %= iD
        GA[i] %= iD
        AG[i] %= iD
        AGG[i] %= iD
        ATG[i] %= iD
        AGT[i] %= iD

    print((A[N]+G[N]+C[N]+T[N])%iD)
解()

Submission status: Accepted

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

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        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)
    memo[cur][last3] = ret
    return ret
    
print(dfs(0, "TTT") % 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)) 
    memo[cur][last3] = ret
    return ret
    
print(dfs(0, 'TTT') % MOD)

Submission status: Accepted

Solution code:
n = int(input())
s = ["A","T","G","C"]
ban = ["AGC","ACG","GAC"]
ban4 = ["ATGC","AGTC","AGGC"]
last3 = [{},{}]
zl = {}
for i in s:
    for j in s:
        for k in s:
            if i+j+k not in ban:
                last3[0][i+j+k] = 1
                zl[i+j+k] = 0
last3[1] = zl.copy()

for k in range(3,n):
    for i in last3[0]:
        for j in s:
            l = i+j
            if not (l in ban4 or l[1:] in ban):
                last3[1][l[1:]] += last3[0][i]
    last3[0] = last3[1]
    last3[1] =zl.copy()

print(sum(last3[0].values())%(10**9+7))

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"):
            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)
            ret%=MOD
        memo[cur][last3] = ret
    return ret
print(dfs(0,"TTT"))

Submission status: Accepted

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

def is_agc(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 True
    return False

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0

    for char in 'ATGC':
        if not is_agc(last3 + char):
            ret = (ret + dfs(cur + 1, last3[1:] + char)) % mod
        memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
import itertools, math

N = int(input())

ACGTList = ["A", "G", "C", "T"]
AGCList = ["ATGC", "AGTC", "AGGC"]
for ACGT in ACGTList:
    for AGC in ["AGC", "ACG", "GAC"]:
        AGCList.append(ACGT + AGC)
        AGCList.append(AGC + ACGT)

patternObj = itertools.product(ACGTList, repeat=3)
patternDict = {}
for i, pattern in enumerate(patternObj):
    strPattern = "".join(pattern)
    patternDict[strPattern] = 0 if strPattern in ["AGC", "ACG", "GAC"] else 1

for i in range(N - 3):
    nextPatternDict = dict.fromkeys(patternDict, 0)
    for pattern in patternDict:
        for ACGT in ACGTList:
            newPattern = pattern + ACGT
            if newPattern in AGCList:
                continue
            nextPatternDict[newPattern[:3]] += patternDict[newPattern[1:]]
    patternDict = nextPatternDict.copy()

ans = 0
devide = int(math.pow(10, 9)) + 7
for pattern in patternDict:
    ans += patternDict[pattern]
    ans %= devide

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
aa = ["A","C","G","T"]
dic = {}
invdic = {}
n = int(input())
for i in range(4):
    for j in range(4):
        for k in range(4):
            dic[16*i+4*j+k] = aa[i]+aa[j]+aa[k]
            invdic[aa[i]+aa[j]+aa[k]] = 16*i+4*j+k


dp = [[0 for j in range(64)] for i in range(101)]

for i in range(64):
    dp[3][i] = 1

dp[3][invdic["AGC"]]=0
dp[3][invdic["GAC"]]=0
dp[3][invdic["ACG"]]=0

for i in range(3,100):
    for j in range(64):
        moji = dic[j]
        if(moji[0] == "A" and moji[2] == "G") or(moji[0] == "A" and moji[1] == "G")or(moji[1] == "A" and moji[2] == "G")or(moji[1] == "G" and moji[2] == "A"):
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"G"]] = (dp[i+1][invdic[moji[1]+moji[2]+"G"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
        elif(moji[1] == "A" and moji[2] == "C"):
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"C"]] = (dp[i+1][invdic[moji[1]+moji[2]+"C"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
        else:
            dp[i+1][invdic[moji[1]+moji[2]+"A"]] = (dp[i+1][invdic[moji[1]+moji[2]+"A"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"C"]] = (dp[i+1][invdic[moji[1]+moji[2]+"C"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"T"]] = (dp[i+1][invdic[moji[1]+moji[2]+"T"]]+dp[i][j]) % MOD
            dp[i+1][invdic[moji[1]+moji[2]+"G"]] = (dp[i+1][invdic[moji[1]+moji[2]+"G"]]+dp[i][j]) % MOD        
    
        

ans = 0

for i in range(64):
    ans = (ans+dp[n][i]) % MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def checkAGC(string):
    str0 = string[0] +string[1] +string[2] +string[3]
    str1 = string[1] +string[0] +string[2] +string[3]
    str2 = string[0] +string[2] +string[1] +string[3]
    str3 = string[0] +string[1] +string[3] +string[2]
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 or "AGC" in str3:
        return True
    else:
        return False

def checkAGC3(string):
    str0 = string[0] +string[1] +string[2]
    str1 = string[1] +string[0] +string[2] 
    str2 = string[0] +string[2] +string[1] 
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 :
        return True
    else:
        return False
      

import itertools

words = list(itertools.product("ATGC", "ATGC","ATGC"))

#3文字のインデックスを返す
nucleotide_dict =  dict(list( (words[i],i) for i in range(len(words))))

import numpy as np
# 重み行列を求める
W = np.zeros((len(words),len(words)))
for word_prev in words:
    for word_next in words:
        if word_prev[1:] == word_next[:-1] and not checkAGC(word_prev[:-1]+word_next[1:]):
            #print(nucleotide_dict[word_next],nucleotide_dict[word_prev],word_prev[:-1]+word_next[1:] )
            W[nucleotide_dict[word_next],nucleotide_dict[word_prev]] = 1
b = np.array([0 if checkAGC3(i) else 1 for i in words])

def mod(num):
    return num % int(pow(10,9)+7)
  
res = b
for i in range(N-3):
    res = np.vectorize(lambda x: mod(x))(np.dot(W,res))
print(int(mod(np.sum(res))))

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())
mod = 10 ** 9 + 7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]


def ng(a: int, b: int, c: int):
    return (a == 1 and b == 2 and c == 3)


# 初期状態の直近3文字はTTTであると見なして良い
dp[0][0][0][0] = 1
for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    # 3文字パターン
                    if (ng(b, c, d) or ng(c, b, d) or ng(b, d, c)):
                        continue
                    # 4文字パターン
                    if ng(a, c, d) or ng(a, b, d):
                        continue
                    # NGパターンがなければ遷移先に足す
                    dp[i+1][b][c][d] = (dp[i][a][b][c] + dp[i+1][b][c][d]) % mod


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


print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
dp = [[[[1 if i==0 else 0 for i in range(n-2)] for j in range(4)] for k in range(4)] for l in range(4)]
dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[2][0][1][0] = 0
for i in range(n - 3):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[j][k][l][i] == 0:
                    continue
                for m in range(4):
                    if k == 0 and l == 2 and m == 1:
                        continue
                    if k == 0 and l == 1 and m == 2:
                        continue
                    if k == 2 and l == 0 and m == 1:
                        continue
                    if j == 0 and l == 2 and m == 1:
                        continue
                    if j == 0 and k == 2 and m == 1:
                        continue
                    dp[k][l][m][i + 1] += dp[j][k][l][i]
                    dp[k][l][m][i + 1] %= mod
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[j][k][l][n - 3]

print(ans % mod)