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 = sys.stdin.readline

def main():
    N = int(input())
    dp = [[0] * 4 if i != 3 else [1] * 4 for i in range(N+3)]
    MOD = int(1e9) + 7
    for i in range(4, N+3):
        sum_pre = sum(dp[i-1]) % MOD
        # A
        dp[i][0] = sum_pre
        # C
        dp[i][1] = (sum_pre - dp[i-2][0] - dp[i-2][2] - dp[i-3][0] * 3) % MOD
        # G
        dp[i][2] = (sum_pre - dp[i-2][0] + dp[i-3][2]) % MOD
        # T
        dp[i][3] = sum_pre
    print(sum(dp[-1]) % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
dp = [[[[0 for _ in range(n+1)] for _ in range(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 == 0 and j == 1 and k == 2) or (i == 0 and j == 2 and k == 1) or (i == 1 and j == 0 and k == 2)):
        pass
      else:
        dp[i][j][k][3] = 1
        
for length in range(3, n):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if(j == 0 and k == 2):
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][2][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
        elif((i == 0 and k == 1) or (i == 0 and j == 1) or (j == 0 and k == 1) or (j == 1 and k == 0)):
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][1][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
        else:
          dp[j][k][0][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][1][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][2][length + 1] += (dp[i][j][k][length])%mod
          dp[j][k][3][length + 1] += (dp[i][j][k][length])%mod
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += dp[i][j][k][n]
      
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
now = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)]
now[3][3][3][3] = 1
for _ in range(n):
  last = now
  now = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          for m in range(4):
            now[j][k][l][m] += last[i][j][k][l]
            now[j][k][l][m] %= mod
  for h in range(4):
    now[h][0][1][2] = 0
    now[h][1][0][2] = 0
    now[h][0][2][1] = 0
    now[0][h][1][2] = 0
    now[0][1][h][2] = 0
ans = 0
for j in range(4):
  for k in range(4):
    for l in range(4):
      for m in range(4):
        ans += now[j][k][l][m]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    N=int(input())
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    # initialize(n=3)
    NG={(0,1,2),(1,0,2),(0,2,1)}
    from itertools import product
    for i,j,k in product(range(4),repeat=3):
        if (i,j,k) in NG: continue
        dp[3][i][j][k]=1
    # iterate
    for n in range(4,N+1):
        for i,j,k,l in product(range(4),repeat=4):
            if dp[n-1][i][j][k]==0: continue
            if (j,k,l) in NG: continue
            if (i,j,l)==(0,1,2): continue
            if (i,k,l)==(0,1,2): continue
            dp[n][j][k][l]+=dp[n-1][i][j][k]
            dp[n][j][k][l]%=MOD
    # calculate
    ans=0
    for i,j,k in product(range(4),repeat=3):
        ans+=dp[N][i][j][k]
    print(ans%MOD)

resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    N=int(input())
    dp=[[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    # initialize(n=3)
    NG={(0,1,2),(1,0,2),(0,2,1)}
    from itertools import product
    for i,j,k in product(range(4),repeat=3):
        if (i,j,k) in NG: continue
        dp[3][i][j][k]=1
    # iterate
    for n in range(4,N+1):
        for i,j,k,l in product(range(4),repeat=4):
            if dp[n-1][i][j][k]==0: continue
            if (j,k,l) in NG: continue
            if (i,j,l)==(0,1,2): continue
            if (i,k,l)==(0,1,2): continue
            dp[n][j][k][l]+=dp[n-1][i][j][k]
    # calculate
    ans=0
    for i,j,k in product(range(4),repeat=3):
        ans+=dp[N][i][j][k]
    print(ans%MOD)

resolve()

Submission status: Accepted

Solution code:
import functools
import itertools
import collections

l = list("ACGT")

@functools.lru_cache(maxsize=None)
def f(d, sl, e):
    if e == d:
        return 1
    else:
        cnt = 0
        for v in l:
            tsl = collections.deque(sl)
            if len(sl) == 4:
                tsl.popleft()
            tsl.append(v)
            ts = "".join(tsl)
            if len(ts) >= 3 and (ts[-3:] == "AGC" or ts[-3:] == "GAC" or ts[-3:] == "ACG"):
                continue
            if len(ts) >= 4 and ts[0] == "A" and ts[2:] == "GC":
                continue
            if len(ts) >= 4 and ts[:2] == "AG" and ts[3] == "C":
                continue
            cnt += f(d + 1, ts, e)
        return cnt


def slove():
    import sys
    input = sys.stdin.readline
    e = int(input().rstrip('\n'))
    sl = []
    print(f(0, "".join(sl), e) % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
#18:20
n = int(input())
mod = 10 ** 9 + 7
now = [[[[0 for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
now[3][3][3][3] = 1
for _ in range(n):
  last = now
  now = [[[[0 for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          for m in range(4):
            now[j][k][l][m] += last[i][j][k][l]
            now[j][k][l][m] %= mod
  for j in range(4):
    now[j][0][1][2] = 0
    now[j][1][0][2] = 0
    now[j][0][2][1] = 0
  for k in range(4):
    now[0][k][1][2] = 0
  for l in range(4):
    now[0][1][l][2] = 0
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        ans += now[i][j][k][l]
print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())

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

# dp[i][j][k][l]
# iは文字列の長さ
# j,k,lは最後から1,2,3文字目の文字に対応(A,G,C,Tを0,1,2,3にあてた)

# 長さ0の文字列は1通り
dp[0][3][3][3] = 1
MOD = 10**9 + 7

for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                #if dp[i][j][k][l] == 0: # 条件に当てはまるものがない場合はcontinue(これはなくてもok)
                    #continue
                for add in range(4): # (i+1)文字目として新しく追加する文字
                    # ダメな5つの条件を捨てる
                    if add == 2 and j == 1 and k == 0:
                        continue
                    if add == 2 and j == 0 and k == 1:
                        continue
                    if add == 1 and j == 2 and k == 0:
                        continue
                    if add == 2 and j == 1 and l == 0:
                        continue
                    if add == 2 and k == 1 and l == 0:
                        continue
                    # ダメな条件を抜けたらaddをi+1番目に足した文字列の個数として数える
                    # S = ...j,k,l から S = ...j,k,l,add へ
                    dp[i+1][add][j][k] += dp[i][j][k][l]
                    dp[i+1][add][j][k] %= MOD

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

# dp[i][j][k][l]
# iは文字列の長さ
# j,k,lは最後から1,2,3文字目の文字に対応(A,G,C,Tを0,1,2,3にあてた)

# 長さ0の文字列は1通り
dp[0][3][3][3] = 1
MOD = 10**9 + 7

for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[i][j][k][l] == 0: # 条件に当てはまるものがない場合はcontinue(これはなくてもok)
                    continue
                for add in range(4): # (i+1)文字目として新しく追加する文字
                    # ダメな5つの条件を捨てる
                    if add == 2 and j == 1 and k == 0:
                        continue
                    if add == 2 and j == 0 and k == 1:
                        continue
                    if add == 1 and j == 2 and k == 0:
                        continue
                    if add == 2 and j == 1 and l == 0:
                        continue
                    if add == 2 and k == 1 and l == 0:
                        continue
                    # ダメな条件を抜けたらaddをi+1番目に足した文字列の個数として数える
                    # S = ...j,k,l から S = ...j,k,l,add へ
                    dp[i+1][add][j][k] += dp[i][j][k][l]
                    dp[i+1][add][j][k] %= MOD

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

print(ans)

Submission status: Accepted

Solution code:
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = list(map(lambda pat: re.compile(pat), [r"AGC", r"GAC", r"ACG", r"A.GC", r"AG.C"]))
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: ch.search(now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: ch.search(now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = list(map(lambda pat: re.compile(pat), [r".*AGC", r".*GAC", r".*ACG", r".*A.GC", r".*AG.C"]))
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: ch.match(now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: ch.match(now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

MOD = int(1e9) + 7

acgt = ["A", "C", "G", "T"]
changed = [".*AGC", ".*GAC", ".*ACG", ".*A.GC", ".*AG.C"]
abcl = [ a+b+c for a in acgt for b in acgt for c in acgt]

dp = {}
for now in abcl:
    if any(map(lambda ch: re.match(ch, now), changed)):
        dp[now] = 0
    else:
        dp[now] = 1

N -= 3

while N > 0:
    dpNow = {}
    for abc in abcl:
        abc = abc[:min(N, 3)]
        dpNow[abc] = 0
        for key, value in dp.items():
            now = key + abc
            if not any(map(lambda ch: re.match(ch, now), changed)):
                dpNow[abc] += value
                dpNow[abc] %= MOD
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

acgt = ["A", "C", "G", "T"]
changed = [".*AGC", ".*GAC", ".*ACG", ".*A.GC", ".*AG.C"]


# initialize
dp = {}
for a in acgt:
    for b in acgt:
        for c in acgt:
            now = a+b+c
            
            if any(map(lambda ch: re.match(ch, now), changed)):
                dp[now] = 0
            else:
                dp[now] = 1

N -= 3

MOD = int(1e9) + 7
# main
while N > 0:
    dpNow = {}
    for a in acgt:
        for b in acgt:
            for c in acgt:
                abc = (a + b + c)[:min(N, 3)]
                dpNow[abc] = 0
                for key, value in dp.items():
                    now = key + abc

                    if not any(map(lambda ch: re.match(ch, now), changed)):
                        dpNow[abc] += value
                        dpNow[abc] %= MOD
                        
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import re

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())

acgt = ["A", "C", "G", "T"]
changed = [".*GAC.*", ".*ACG.*", ".*A.GC.*", ".*AG.C.*"]
bad = ".*AGC"


# initialize
dp = {}
for a in acgt:
    for b in acgt:
        for c in acgt:
            now = a+b+c
            
            if re.match(bad, now):
                dp[now] = 0
            elif any(map(lambda ch: re.match(ch, now), changed)):
                dp[now] = 0
            else:
                dp[now] = 1

N -= 3

MOD = int(1e9) + 7
# main
while N > 0:
    dpNow = {}
    for a in acgt:
        for b in acgt:
            for c in acgt:
                abc = (a + b + c)[:min(N, 3)]
                dpNow[abc] = 0
                for key, value in dp.items():
                    now = key + abc

                    if re.match(bad, now):
                        ()
                    elif any(map(lambda ch: re.match(ch, now), changed)):
                        ()
                    else:
                        dpNow[abc] += value
                        dpNow[abc] %= MOD
                        
    dp = dpNow
    N -= 3

ans = 0
for v in dp.values():
    ans += v
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env py

log = lambda *x: print(*x)

def no_c(f,s,t):
    if f==1 and t==2: return True
    if f==1 and s==2: return True
    if s==1 and t==2: return True
    if s==2 and t==1: return True
    return False

def no_g(f,s,t):
    if s==1 and t==3: return True
    return False

def solve(k):
    dp = [[ [([0]*5) for i in range(5)] for i in range(5) ] for i in range(k+1)]

    for l in range(k, 0, -1):
        for f in range(0,5):
            for s in range(0,5):
                for t in range(0,5):
                    if l == k:
                        dp[l][f][s][t] = 1
                        continue

                    if l == 1:
                        dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

                    if l == 2:
                        if (s==1 and t==2) or (s==2 and t==1): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][4]
                        if (s==1 and t==3): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][3] + dp[l+1][s][t][4]
                        else: dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

                    if no_c(f,s,t): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][4]
                    elif no_g(f,s,t): dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][3] + dp[l+1][s][t][4]
                    else: dp[l][f][s][t] = dp[l+1][s][t][1] + dp[l+1][s][t][2] + dp[l+1][s][t][3] + dp[l+1][s][t][4]

    return sum(dp[1][0][0][t] for t in (1,2,3,4)) % 1000000007

log(solve(int(input())))

Submission status: Accepted

Solution code:
N = int(input())
mod = 10 ** 9 + 7
memo = [{} for i in range(N + 1)]
#最新の４文字について、隣接２文字の入れ替えをしてもAGCは現れないかどうか
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
  #ACGTのうち１文字を末尾に加える
  for c in 'ACGT':
    #checkを通ったのなら、retに次の文字列の個数を加算
    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:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main_old(): 
    N = II()
    
    dp = {'a': [1,1,4,16] + [0 for _ in range(N)],
    't': [1,1,4,16] + [0 for _ in range(N)],
    'g': [1,1,4,15] + [0 for _ in range(N)],
    'c': [1,1,4,14] + [0 for _ in range(N)]
    }

    codons = ['a', 't', 'g', 'c']

    # if N < 5:
    # for i in range(4, N+1):
    #     dp['a'][i] = dp['a'][i-1] +  dp['t'][i-1] +  dp['g'][i-1] +  dp['c'][i-1]
    #     dp['t'][i] = dp['a'][i-1] +  dp['t'][i-1] +  dp['g'][i-1] +  dp['c'][i-1]
    #     dp['g'][i] = dp['a'][i-2] * 3 + dp['t'][i-2] * 4 + dp['g'][i-2] * 4 + dp['c'][i-2] * 4
    #     dp['c'][i] = dp['a'][i-3] * 9 + dp['t'][i-3] * 12 + dp['g'][i-3] * 11 + dp['c'][i-3] * 12
    for i in range(4, N+1):
        dp['a'][i] = dp['a'][i-3] * 14 + dp['t'][i-3] * 16 + dp['g'][i-3] * 15 + dp['c'][i-3] * 16
        dp['t'][i] = dp['a'][i-3] * 14 + dp['t'][i-3] * 16 + dp['g'][i-3] * 15 + dp['c'][i-3] * 16
        dp['g'][i] = dp['a'][i-3] * 13 + dp['t'][i-3] * 15 + dp['g'][i-3] * 15 + dp['c'][i-3] * 15
        dp['c'][i] = dp['a'][i-3] * 9 + dp['t'][i-3] * 14 + dp['g'][i-3] * 13 + dp['c'][i-3] * 14

    sum_ = 0
    for x in codons:
        sum_ += dp[x][N] % MOD
    print(sum_ % MOD)
    return

def is_valid(s):
    if s[0:3] == 'AGC' or s[0]+s[2:4] == 'AGC' or s[0:2] + s[3] == 'AGC' or s[1:4] == 'AGC' or s.count('GAC') > 0 or s.count('ACG') > 0:
        return False
    else:
        return True

def main(): 
    N = II()

    if N == 3:
        print(61)
        return
    
    import collections
    dp = collections.defaultdict(int)
    import itertools
    for st in itertools.product('AGCT', repeat=4):
        st = ''.join(st)
        if is_valid(st):
            dp[st] = 1
        else:
            dp[st] = 0

    for i in range(4, N):
        dp2 = collections.defaultdict(int)
        for st in itertools.product('AGCT', repeat=4):
            st = ''.join(st)
            for char in 'AGCT':
                nex = st[1:4] + char
                if is_valid(nex):
                    dp2[nex] = (dp2[nex] + dp[st])%MOD
                else:
                    pass
        dp = dp2

    sum_ = 0
    for st in itertools.product('AGCT', repeat=4):
        st = ''.join(st)
        sum_ = (sum_ + dp[st])%MOD
    print(sum_)

main()

Submission status: Accepted

Solution code:
n = int(input())
aa = [1]
ac = [1]
ag = [1]
cc = [1]
cg = [1]
ca = [1]
gc = [1]
ga = [1]
gg = [1]
at = [1]
gt = [1]
t = [2]
ta = [1]
tc = [1]
tg = [1]
mod = 10**9 + 7
for i in range(n-2):
    ac.append((ca[i]+ta[i]+aa[i])%mod)
    ag.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    cg.append((cc[i]+gc[i]+tc[i])%mod)
    aa.append((ca[i]+aa[i]+ga[i]+ta[i])%mod)
    cc.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    ca.append((ac[i]+cc[i]+gc[i]+tc[i])%mod)
    if i > 0:
        gc.append((cg[i]+gg[i]+tg[i]-ag[i-1]-at[i-1])%mod)
    else:
        gc.append((cg[i]+gg[i]+tg[i])%mod)
    ga.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    gg.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    at.append((ca[i]+ga[i]+ta[i]+aa[i])%mod)
    gt.append((cg[i]+gg[i]+tg[i]+ag[i])%mod)
    t.append((ac[i]+cc[i]+gc[i]+tc[i]+t[i]+at[i]+gt[i])%mod)
    ta.append(t[i]+at[i]+gt[i])
    if i > 0:
        tc.append(t[i]+at[i]+gt[i]-ag[i-1])
    else:
        tc.append(t[i]+at[i]+gt[i])
    tg.append(t[i]+at[i]+gt[i])
ans = 0
ans = (aa[n-2]+ac[n-2]+ag[n-2]+cc[n-2]+cg[n-2]+ca[n-2]+gc[n-2]+ga[n-2]+gg[n-2]+t[n-2]+ta[n-2]+tc[n-2]+tg[n-2]+at[n-2]+gt[n-2])%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

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

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

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

def rec(cur, s):
    if s in memo[cur]:
        return memo[cur][s]
    if cur==N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(s+c):
            ret = (ret + rec(cur+1, s[-2:]+c))%mod
    memo[cur][s] = ret
    return ret

print(rec(0,'TTT'))

Submission status: Accepted

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

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

def dfs(cur, last3):
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == N:
    return 1
  ret = 0
  for c in 'ACGT':
    if ok(last3 + c):
      ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
  memo[cur][last3] = ret
  return ret
    
print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
dp = [[0] * 4 for _ in range(n)]

# A / C / G / T
dp[0] = [1, 1, 1, 1]
dp[1] = [4, 4, 4, 4]
# AGC, ACG, GAC, A?GC,AG?C -> AGGC, ATGC,AGTC

for i in range(2, n):
    if i == 2:
        dp[i][0] = dp[i - 1][0] * 4
        dp[i][1] = dp[i - 1][1] * 4 - 2
        dp[i][2] = dp[i - 1][2] * 4 - 1
        dp[i][3] = dp[i - 1][3] * 4
    else:
        dp[i][0] = sum(dp[i - 1])
        # -AGC -CAG -A**C
        dp[i][1] = sum(dp[i - 1]) - dp[i - 2][0] - dp[i - 2][2] - dp[i - 3][0] * 3
        # -ACG
        dp[i][2] = sum(dp[i - 1]) - dp[i - 2][0] + dp[i - 3][2]
        dp[i][3] = sum(dp[i - 1])


print(sum(dp[n - 1]) % mod)

Submission status: Accepted

Solution code:
from itertools import product
from functools import lru_cache
n = int(input())
mod = 10**9+7
condition = True

@lru_cache(64*n)
def func(tpl, count) :
    if tpl in (("A","G","C"), ("A","C","G"), ("G","A","C")) :
        return 0
    if count :
        count -= 1
        if tpl[1:] == ("A","G") :
            return sum(func(("A","G",c), count) for c in "AGT")%mod
        if tpl[1:] == ("A","C") :
            return sum(func(("A","C",c), count) for c in "ACT")%mod
        if tpl[1:] == ("G","A") :
            return sum(func(("G","A",c), count) for c in "AGT")%mod
        if tpl[:2] == ("A","G") :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        if tpl[0]+tpl[2] == "AG" :
            return sum(func(tpl[1:]+(c,), count) for c in "AGT")%mod
        return sum(func(tpl[1:]+(c,), count) for c in "ACGT")%mod
    return 1

ans = 0
for firstthree in product("ACGT", repeat=3) :
    ans = (ans+func(firstthree, n-3))%mod
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 j in range(4)
    ]

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

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
                    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:
import re

N = int(input())

memo = dict()


def is_agc(text):
    if re.match("(.agc|.acg|.gac|a.gc|ag.c)", text):
        return True
    return False


def dfs(s, m):
    if (s, m) in memo:
        return memo[(s, m)]
    if m == N:
        return 1

    count = 0
    for c in "acgt":
        t = s + c
        if is_agc(t):
            continue
        count += dfs(t[-3:], m+1)

    # print(s, m, count)
    memo[(s, m)] = count % (10**9+7)
    return memo[(s, m)]


print(dfs("ttt", 0))
# print(memo)

Submission status: Accepted

Solution code:
n, MOD = int(input()), 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], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in "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:
def main():
    #import sys
    #input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    mod = 10**9+7
    
    A = [defaultdict(int) for i in range(N)]
    helix = ["A","T","C","G"]
    out = ["AGC","GAC","ACG"]
    for i in helix:
        for j in helix:
            for k in helix:
                s = i+j+k
                if not s in out:
                    A[2][s] = 1
    for n in range(N-3):
        for i in helix:
            for j in helix:
                for k in helix:
                    m = n+3
                    s = i+j+k
                    if not s in out:
                        for l in helix:
                            t = l+i+j
                            if (not t in helix) and (not (k=="C" and (l+j=="AG" or i+j=="GA" or l+i=="AG"))) and (not (k=="G" and (i+j=="AC"))):
                                A[m][s] += A[m-1][t]
                                A[m][s] %= mod
    answer = 0
    for i in helix:
        for j in helix:
            for k in helix:
                s = i+j+k
                if not s in out:
                    answer += A[N-1][s]
                    answer %= mod
    print(answer)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
mod = 10**9 + 7
DP = [defaultdict(int) for _ in range(n+1)]
DP[0]['TTT'] = 1

for length in range(n):
    for seq, count in DP[length].items():

        if seq[1:] in ['AG', 'GA'] or seq[:2] == 'AG' or seq[0]+seq[2] == 'AG':
            for ns in 'AGT':
                new_seq = seq[1:] + ns
                DP[length+1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        elif seq[1:] == 'AC':
            for ns in 'ACT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

        else:
            for ns in 'ACGT':
                new_seq = seq[1:] + ns
                DP[length + 1][new_seq] += count
                DP[length + 1][new_seq] %= mod

ans = sum(DP[n].values()) % mod
print(ans)

Submission status: Accepted

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


N = int(input())
mod=1e+9 +7
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
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 a in range(4):
                    if c2==0 and c3==1 and a==2: continue
                    if c2==0 and c3==2 and a==1: continue
                    if c2==1 and c3==0 and a==2: continue
                    if c1==0 and c3==1 and a==2: continue
                    if c1==0 and c2==1 and a==2: continue
                    dp[len+1][c2][c3][a]+=dp[len][c1][c2][c3]
                    dp[len+1][c2][c3][a]%=mod
ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[N][i][j][k]
            ans%=mod
print(int(ans))