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 = int(input())
mod = 10 ** 9 + 7

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

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

    count = 0
    for c in "ACGT":
        if valid(S + c):
            count = (count + dfs(cur + 1, S[1:] + c)) % mod
    memo[cur][S] = count
    return count

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
# ABC 122 D

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

dp = [[[[0,0,0,0] for k in range(4)] for l in range(4)] for m in range(N+1)]
# dp[i][a][b][c] := i番目まで見て、最後の三文字が左からa,b,c
# A,C,G,T = 0,1,2,3 にそれぞれ対応
dp[0][3][3][3] = 1

for p in range(1,N+1):
    for k in range(4):
        for l in range(4):
            for m in range(4):
                for n in range(4):
                    # だめなのは klmn = *021, *012, *201, 0*21, 02*1
                    if (l==0 and m==2 and n==1) or (l==0 and m==1 and n==2) or (l==2 and m==0 and n==1) or (k==0 and m==2 and n==1) or (k==0 and l==2 and n==1):
                        pass
                    else:
                        dp[p][l][m][n] += dp[p-1][k][l][m]
                        dp[p][l][m][n] %= MOD

ans = 0
for k in range(4):
    for l in range(4):
        for m in range(4):
            ans += dp[N][k][l][m]
print(ans%MOD)

Submission status: Accepted

Solution code:
N = int(input())
M = 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 l in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[l][i][j][k] == 0:
                    continue
                for a in range(4):
                    if j == 0 and k == 1 and a == 2:
                        continue
                    if j == 0 and k == 2 and a == 1:
                        continue
                    if j == 1 and k == 0 and a == 2:
                        continue
                    if i == 0 and j == 1 and a == 2:
                        continue
                    if i == 0 and k == 1 and a == 2:
                        continue
                    dp[l + 1][j][k][a] += dp[l][i][j][k]
                    dp[l + 1][j][k][a] %= M
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%M)

Submission status: Accepted

Solution code:
import numpy as np
    
N = int(input())
MOD=7+10**9

def pattern_calc(num,i,j,k,l):
    #print(num,":",i,",",j,",",k,",",l,end="")
    
    #最終4文字がNGならパターン数0
    if calc_result[0,i,j,k,l]==0:
        #print("last 4 char is NG pattern.")
        sub_ans = 0
        
    else:
        if calc_flag[num,i,j,k,l] == True:
            sub_ans = calc_result[num,i,j,k,l]
            #print("…Calculated:",calc_result[num,i,j,k,l])
        else:
            #print("…Need  Calc :")

            for atot in range(4): 
                calc_result[num,i,j,k,l] = calc_result[num,i,j,k,l] + pattern_calc(num-1,atot,i,j,k)%MOD #uint64にしてもエラー出たのでここにもMODを入れた。
                #print(pattern_calc(num-1,atot,i,j,k))
                #print(calc_result[num,i,j,k,l])
                
            calc_flag[num,i,j,k,l] = True
            sub_ans = calc_result[num,i,j,k,l]
            #print(num,":",i,",",j,",",k,",",l,"→",sub_ans)
    return sub_ans            

if N==3:
    print("61")
else:   
    calc_result = np.zeros((N-3,4,4,4,4),dtype=np.uint64) #計算結果。[]の条件を満たせるのは何通りあるか? #ここがfloatだとダメだった!!!
    #ex
    #result_list[0,0,1,2,3]…最後4文字がA,G,C,TでAより前の文字数が0のパターンは満たせるか? → 0
    #result_list[1,0,1,2,3]…最後4文字がA,G,C,TでAより前の文字数が0のパターンは満たせるか? → 0


    #result_list[0,0,1,2,3]…0
    #result_list[0,1,1,2,3]…1
    #result_list[0,2,1,2,3]…1
    #result_list[0,3,1,2,3]…1

    #result_list[1,1,2,3,0]…最後4文字がG,C,T,AでGより前の文字数が1のパターンは満たせるか? → 3
    #result_list[2,2,3,0,1]…最後4文字がC,T,A,GでCより前の文字数が1のパターンは満たせるか? 
    #   →result_list[1,0,2,3,0],result_list[1,1,2,3,0],result_list[1,2,2,3,0],result_list[1,3,2,3,0]のSUM

    calc_flag = np.zeros((N-3,4,4,4,4), dtype=np.bool) #計算済みか
    #A→0,G→1,C→2,T→3として扱う。

    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    calc_result[0,i,j,k,l] = 1
                    calc_flag[0,i,j,k,l] = True

    calc_result[0,0,0,1,2]=0
    calc_result[0,0,0,2,1]=0
    calc_result[0,0,1,1,2]=0
    calc_result[0,0,1,3,2]=0
    calc_result[0,0,1,2,0]=0
    calc_result[0,0,1,2,1]=0
    calc_result[0,0,1,2,2]=0
    calc_result[0,0,1,2,3]=0
    calc_result[0,0,1,0,2]=0
    calc_result[0,0,2,1,0]=0
    calc_result[0,0,2,1,1]=0
    calc_result[0,0,2,1,2]=0
    calc_result[0,0,2,1,3]=0
    calc_result[0,0,3,1,2]=0
    calc_result[0,1,0,1,2]=0
    calc_result[0,1,0,2,0]=0
    calc_result[0,1,0,2,1]=0
    calc_result[0,1,0,2,2]=0
    calc_result[0,1,0,2,3]=0
    calc_result[0,1,1,0,2]=0
    calc_result[0,2,0,2,1]=0
    calc_result[0,2,1,0,2]=0
    calc_result[0,2,0,1,2]=0
    calc_result[0,3,0,2,1]=0
    calc_result[0,3,1,0,2]=0
    calc_result[0,3,0,1,2]=0

    N = N - 4
    ans = 0
    
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    #print(N,",",i,",",j,",",k,",",l,":",int(pattern_calc(N,i,j,k,l)))
                    ans = (ans + pattern_calc(N,i,j,k,l))

    print(int(ans%MOD))
    
    #29まではOKっぽい?
    #30 正答　531294469　自分の　531293960…5093足りない →floatからintに直したらいけた!

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

inf = 10**9+7
def ng(key, c=None):
    if c is None:
        return key == "agc" or key == "gac" or key == "acg"
    if key[0] == 'a' and key[1] == 'g' and c == 'c':
        "ag.c"
        return True
    if key[0] == 'a' and key[2] == 'g' and c == 'c':
        "a.gc"
        return True
    if key[1] == 'a' and key[2] == 'g' and c == 'c':
        "agc"
        return True
    if key[1] == 'g' and key[2] == 'a' and c == 'c':
        "gac"
        return True
    if key[1] == 'a' and key[2] == 'c' and c == 'g':
        "acg"
        return True
    return False


def init():
    ret = {}
    for c1 in list('acgt'):
        for c2 in list('acgt'):
            for c3 in list('acgt'):
                key = c1+c2+c3
                if ng(key):
                    continue
                ret[key] = 1
    return ret


def next(dp):
    ndp = {}
    for key in dp:
        for c in list('atcg'):
            if ng(key, c):
                continue
            nkey = key[1:] + c
            ndp.setdefault(nkey, 0)
            ndp[nkey] += dp[key] % inf
    return ndp


def main():
    N = int(input())
    dp = init()
    for i in range(N-3):
        dp = next(dp)
    print(sum(dp.values()) % inf)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10**9+7
dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(N+1)]
A, G, C, T = 0, 1, 2, 3

# 初期化
for i in range(4):
    for j in range(4):
        for k in range(4):
            if k == A and j == G and i == C: continue
            if k == A and j == C and i == G: continue
            if k == G and j == A and i == C: continue
            dp[3][k][j][i] = 1

for index in range(4,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if k == A and j == G and i == C:
                        continue
                    if k == G and j == A and i == C:
                        continue
                    if l == A and j == G and i == C:
                        continue
                    if l == A and k == G and i == C:
                        continue
                    if k == A and j == C and i == G:
                        continue
                    dp[index][k][j][i] += dp[index-1][l][k][j]
                    dp[index][k][j][i] = dp[index][k][j][i]%MOD
                    
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][k][j][i]
            ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import itertools

s = 'ACGT'
s = [a+b+c for a,b,c in itertools.product(s,s,s)]
n = {s_:1 for s_ in s}
n['AGC'] = 0
n['GAC'] = 0
n['ACG'] = 0

N = int(input())
if N == 3:
    count = n
else:
    for i in range(N-3):
        count = {s_:0 for s_ in s}
        for _ in s:
            for a in 'ACGT':
                x = _+a
                if 'GAC' in x or 'ACG' in x or ('A' == x[0] and 'GC' == x[2:]) or ('AG' == x[:2] and 'C' == x[3]):
                    pass
                else:
                    count[x[1:]] += n[_]
        count['AGC'] = 0
        count['GAC'] = 0
        count['ACG'] = 0
        n = count
print(sum([value for value in count.values()])%(10**9+7))

Submission status: Accepted

Solution code:
N=int(input())
dp = [{} for _ in range(101)]

str = "ACGT"
mod = 10**9+7
for i in range(4):
  for j in range(4):
    for k in range(4):
      last3 = str[i] + str[j] + str[k]
      if last3 == "AGC" or last3 == "ACG" or last3 == "GAC":
        dp[3][last3] = 0
      else:
        dp[3][last3] = 1

for n in range(4,101):
  for last3 in dp[n-1]:
    for c in str:
      new_last3 = last3[1:]+c
      if new_last3 == "AGC" or new_last3 == "ACG" or new_last3 == "GAC":
        dp[n][new_last3] = 0
      else:
        if last3 == "AGC" or last3 == "ACG" or last3 == "GAC":
          if new_last3 not in dp[n]:
            dp[n][new_last3] = 0
        elif last3 == "AAG" or last3 == "AGA" or last3 == "AGG" or last3 == "AGT" or last3 == "ATG" or last3 == "CAG" or last3 == "CGA" or last3 == "GAG" or last3 == "GGA" or last3 == "TAG" or last3 == "TGA":
          if new_last3[2] != "C":
            if new_last3 not in dp[n]:
              dp[n][new_last3] = dp[n-1][last3]
            else:
              dp[n][new_last3] += dp[n-1][last3]
        elif last3 == "AAC" or last3 == "CAC" or last3 == "TAC":
          if new_last3[2] != "G":
            if new_last3 not in dp[n]:
              dp[n][new_last3] = dp[n-1][last3]
            else:
              dp[n][new_last3] += dp[n-1][last3]
        else:
          if new_last3 not in dp[n]:
            dp[n][new_last3] = dp[n-1][last3]
          else:
            dp[n][new_last3] += dp[n-1][last3]

sum = 0
for s in dp[N]:
  sum += dp[N][s]
  sum %= mod

print(sum)

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

import numpy as np
#'A','T','G','C'
a = np.zeros([4,4,4],np.int64)
a+=1

a[0,2,3]=0
a[2,0,3]=0
a[0,3,2]=0

for i in range(N-3):
  b = np.zeros([4,4,4],np.int64)
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if ( j==0 and k==2 ) or ( j==2 and k==0 ) or ( i==0 and k==2 ) or (i==0 and j==2 ):
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,2] += a[i,j,k]
        elif ( j==0 and k==3 ):
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,3] += a[i,j,k]
        else:
          b[j,k,0] += a[i,j,k]
          b[j,k,1] += a[i,j,k]
          b[j,k,2] += a[i,j,k]
          b[j,k,3] += a[i,j,k]
  a=b%(1000000007)
  
        

print ( np.sum(a)%1000000007 )

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
#dp[文字数][前3][前2][前1]=個数
dp=[[[[0for i in range(4)]for i in range(4)]for i in range(4)]for i in range(n)]
s=[0 for i in range(n)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[0][i][j][k]=1
s[0]=4
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[1][i][j][k]=1
s[1]=16
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[2][i][j][k]=1
dp[2][0][2][1]=0
dp[2][0][1][2]=0
dp[2][2][0][1]=0
s[2]=61
for a in range(3,n):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        dp[a][i][j][k]=sum(dp[a-1][j][k])
  #agc-,ag-c,a-gc,-agc,gac-,-gac,acg-,-acg
  #-agc,-gac,-acg
  #0120,0121,0122,0123
  dp[a][0][1][2]-=dp[a-1][1][2][0]+dp[a-1][1][2][1]+dp[a-1][1][2][2]+dp[a-1][1][2][3]
  #0210,0211,0212,0213
  dp[a][0][2][1]-=dp[a-1][2][1][0]+dp[a-1][2][1][1]+dp[a-1][2][1][2]+dp[a-1][2][1][3]
  #0221
  dp[a][0][2][2]-=dp[a-1][2][2][1]
  #0231
  dp[a][0][2][3]-=dp[a-1][2][3][1]
  #0321
  dp[a][0][3][2]-=dp[a-1][3][2][1]
  #2010,2011,2013
  dp[a][2][0][1]-=dp[a-1][0][1][0]+dp[a-1][0][1][1]+dp[a-1][0][1][3]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        dp[a][i][j][k]%=mod
        s[a]+=dp[a][i][j][k]
        s[a]%=mod
print(s[n-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

nglist = [
    "?AGC", "AGC?",
    "A?GC", "AG?C",
    "GAC?", "?GAC",
    "ACG?", "?ACG"
]
ng = {}
for t in "AGCT":
    for n in nglist:
        ng[n.replace('?', t)] = 1

dp = {"TTT": 1}

for i in range(N):
    ans = 0
    _dp = defaultdict(int)
    for k, v in dp.items():
        for t in "AGCT":
            s = k+t
            if s not in ng:
                _dp[s[1:]] += v
                ans = (ans+v) % MOD
    dp = _dp
    if i == (N-1):
        print(ans)

Submission status: Accepted

Solution code:
N = int(input())
M = 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)
]
#print([1 if i==0 else 0 for i in range(N-2)])

dp[0][1][2][0] = 0 # AGC
dp[0][2][1][0] = 0 # GAC
dp[1][0][2][0] = 0 # ACG

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    # 問題ないのものは１
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    #dp[j][k][l][m+1] %= M
                    # AGC,GAC,ACGは全部０にする
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

Submission status: Accepted

Solution code:
###AGC,GAC,ACG,A*GC,AG*Cが存在しない

###k-1個の組み合わせの後に'AGCT'を付け足し、ダメな組み合わせを引いた数がk個の組み合わせ
###k-1がl個のとき、kはl*4-ダメな数

import sys

n = int(input())

if n <= 2:
  print(4**n)
  sys.exit()

end = {}
for i in ['A','G','C','T']:
  for j in ['A','G','C','T']:
    for k in ['A','G','C','T']:
      if i+j+k in ['AGC','GAC','ACG']:
        end[i+j+k] = 0
      else:
        end[i+j+k] = 1
        
num = 61
if n == 3:
  print(num)
  sys.exit()

###*AG+C
notend = ['AAG','GAG','CAG','TAG']
notpattarn = ['AAGC','GAGC','CAGC','TAGC']
###*GA+C
notend += ['AGA','GGA','CGA','TGA']
notpattarn += ['AGAC','GGAC','CGAC','TGAC']
###*AC+G
notend += ['AAC','CAC','TAC']
notpattarn += ['AACG','CACG','TACG']
###AG*+C
notend += ['AGG','AGT']
notpattarn += ['AGGC','AGTC']
###A*G+C
notend += ['ATG']
notpattarn += ['ATGC']

for i in range(4,n+1):
  
  num *= 4
  for j in end.keys():
    if j in notend:
      num -= end[j]
      
  end_tmp = {}
  for j in end.keys():
    end_tmp[j] = 0
  
  for j in end.keys():
    for k in ['A','G','C','T']:
      if k+j in notpattarn:
        pass
      else:
        end_tmp[j] += end[k+j[0:2]]
        
  end = end_tmp
  
#print(num)
print(num%(10**9+7))

Submission status: Accepted

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

E = "ACGT"

from collections import defaultdict

ngp = [
    "AGC?", "GAC?", "ACG?",
    "?AGC", "?GAC", "?ACG",
    "A?GC", "AG?C"
]

ng = set(["AGC", "GAC", "ACG"])

for x in ngp:
    for c in E:
        ng.add(x.replace("?", c))

rs = {"": 1}

for i in range(N):
    nrs = defaultdict(int)
    for k, v in rs.items():
        for e in E:
            nk = (k + e)[-4:]
            if not nk in ng:
                nrs[nk[-3:]] += v
    rs = nrs

result = sum(nrs.values()) % M

print(result)

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################


counts_3 = {
  "CAA": 1,
  "CTT": 1,
  "TTT": 1,
  "GGC": 1,
  "CGT": 1,
  "GTG": 1,
  "ACC": 1,
  "GCA": 1,
  "TTC": 1,
  "TCA": 1,
  "GGT": 1,
  "GTT": 1,
  "CAG": 1,
  "AAT": 1,
  "TAA": 1,
  "TAG": 1,
  "CCA": 1,
  "GCT": 1,
  "CTA": 1,
  "TCT": 1,
  "TTG": 1,
  "ATT": 1,
  "CAT": 1,
  "GAA": 1,
  "ATA": 1,
  "CCC": 1,
  "GCG": 1,
  "TTA": 1,
  "ACA": 1,
  "AGT": 1,
  "AGG": 1,
  "AGA": 1,
  "CCG": 1,
  "ATG": 1,
  "GAG": 1,
  "AAA": 1,
  "TCC": 1,
  "AAG": 1,
  "GCC": 1,
  "ACT": 1,
  "TGG": 1,
  "CTC": 1,
  "TCG": 1,
  "TGT": 1,
  "CGC": 1,
  "TAC": 1,
  "TAT": 1,
  "CGG": 1,
  "GGG": 1,
  "TGA": 1,
  "CCT": 1,
  "AAC": 1,
  "CGA": 1,
  "GTC": 1,
  "ATC": 1,
  "GGA": 1,
  "CAC": 1,
  "CTG": 1,
  "GAT": 1,
  "TGC": 1,
  "GTA": 1
}


mod = 10**9 + 7


def main():
    n = intin()

    all_ok = []
    not_c = []
    not_g = []
    for suffix in counts_3:
        if suffix == 'ATG' or suffix == 'AGG' or suffix == 'AAG':
            not_c.append(suffix)
        elif suffix == 'AGT':
            not_c.append(suffix)
        elif 'T' in suffix[1:]:
            all_ok.append(suffix)
        elif suffix[1:] == 'AA' or suffix[1:] == 'GG' or suffix[1:] == 'CC':
            all_ok.append(suffix)
        elif suffix[1:] == 'AG' or suffix[1:] == 'GA':
            not_c.append(suffix)
        elif suffix[1:] == 'AC':
            not_g.append(suffix)
        else:
            all_ok.append(suffix)

    suffix_counts = {3: counts_3}

    for i in range(4, 101):
        prev_count = suffix_counts[i-1]
        suffix_count = {}
        for suffix, count in prev_count.items():
            if suffix in all_ok:
                charlist = ['A', 'C', 'G', 'T']
            if suffix in not_c:
                charlist = ['A', 'G', 'T']
            if suffix in not_g:
                charlist = ['A', 'C', 'T']
            for c in charlist:
                new_suffix = suffix[1:] + c
                suffix_count.setdefault(new_suffix, 0)
                suffix_count[new_suffix] = modadd(suffix_count[new_suffix], count)
        suffix_counts[i] = suffix_count

    suffix_count = suffix_counts[n]

    ans = 0
    for i, count in suffix_count.items():
        ans = modadd(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


###############################################################################

counts_3 = {
  "CAA": 1,
  "CTT": 1,
  "TTT": 1,
  "GGC": 1,
  "CGT": 1,
  "GTG": 1,
  "ACC": 1,
  "GCA": 1,
  "TTC": 1,
  "TCA": 1,
  "GGT": 1,
  "GTT": 1,
  "CAG": 1,
  "AAT": 1,
  "TAA": 1,
  "TAG": 1,
  "CCA": 1,
  "GCT": 1,
  "CTA": 1,
  "TCT": 1,
  "TTG": 1,
  "ATT": 1,
  "CAT": 1,
  "GAA": 1,
  "ATA": 1,
  "CCC": 1,
  "GCG": 1,
  "TTA": 1,
  "ACA": 1,
  "AGT": 1,
  "AGG": 1,
  "AGA": 1,
  "CCG": 1,
  "ATG": 1,
  "GAG": 1,
  "AAA": 1,
  "TCC": 1,
  "AAG": 1,
  "GCC": 1,
  "ACT": 1,
  "TGG": 1,
  "CTC": 1,
  "TCG": 1,
  "TGT": 1,
  "CGC": 1,
  "TAC": 1,
  "TAT": 1,
  "CGG": 1,
  "GGG": 1,
  "TGA": 1,
  "CCT": 1,
  "AAC": 1,
  "CGA": 1,
  "GTC": 1,
  "ATC": 1,
  "GGA": 1,
  "CAC": 1,
  "CTG": 1,
  "GAT": 1,
  "TGC": 1,
  "GTA": 1
}


def main():
    n = intin()
    mod = 10**9 + 7

    all_ok = []
    not_c = []
    not_g = []
    for suffix in counts_3:
        if suffix == 'ATG' or suffix == 'AGG' or suffix == 'AAG':
            not_c.append(suffix)
        elif suffix == 'AGT':
            not_c.append(suffix)
        elif 'T' in suffix[1:]:
            #print(suffix)
            all_ok.append(suffix)
        elif suffix[1:] == 'AA' or suffix[1:] == 'GG' or suffix[1:] == 'CC':
            #print(suffix)
            all_ok.append(suffix)
        elif suffix[1:] == 'AG' or suffix[1:] == 'GA':
            not_c.append(suffix)
        elif suffix[1:] == 'AC':
            not_g.append(suffix)
        else:
            #print(suffix)
            all_ok.append(suffix)

    suffix_counts = {3: counts_3}

    for i in range(4, 101):
        prev_count = suffix_counts[i-1]
        suffix_count = {}
        for suffix, count in prev_count.items():
            if suffix in all_ok:
                charlist = ['A', 'C', 'G', 'T']
            if suffix in not_c:
                charlist = ['A', 'G', 'T']
            if suffix in not_g:
                charlist = ['A', 'C', 'T']
            for c in charlist:
                new_suffix = suffix[1:] + c
                suffix_count.setdefault(new_suffix, 0)
                suffix_count[new_suffix] += count
                suffix_count[new_suffix] %= mod
        suffix_counts[i] = suffix_count

    suffix_count = suffix_counts[n]

    #print(suffix_count)

    ans = 0
    for i, count in suffix_count.items():
        ans += count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def ok(s: str):
    ng = 'AGC'
    c = s.count(ng)
    for i in range(1, 4):
        s2 = s[:i-1] + s[i] + s[i-1] + s[i+1:]
        c += s2.count(ng)
    return c == 0
    

def solve(N: int):
    K = [''.join(t) for t in itertools.product('ACGT', repeat=3)]
    C = [{k: 0 for k in K} for i in range(N+2)] # C[-1 ~ N]
    C[0]['TTT'] = 1
    
    for i in range(1, N+1):
        for last3 in C[i-1].keys():
            for c in 'ACGT':
                if ok(last3 + c):
                    C[i][last3[1:] + c] = (C[i][last3[1:] + c] + C[i-1][last3]) % MOD
    print(sum([C[N][k] for k in K]) % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from itertools import chain
from functools import reduce

N = int(input())
atgc = "ATGC"
labels = []
for c1 in atgc:
    for c2 in atgc:
        for c3 in atgc:
            labels.append(c1+c2+c3)

labels[0], labels[11] = labels[11], labels[0]
labels[1], labels[14] = labels[14], labels[1]
labels[2], labels[35] = labels[35], labels[2]

lb2i = {lb:i for i, lb in enumerate(labels)}
mat = [[0]*64 for i in range(64)]

def swap(s, i, j):
    s = list(s)
    s[i], s[j] = s[j], s[i]
    return "".join(s)

for i, lb1 in enumerate(labels):
    tmp = [(lb1+c) for c in atgc]
    tmp = [s for s in tmp if not any(["AGC" in swap(s, i, i+1) for i in range(3)])]
    for lb2 in tmp:
        mat[i][lb2i[lb2[1:]]] += 1

prev = [1]*64
curr = [0]*64

mod = 1000000007

for _ in range(N-3):
    prev[0:3] = [0,0,0]
    for j in range(64):
        curr[j] = 0
    for lbi1 in range(64):
        for lbi2 in range(64):
            curr[lbi2] += mat[lbi1][lbi2]*prev[lbi1]
            curr[lbi2] %= mod
    curr, prev = prev, curr

prev[0:3] = [0,0,0]
print(reduce(lambda acc, x: (acc+x)%mod, prev, 0))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(N+1)]


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

mod = 10**9+7

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 == 1 and c1 == 0 and a == 2:
                        continue
                    if c2 == 0 and c1 == 2 and a == 1:
                        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][c3][c2][c1]
                    dp[length+1][c2][c1][a] %= mod

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

print(ans)

Submission status: Accepted

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

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

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in '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, mod = int(input()), 10**9+7
memo = [{} for i in range(N+1)]
# memo = [{},{},{},...]

def ok(last4):
  for i in range(4):
    l = list(last4)
    if l[1]=='A' and l[2]=='G' and l[3]=='C':
      return False
    if l[1]=='A' and l[2]=='C' and l[3]=='G':
      return False
    if l[1]=='G' and l[2]=='A' and l[3]=='C':
      return False
    if l[0]=='A' and l[2]=='G' and l[3]=='C':
      return False
    if l[0]=='A' and l[1]=='G' and l[3]=='C':
      return False
    else:return True
    
def func(num, last3):
  if last3 in memo[num]:
    return memo[num][last3]
  if num == N:
    return 1
  ans = 0
  for i in 'ACGT':
    if ok(last3 + i):
      ans = (ans + func(num+1, last3[1:] + i)) % mod
  memo[num][last3] = ans
  return ans
    
      
print(func(0,'TTT'))
# 72

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(1,n+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                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[i][c2][c1][a] += dp[i-1][c3][c2][c1]
                    dp[i][c2][c1][a] %= MOD
ans = 0
for c1 in range(4):
    for c2 in range(4):
        ans += sum(dp[i][c1][c2])
        ans %= MOD
print(ans)

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(1,N+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                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[i][c2][c1][a] += dp[i-1][c3][c2][c1]
                    dp[i][c2][c1][a] %= mod
ans = 0
for c1 in range(4):
    for c2 in range(4):
        ans += sum(dp[i][c1][c2])
        ans %= mod
print(ans)

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 + 1][c2 + c3 + p] + dp[l][c1 + c2 + c3]) % 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)