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 sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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

MOD = 10 ** 9 + 7
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 n in range(4):
                    if j == 0 and k == 2 and n == 1: continue
                    if j == 0 and k == 1 and n == 2: continue
                    if j == 1 and k == 0 and n == 2: continue

                    if i == 0 and j == 1 and n == 2: continue
                    if i == 0 and k == 1 and n == 2: continue 

                    dp[l+1][j][k][n] += dp[l][i][j][k]
                    dp[l+1][j][k][n] %= 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%MOD)

Submission status: Accepted

Solution code:
#A,G,C,T=0,1,2,3
#AGC,ACG,GACを含まない
#A?GC,AG?Cを含まない
import copy

n=int(input())
A=[[1,1,1,1],[1,1,0,1],[1,0,1,1],[1,1,1,1]] #3文字前がAのとき
B=[[3,3,2,3],[3,3,3,3],[3,3,3,3],[3,3,3,3]] #それ以外
mod=10**9+7

for _ in range(n-3):
    nA=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    nB=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    for i in range(4):
        for j in range(4): #付け足す文字
            if j!=2: #3文字前がAで、Cを足さないとき
                if not (i==2 and j==1): #ACG
                    nA[i][j]+=A[0][i]
                nB[i][j]+=A[1][i]
                nB[i][j]+=A[2][i]
                nB[i][j]+=A[3][i]
            else: #Cを足すとき
                if i!=1: #A?GC
                    nA[i][j]+=A[0][i]
                    #nB[i][j]+=A[1][i] #AG?C
                    nB[i][j]+=A[2][i]
                    nB[i][j]+=A[3][i]
            
            if not i*j==2: #AGC,ACG
                nA[i][j]+=B[0][i]
            if not (i==0 and j==2): #GAC
                nB[i][j]+=B[1][i]
            nB[i][j]+=B[2][i]
            nB[i][j]+=B[3][i]
    for a in nA:
        for i in range(4):
            a[i]%=mod
    for b in nB:
        for i in range(4):
            b[i]%=mod
    A=copy.copy(nA)
    B=copy.copy(nB)
    
ans=0
for a in A:
    ans+=sum(a)%mod
for b in B:
    ans+=sum(b)%mod 
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7

N = int(input())

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

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

#Tは制約に入らないので、スタートをTTT+Sみたいな感じに考える。ここで0とか1とか2を使うといらないところでcontinueしてしまう。
dp[0][3][3][3] = 1

for l in range(N):
    #左から3番目
    for last3 in range(4):
        #左から2番目
        for last2 in range(4):
            #左から1番目
            for last1 in range(4):
                #条件に当てはまるものないときはcontinue
                if dp[l][last3][last2][last1] == 0: 
                    continue
                #追加する文字
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1: continue
                    if last2 == 0 and last1 == 1 and now == 2: continue
                    if last2 == 2 and last1 == 0 and now == 1: continue
                    if last3 == 0 and last1 == 2 and now == 1: continue
                    if last3 == 0 and last2 == 2 and now == 1: continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD

#長さNの全部の答えを回収する
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:
import sys
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7

N = int(input())

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

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

#Tは制約に入らないので、スタートをTTT+Sみたいな感じに考える。
dp[0][3][3][3] = 1

for l in range(N):
    #左から3番目
    for last3 in range(4):
        #左から2番目
        for last2 in range(4):
            #左から1番目
            for last1 in range(4):
                #条件に当てはまるものないときはcontinue
                # if dp[l][i][j][k] == 0: 
                #     continue
                #追加する文字
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1: continue
                    if last2 == 0 and last1 == 1 and now == 2: continue
                    if last2 == 2 and last1 == 0 and now == 1: continue
                    if last3 == 0 and last1 == 2 and now == 1: continue
                    if last3 == 0 and last2 == 2 and now == 1: continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD

#長さNの全部の答えを回収する
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:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

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
@lru_cache(None)
def dfs(cur,last3):
#    if last3 in memo[cur]:
 #       return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
  #  memo[cur][last3] = ret
    return ret
print(dfs(0,'   '))

Submission status: Accepted

Solution code:
n=int(input())
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
        #t[i-1],t[i]=t[i],t[i-1]
        
    return True

mod=10**9+7

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1
    ret=0
    for i in 'ACGT':
        if ok(last3+i):
            ret=(ret+dfs(cur+1,last3[1:]+i))%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 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 i in 'ACGT':
        if ok(last3 + i):
            ret = (ret + dfs(cur+1,last3[1:]+i)) % mod
    memo[cur][last3] = ret
    return ret
print(dfs(0,'   '))

Submission status: Accepted

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

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

for i in range(n):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for nxt in range(4):
                    if nxt == 3 and c1 == 2 and c2 == 1: continue
                    if nxt == 2 and c1 == 3 and c2 == 1: continue
                    if nxt == 3 and c1 == 1 and c2 == 2: continue
                    if nxt == 3 and c2 == 2 and c3 == 1: continue
                    if nxt == 3 and c1 == 2 and c3 == 1: continue
                    dp[i+1][nxt][c1][c2] += dp[i][c1][c2][c3]
                    dp[i+1][nxt][c1][c2] %= 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
memo=[{} for i in range(n+1)]
def ok(last4):
  for i in range(4):
    tmp=list(last4)
    if i>=1:
      tmp[i-1],tmp[i]=tmp[i],tmp[i-1]
    if ''.join(tmp).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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    N = int(input())

    #dp[i]:[..]左からi文字目がA,C,G,Tの場合の数
    dp = [[0]*4 for _ in range(N+1)]
    dp[1] = [1]*4
    for i in range(1,N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1])
            dp[i][j] %= mod
        #3文字見る
        if i >= 2:
            dp[i][1] -= dp[i-2][0]*1 + dp[i-2][2]*1
            dp[i][2] -= dp[i-2][0]*1
        #4文字見る
        if i >= 3:
            #ACGC ATGC AGGCで×3
            dp[i][1] -= dp[i-3][0]*3
            #GACGはそもそも足してないので余計に引いた分足す
            dp[i][2] += dp[i-3][2]*1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(str):
    global AGC
    if len(str)==3:
        AGC.append(str)
    else:
        dfs(str+'A')
        dfs(str+'G')
        dfs(str+'C')
        dfs(str+'T')


moji=['A','G','C','T']
AGC=[]
dfs('')
ban=[]
for str in moji:
    ban.append(str+'AGC')
    ban.append(str+'ACG')
    ban.append(str+'GAC')
    ban.append('AGC'+str)
    ban.append('ACG'+str)
    ban.append('GAC'+str)
    ban.append('AG'+str+'C')
    ban.append('A'+str+'GC')

ban=list(set(ban))

N=int(input())
mod=10**9+7
dp=[{key:0 for key in AGC} for i in range(0,N+1)]
for key in AGC:
    if key!='AGC' and key!='ACG' and key!='GAC':
        dp[3][key]=1

for i in range(3,N):
    for key in AGC:
        ans=0
        for str in moji:
            if not key+str in ban:
                dp[i+1][key[1:]+str]+=dp[i][key]

print(sum(dp[N][key] for key in AGC)%mod)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(input())
    states = [s + t + u for s in 'ACGT' for t in 'ACGT' for u in 'ACGT']
    states.remove('AGC')
    states.remove('ACG')
    states.remove('GAC')
    transitions = defaultdict(list)
    ngs = []
    for s in 'ACGT':
        for t in 'ACGT':
            for u in 'ACGT':
                for v in 'ACGT':
                    if 'AGC' in s + t + u + v or 'AGC' in t + s + u + v or 'AGC' in s + u + t + v or 'AGC' in s + t + v + u:
                        ngs.append(s + t + u + v)
    for s in states:
        for t in states:
            if s[1:] == t[:2] and s[0] + t not in ngs:
                transitions[s].append(t)
    count = {s: 1 for s in states}
    for _ in range(N - 3):
        updated = {s: 0 for s in states}
        for fr, tos in transitions.items():
            for to in tos:
                updated[to] += count[fr]
                updated[to] %= 10 ** 9 + 7
        count = updated
    print(sum(count.values()) % (10 ** 9 + 7))

main()

Submission status: Accepted

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

def DFS(i, w):
    if w in memo[i]:
        return memo[i][w]
    if i == N:
        return 1
    
    ans = 0
    for c in 'ACGT':
        if w + c not in NG:
            ans = (ans + DFS(i+1, w[1:] + c)) % MOD
    memo[i][w] = ans
    return ans

if N == 3:
    print(61)
else:
    ans, NG = 0, set(['AGGC', 'ATGC', 'AGTC'])
    for w in ['AGC', 'GAC', 'ACG']:
        for c in 'ACGT':
            NG.add(c+w)
            NG.add(w+c)
    for w in [x+y+z for x in 'ACGT' for y in 'ACGT' for z in 'ACGT' if x+y+z not in ['AGC', 'GAC', 'ACG']]:
        ans = (ans + DFS(3, w)) % MOD
    print(ans)

Submission status: Accepted

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

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

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

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

if n == 3:
    ans = 0
    for i in dp[-1]:
        for j in i:
            for k in j:
                ans += k
    print(ans)
    sys.exit()

for i in range(4, n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if (j == 0 and k == 1 and l == 2) or (j == 1 and k == 0 and l == 2) or (j == 0 and k == 2 and l == 1):
                    dp[i][j][k][l] = 0
                    continue
                if l != 2:
                    dp[i][j][k][l] = sum([dp[i - 1][x][j][k] for x in range(4)])
                    dp[i][j][k][l] %= mod
                    continue
                dp[i][j][k][l] = sum([dp[i - 1][x][j][k] for x in range(4)])
                dp[i][j][k][l] %= mod

                if l == 2 and k == 1:
                    dp[i][j][k][l] -= dp[i - 1][0][j][1]
                    dp[i][j][k][l] %= mod
                
                if l == 2 and j == 1:
                    dp[i][j][k][l] -= dp[i - 1][0][1][k]
                    dp[i][j][k][l] %= mod
                
                if l == 2 and j == 1 and k == 1:
                    dp[i][j][k][l] += dp[i - 1][0][1][1]
                    dp[i][j][k][l] %= mod


ans = 0
for i in dp[-1]:
    for j in i:
        for k in j:
            ans += k
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

N = int(input())
MOD = 10**9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])

for s in S:
    M.add(s + 'AGC')
    M.add(s + 'GAC')
    M.add(s + 'ACG')
    M.add('A' + s + 'GC')
    M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
    if length >= N:
        return 1

    ret = 0

    for s in S:
        T = prev + s
        if not T in M:
            T = T[:: -1][: 3][:: -1]
            ret += search(T, length + 1)
    return ret

ans = search('', 0) % MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
dp=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[3][i][j][k]=1
dp[3][0][2][1]=0
dp[3][0][1][2]=0
dp[3][2][0][1]=0
for i in range(4,n+1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        for m in range(4):
          dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][m][j][k])%mod
          if m==0 and k==2 and l==1:
            dp[i][j][k][l]=0
          if m==0 and j==2 and l==1:
            dp[i][j][k][l]=0
  dp[i][0][2][1]=0
  dp[i][0][1][2]=0
  dp[i][2][0][1]=0
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 main():
    from functools import lru_cache
    N = int(input())
    MOD = 10**9 + 7

    def is_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

    @lru_cache(maxsize=10000)
    def dfs(cur, last3):
        if cur == N:
            return 1
        ret = 0
        for c in "AGCT":
            if is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    N = int(input())
    MOD = 10**9 + 7

    def is_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

    @lru_cache(maxsize=1000)
    def dfs(cur, last3):
        if cur == N:
            return 1
        ret = 0
        for c in "AGCT":
            if is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def is_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 is_ok(last3 + c):
                ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
        memo[cur][last3] = ret
        return ret

    print(dfs(0, "TTT"))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

N = int(input())
MOD = 10**9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])

for s in S:
    M.add(s + 'AGC')
    M.add(s + 'GAC')
    M.add(s + 'ACG')
    M.add('A' + s + 'GC')
    M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
    if length >= N:
        return 1

    ret = 0

    for s in S:
        T = prev + s
        if not T in M:
            T = T[:: -1][: 3][:: -1]
            ret += search(T, length + 1)
    return ret % MOD

ans = search('', 0)
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def no_agc(last4):
    for i in range(4):
        cp_last4 = list(last4)
        if i >= 1:
            cp_last4[i-1], cp_last4[i] = cp_last4[i], cp_last4[i-1]
        #ここ
        cp_last4_sent = "".join(cp_last4)
            # print(cp_last4_sent)
        if cp_last4_sent.count("AGC") >= 1:
            return False
    return True

# print(no_agc("ACGT"))
N = INT()
ans = 0
memo = [{} for i in range(N+1)]
def dfs(idx, last3):
    if last3 in memo[idx]:
        return memo[idx][last3]
    if idx == N:
        return 1
    ret = 0
    for c in "ACGT":
        # sent = last3 + c
        if no_agc(last3 + c):
            ret = (ret + dfs(idx+1, (last3 + c)[1:])) % mod
    memo[idx][last3] = ret
    return ret
            # print(sent[idx:])
            # print(sent[idx+1:idx+4])
            # ans += dfs(idx+1, sent[idx+1:idx+4])

# 先頭から0
print(dfs(0, "TTT"))
# print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
dp = [[[[0, 0, 0, 0] for _ in range(4)] for _ in range(4)] for _ in range(n - 2)] #a,c,g,t
arr = [[0, 2, 1], [0, 1, 2], [2, 0, 1]]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if not [i, j, k] in arr:
                dp[0][i][j][k] = 1

arr2 = [[0, 2, 2, 1], [0, 3, 2, 1], [0, 2, 3, 1], [0, 2, 2, 1]]
for nn in range(1, n - 2):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not [i, j, k, l] in arr2 and not [j, k, l] in arr:
                        dp[nn][j][k][l] += dp[nn - 1][i][j][k]
                        dp[nn][j][k][l] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[n - 3][i][j][k]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10 ** 9 + 7

# dp[n][i][j][k]: str[n:n+3]で(i,j,k)となる個数
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N - 2)]

# 初期条件
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i == 0 and j == 1 and k == 2: # ACG
                continue
            if i == 0 and j == 2 and k == 1: # AGC
                continue
            if i == 2 and j == 0 and k == 1: # GAC
                continue
            dp[0][i][j][k] = 1

# 配るDP
for n in range(N - 3):
    for i in range(4):
        for j in range(4):
            for k in range(4):

                # c: 次の文字
                for c in range(4):
                    if j == 0 and k == 1 and c == 2: # ?ACG
                        continue
                    if j == 0 and k == 2 and c == 1: # ?AGC
                        continue
                    if j == 2 and k == 0 and c == 1: # ?GAC
                        continue
                    if i == 0 and k == 2 and c == 1: # A?GC
                        continue
                    if i == 0 and j == 2 and c == 1: # AG?C
                        continue

                    dp[n+1][j][k][c] = (dp[n+1][j][k][c] + dp[n][i][j][k]) % MOD

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[-1][i][j][k]) % 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)]
A,G,C,T = 0,1,2,3
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i,j,k) in [(A,G,C), (A,C,G), (G,A,C)]: continue
            dp[i][j][k] = 1

for _ in range(N-3):
    dp2 = [[[0]*4 for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in [(A,G,C), (A,C,G), (G,A,C)]: continue
                for l in range(4):
                    if (j,k,l) in [(A,G,C), (A,C,G), (G,A,C)]: continue
                    if (i,k,l) == (A,G,C) or (i,j,l) == (A,G,C): continue
                    dp2[j][k][l] += dp[i][j][k]
                    dp2[j][k][l] %= MOD
    dp = dp2

ans = 0
for row in dp:
    for row2 in row:
        ans += sum(row2)
print(ans%MOD)

Submission status: Accepted

Solution code:
n = int(input())
if n == 3:
    print(61)
    exit()
MOD = 10 ** 9 + 7
# dp[i][i-1][i-2][i-3][i-4]
dp = [[[[[0] * (4) for _ in range(4)] for i in range(4)] for i in range(4)] for i in range(n + 1)]

to = {0:"A", 1:"C", 2:"G", 3:"T"}
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue
                if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                dp[4][i1][i2][i3][i4] = 1

for i in range(4, n):
    for i1 in range(4):
        for i2 in range(4):
            for i3 in range(4):
                for i4 in range(4):
                    if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue
                    if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    for j in range(4):
                        dp[i + 1][i1][i2][i3][i4] += dp[i][i2][i3][i4][j]
                        dp[i + 1][i1][i2][i3][i4] %= MOD

ans = 0
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                ans += dp[-1][i1][i2][i3][i4]
                ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

dp=[[[[0]*5 for i in range(5)] for j in range(5)] for k in range(N+1)]
dp[0][0][0][0]=1
#A:1 G:2 C:3 T:4
#AGC GAC ACG
#A?GC AG?C
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                dp[n+1][j][k][1]+=dp[n][i][j][k]
                dp[n+1][j][k][2]+=0 if (j==1 and k==3) else dp[n][i][j][k]
                dp[n+1][j][k][3]+=0 if (i==1 and k==2) or (i==1 and j==2) or (j==1 and k==2) or (j==2 and k==1) else dp[n][i][j][k]
                dp[n+1][j][k][4]+=dp[n][i][j][k]
ans=0
for item in dp[N]:
    for jtem in item:
        ans+=sum(jtem)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 1000000007

N = int(input())

S = ['A', 'C', 'G', 'T']
T = []

for i in range(4):
    for j in range(4):
        for k in range(4):
            s = S[i] + S[j] + S[k]
            T.append(s)

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

for j in range(64):
    sj = T[j]
    if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
        continue
    dp[2][j] = 1

for i in range(3, N):
    for j in range(64):
        sj = T[j]
        if sj == 'GAC' or sj == 'ACG' or sj == 'AGC':
            continue
        for k in range(64):
            sk = T[k]
            if sj[2] == 'C' and sk[0] == 'A' and sk[2] == 'G':
                continue
            if sj[2] == 'C' and sk[:2] == 'AG':
                continue
            if sj[:2] == sk[1:]:
                dp[i][j] += dp[i - 1][k]
                dp[i][j] %= MOD

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

Submission status: Accepted

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

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

N = INT()

# last4 の文字列
def no_agc_is(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            # swap
            t[i-1], t[i] = t[i], t[i-1]
        # 4charでできた文字列中にAGCがあればfalse
        if "".join(t).count("AGC") >= 1:
            return False
    return True

# 0, 1, 2, 3
memo = [{} for i in range(N+1)]
# memo[0] = {}
# memo[0] = {"TTT": 4}とか
# memo[1]
def dfs(cur, last3):
    # cur, last3 = q.pop()
    # 同じやつあったらメモした奴呼び出し
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in "ACGT":
        if no_agc_is(last3 + c):
            ret = (ret + dfs(cur + 1, (last3 + c)[1:])) % mod
    memo[cur][last3] = ret
    return ret
print(dfs(0, "TTT"))