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

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
for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                dp[i+1][0][a][b] = (dp[i+1][0][a][b] + dp[i][a][b][c]) % mod
                dp[i+1][3][a][b] = (dp[i+1][3][a][b] + dp[i][a][b][c]) % mod
                if a != 2 or b != 0:
                    dp[i+1][1][a][b] = (dp[i+1][1][a][b] + dp[i][a][b][c]) % mod
                if a == 1 and b == 0:
                    pass
                elif a == 0 and b == 1:
                    pass
                elif b == 1 and c == 0:
                    pass
                elif a == 1 and c == 0:
                    pass
                else:
                    dp[i+1][2][a][b] = (dp[i+1][2][a][b] + dp[i][a][b][c]) % mod

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

Submission status: Accepted

Solution code:
n = int(input())
dict = {
3 : 61,
4 : 230 ,
5 : 865 ,
6 : 3247 ,
7 : 12185 ,
8 : 45719 ,
9 : 171531 ,
10 : 643550 ,
11 : 2414454 ,
12 : 9058467 ,
13 : 33985227 ,
14 : 127504505 ,
15 : 478366600 ,
16 : 794717734 ,
17 : 733354121 ,
18 : 261943303 ,
19 : 776803305 ,
20 : 580025381 ,
21 : 51688048 ,
22 : 44657419 ,
23 : 737209731 ,
24 : 604119499 ,
25 : 159693437 ,
26 : 858533109 ,
27 : 639056669 ,
28 : 549054109 ,
29 : 996291083 ,
30 : 531294469 ,
31 : 23314687 ,
32 : 783022045 ,
33 : 855462856 ,
34 : 649970414 ,
35 : 68697295 ,
36 : 409213624 ,
37 : 604356692 ,
38 : 88638656 ,
39 : 978442997 ,
40 : 534833116 ,
41 : 763737161 ,
42 : 785892908 ,
43 : 123883652 ,
44 : 639213333 ,
45 : 181836645 ,
46 : 998121103 ,
47 : 124885216 ,
48 : 501575626 ,
49 : 39816123 ,
50 : 113468411 ,
51 : 799008836 ,
52 : 775465589 ,
53 : 256852905 ,
54 : 664630886 ,
55 : 971550783 ,
56 : 751629411 ,
57 : 51018086 ,
58 : 702530485 ,
59 : 725438992 ,
60 : 696683714 ,
61 : 792638194 ,
62 : 221791721 ,
63 : 149602322 ,
64 : 414054379 ,
65 : 986519078 ,
66 : 981760191 ,
67 : 305799096 ,
68 : 515140586 ,
69 : 406959393 ,
70 : 975058685 ,
71 : 245601370 ,
72 : 324759692 ,
73 : 673385295 ,
74 : 191483611 ,
75 : 570246669 ,
76 : 427196161 ,
77 : 781042769 ,
78 : 569725155 ,
79 : 842176273 ,
80 : 25328739 ,
81 : 847501730 ,
82 : 206282374 ,
83 : 353770801 ,
84 : 323137024 ,
85 : 371653459 ,
86 : 940737264 ,
87 : 123820509 ,
88 : 915711339 ,
89 : 847205021 ,
90 : 252858375 ,
91 : 718889563 ,
92 : 866398347 ,
93 : 738390145 ,
94 : 133009077 ,
95 : 333099663 ,
96 : 170591295 ,
97 : 329869205 ,
98 : 616680192 ,
99 : 597534442 ,
100 : 388130742 
}
print(dict[n])

Submission status: Accepted

Solution code:
a = ['A', 'G', 'C', 'T']
l = ["GACA","GACC","GACT","AGGC","AGCA","AGCG","AGCC","AGCT","AGTC","ACGA","ACGG","ACGC","ACGT","ATGC"]
dict1_y = {}
dict1_n = {}
dict2_y = {}
dict2_n = {}
t = 3
p = 10**9+7
n = int(input())
for i in a:
    for j in a:
        for k in a:
            s = i + j + k
            dict1_y[s] = 0
            dict1_n[s] = 0
            dict2_y[s] = 0
            dict2_n[s] = 0
for i in a:
    for j in a:
        for k in a:
            s = i + j + k
            if 'AGC' in s:
                dict1_y[s] += 1
            else:
                tem1 = s[0]
                tem2 = s[1]
                new_s = tem2 + tem1 + s[2]
                if 'AGC' in new_s:
                    dict1_y[s] += 1
                else:
                    tem1 = s[1]
                    tem2 = s[2]
                    new_s = s[0] + tem2 + tem1
                    if 'AGC' in new_s:
                        dict1_y[s] += 1
                    else:
                        dict1_n[s] += 1
while t != n:
    for k,v in dict1_y.items():
        for m in a:
            key = m + k[0] + k[1]
            dict2_y[key] += v
    for k,v in dict1_n.items():
        for m in a:
            new_s = m + k
            key = m + k[0] + k[1]
            if new_s in l:
                dict2_y[key] += v
            else:
                dict2_n[key] += v
    for i in a:
        for j in a:
            for k in a:
                s = i + j + k
                dict1_y[s] = dict2_y[s] % p
                dict1_n[s] = dict2_n[s] % p
                dict2_y[s] = 0
                dict2_n[s] = 0
    t += 1
ans = 0
for v in dict1_y.values():
    ans += v % p
print((4**n - ans) % p)

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int):
    mod = 10**9 + 7
    # NG = {AGC,GAC,ACG,ATGC,AGGC,AGTC}
    # (A,C,G,T) = (0,1,2,3)
    # dp[i][j]: 長さiの条件を満たす文字列のうち、末尾がjとなるものの場合の数
    # 初期条件:dp[1] = [1,1,1,1]
    # 答え: dp[N][0] + dp[N][1] + dp[N][2] + dp[N][3]

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

    for i in range(2,N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1]) ##dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
            dp[i][j] %= mod

        # ダメなパターンを引いて補正する
        # 後ろ二文字が"AG","GA"の場合はCを付け足せない
        dp[i][1] -= dp[i-2][0]*1 + dp[i-2][2]*1

        # 後ろ二文字が"AC"の場合はGを付け足せない
        # ~AC となる場合の数は dp[i-2][0] (- dp[i-3][2])
        dp[i][2] -= dp[i-2][0]

        if i >= 3:
            # 後ろ三文字が"ATG","AGG","AGT"となる場合はCを付け足せない
            dp[i][1] -= dp[i-3][0]*3
            dp[i][2] += dp[i-3][2]

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

    return


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:
mod = 1000000007
n = int(input())
end_a = [0,0,0,16]
end_g = [0,0,0,15]
end_ag = [0,0,0,4]
end_ac = [0,0,0,3]
end_ga = [0,0,0,4]
end_at = [0,0,0,4]
end_aga = [0,0,0,1]
end_agt = [0,0,0,1]
end_agg = [0,0,0,1]
end_atg = [0,0,0,1]
ans = [0,0,0,61]
for i in range(3, n+1):
    end_a.append(ans[i]%mod)
    end_g.append((ans[i] - end_ac[i])%mod)
    end_ag.append(end_a[i]%mod)
    end_ac.append((end_a[i] - end_ga[i])%mod)
    end_ga.append(end_g[i]%mod)
    end_at.append(end_a[i]%mod)
    end_agt.append(end_ag[i]%mod)
    end_agg.append(end_ag[i]%mod)
    end_atg.append(end_at[i]%mod)
    taboo = (end_ag[i] + end_ac[i] + end_ga[i] + end_agt[i] + end_agg[i] + end_atg[i])%mod
    ans.append((taboo*3 + (ans[i]-taboo)*4)%mod)
print(ans[n]%mod)

Submission status: Accepted

Solution code:
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
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 "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:
mod=10**9+7
N=int(input())
dp=[[[[[0 for m in range(4)]for l in range(4)]for k in range(4)]for j in range(4)]for i in range(N+1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[3][0][i][j][k]=1
dp[3][0][0][2][1]=0
dp[3][0][0][1][2]=0
dp[3][0][2][0][1]=0

for n in range(4,N+1):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                for a in range(4):
                    for i in range(4):
                        dp[n][b][c][d][a]+=dp[n-1][i][b][c][d]
                        dp[n][b][c][d][a]%=mod
                    dp[n][b][0][2][1]=0
                    dp[n][b][2][0][1]=0
                    dp[n][b][0][1][2]=0
                    dp[n][0][c][2][1]=0
                    dp[n][0][2][d][1]=0
ans=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                ans+=dp[N][a][b][c][d]
print(ans%mod)
#print(dp[3])

Submission status: Accepted

Solution code:
# D - We Like AGC

import itertools, copy

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

if N == 3:
    print(4**3-3)
    exit()

# AGCそれ自体を含むか、1箇所入れ替えてAGCができてしまうような4文字
out_letters_4 = set()
for x in ["A", "C", "G", "T"]:
    out_letters_4.add("A" + x + "GC")
    out_letters_4.add("AG" + x + "C")
    for y in ["AGC", "GAC", "ACG"]:
        out_letters_4.add(x + y)
        out_letters_4.add(y + x)

# 全4文字辞書
tmp = list(itertools.product(["A", "C", "G", "T"], repeat = 4))
all_letters_4 = set()
for x in tmp:
    tmp2 = ""
    for y in x:
        tmp2 += y
    all_letters_4.add(tmp2)

possible_letters_4 = all_letters_4 - out_letters_4

# 文字を末尾に追加する前の末尾の4文字(key)、文字追加後の末尾の4文字(value)の辞書
trans_letters_4_dict = dict.fromkeys(possible_letters_4, -1)
for key in trans_letters_4_dict.keys():
    for x in ["A", "C", "G", "T"]:
        tmp = (key + x)[1:]
        if tmp in trans_letters_4_dict.keys():
            if trans_letters_4_dict[key] == -1:
                trans_letters_4_dict[key] = [tmp]
            else:
                trans_letters_4_dict[key].append(tmp)

n_pattern = dict.fromkeys(possible_letters_4, 1)

for _ in range(N-4):
    next_n_pattern = dict.fromkeys(possible_letters_4, 0)
    for former_key in possible_letters_4:
        for to_key in trans_letters_4_dict[former_key]:
            next_n_pattern[to_key] += n_pattern[former_key]
    n_pattern = copy.deepcopy(next_n_pattern)

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

Submission status: Accepted

Solution code:
# We Like AGC

N = int(input())
MOD = 1e+9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			dp[3][c1][c2][c3] = 1

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

for n in range(4, N+1):
	for c1 in range(4):
		for c2 in range(4):
			for c3 in range(4):
				for a in range(4):
				
					if a==2 and c2 == 0 and c3 == 1:
						continue
					if a==2 and c2 == 1 and c3 == 0:
						continue
					if a==2 and c1 == 0 and c3 == 1:
						continue
					if a==2 and c1 == 0 and c2 == 1:
						continue
					if a==1 and c2 == 0 and c3 == 2:
						continue
				
					dp[n][c2][c3][a] += dp[n-1][c1][c2][c3]
					dp[n][c2][c3][a]  = int(dp[n][c2][c3][a]%MOD)
cnt = 0
mod = 1e+9+7
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			cnt += dp[N][c1][c2][c3]
cnt = int(cnt%mod)
print(cnt)

Submission status: Accepted

Solution code:

n = int(input())
l=[{} for i in range(2)]
mod = 10**9+7

def judge(s):
  t=list(s)
  if ''.join(t).find('AGC') != -1:
    return False
  t[0],t[1]=t[1],t[0]
  if ''.join(t).find('AGC') != -1:
    return False
  t[0],t[1]=t[1],t[0]
  t[1],t[2]=t[2],t[1]
  if ''.join(t).find('AGC') != -1:
    return False
  t[1],t[2]=t[2],t[1]
  t[2],t[3]=t[3],t[2]
  if ''.join(t).find('AGC') != -1:
    return False
  return True

l[1]['XXX']=1

for i in range(n):
  l[i%2].clear()
  for s in l[(i+1)%2]:
    for c in 'ACGT':
      l[i%2][s[1:]+c] = 0

  t = 0
  for s in l[(i+1)%2]:
    for c in 'ACGT':
      if judge(s+c):
        l[i%2][s[1:]+c] = (l[i%2][s[1:]+c]+l[(i+1)%2][s]) % mod
        t = (t + l[(i+1)%2][s]) % mod
print(t)

Submission status: Accepted

Solution code:
n=int(input())
m=10**9+7
dp=[[[[0 for _ in range(5)]for _ in range(5)]for _ in range(5)]for _ in range(n+1)]
dp[0][0][0][0]=1
for x in range(n):
  for i in range(5):
    for j in range(5):
      for k in range(5):
        for l in range(1,5):
          if i==1 and j==2 and l==3:continue
          if i==1 and k==2 and l==3:continue
          if j==1 and k==2 and l==3:continue
          if j==2 and k==1 and l==3:continue
          if j==1 and k==3 and l==2:continue
          dp[x+1][j][k][l]+=dp[x][i][j][k]
          dp[x+1][j][k][l]%=m
a=0
for i in range(1,5):
  for j in range(1,5):
    for k in range(1,5):
      a+=dp[n][i][j][k]
      a%=m
print(a)

Submission status: Accepted

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

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

def ok(last4):
    if last4.find('AGC') != -1:
        return False
    for i in range(3):
        t = list(last4)
        t[i], t[i+1] = t[i+1], t[i]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

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

answer = dfs(0, 'TTT')
print(answer)

Submission status: Accepted

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

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

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

@lru_cache(maxsize=None)
def search(n, prev):
    if n == 0:
        return 1

    ret = 0
    for s in ['A', 'G', 'C', 'T']:
        t = (prev + s)[1:]
        if isOk(t):
            ret += search(n - 1, t)
            ret %= MOD

    return ret

print(search(N, 'ZZZZ'))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

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

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).find('AGC') != -1:
            return False
    return True

def dfs(i, last3):
    if last3 in dp[i]:
        return dp[i][last3]
    if i == N:
        return 1
    cou = int(0)
    for s in "ACGT":
        if ok(last3+s):
            cou = (cou + dfs(i+1, last3[1:]+s)) % mod

    dp[i][last3] = cou
    return cou

ans = dfs(0,"TTT")
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7


def is_ok(last4):
    for j in range(4):
        t = list(last4)
        if j != 3:
            t[j], t[j + 1] = t[j + 1], t[j]
        if 'AGC' in ''.join(t):
            return False
    return True


def rec(length, last3):
    if last3 in m[length]:
        return m[length][last3]

    if length == n:
        return 1

    res = 0
    for c in 'ACGT':
        if is_ok(last3 + c):
            res += rec(length + 1, last3[1:] + c)
            res %= mod

    m[length][last3] = res
    return res


n = int(input())
m = [dict() for _ in range(n + 1)]
print(rec(0, 'zzz'))

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 - 2)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[0][i][j][k] = 1
dp[0][0][2][1] = 0
dp[0][0][1][2] = 0
dp[0][2][0][1] = 0

for i in range(n - 3):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    dp[i + 1][k][l][m] += dp[i][j][k][l]
                    dp[i + 1][k][l][m] %= MOD
                    if j == 0 and k == 2 and m == 1:
                        dp[i + 1][k][l][m] = 0
                    elif j == 0 and l == 2 and m == 1:
                        dp[i + 1][k][l][m] = 0
                dp[i + 1][0][2][1] = 0
                dp[i + 1][0][1][2] = 0
                dp[i + 1][2][0][1] = 0
print(sum(sum(sum(dp[n - 3], []), [])) % MOD)

Submission status: Accepted

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

# GAC, ACG, A?GC, AG?C, AGC
last_a = [1, 4, 16]
last_g = [1, 4, 15]
last_c = [1, 4, 14]
last_t = [1, 4, 16]
for i in range(3, N):
    last_a.append(last_a[i - 1] + last_g[i - 1] + last_c[i - 1] + last_t[i - 1])
    last_g.append(last_a[i - 1] + last_g[i - 1] + (last_c[i - 1] - last_a[i - 2] + last_g[i - 3]) + last_t[i - 1])
    last_c.append((last_a[i - 1] - last_g[i - 2]) + (last_g[i - 1] - last_a[i - 2] - (last_a[i - 3] * 2)) + last_c[i - 1] + (last_t[i - 1] - last_a[i - 3]))
    last_t.append(last_a[i - 1] + last_g[i - 1] + last_c[i - 1] + last_t[i - 1])

N -= 1
print((last_a[N] + last_g[N] + last_c[N] + last_t[N]) % mod)

Submission status: Accepted

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

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).find('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, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ in range(101)]

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).find('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 = int(input())
MOD = 10 ** 9 + 7
memo = [{} for _ in range(101)]

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).find('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)]

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:
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(input())
D, L = 4, 3
AGC = list(range(L))
ATGC = range(D)
cur = defaultdict(lambda: 1)
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
flip = lambda x, n: x[:n] + [x[n+1],x[n]] + x[n+2:]
prohibited1 = [tuple(AGC)] + [tuple(flip(AGC,i)) for i in range(L-1)]
prohibited2 = ({(X,) + p for p in prohibited1 for X in ATGC} | 
             {tuple(flip([X]+AGC,0)) for X in ATGC} |
             {tuple(flip(AGC+[X],L-1)) for X in ATGC})
for p in prohibited1:
    cur[p] = 0
for _ in range(L,N):
    prev = cur
    cur = defaultdict(int)
    for recent in product(ATGC, repeat=L+1):
        if recent in prohibited2:
            continue
        else:
            cur[recent[1:]] += prev[recent[:-1]]
    for latest in product(ATGC, repeat=L):
        cur[latest] %= MOD

ans = sum(cur.values()) % MOD
if N < L:
    print(D**N)
elif N == L:
    print(D**L - len(prohibited1))
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(input())
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
A=0; C=1; G=2; T=3
cur = defaultdict(lambda: 1)
cur[(A,G,C)] = cur[(G,A,C)] = cur[(A,C,G)] = 0
for _ in range(3,N):
    prev = cur
    cur = defaultdict(int)
    for (i,j,k,l) in product(range(4),repeat=4):
        if ((j,k,l)==(A,G,C) or (j,k,l)==(G,A,C) or (i,k,l)==(A,G,C) or
            (i,j,l)==(A,G,C) or (j,k,l)==(A,C,G)):
            continue
        else:
            cur[(j,k,l)] += prev[(i,j,k)]
    for ijk in product(range(4),repeat=3):
        cur[ijk] %= MOD

ans = sum(cur.values()) % MOD
if N <= 3:
    print([1,4,16,61][N])
else:
    print(ans)

Submission status: Accepted

Solution code:
# 'A'=0, 'C'=1, 'G'=2, 'T'=3 の4進法で考える
p=10**9+7
N=int(input())

a=[[0 for i in range(101)] for x in range(64)]
# a[x][i]は，最後の3桁がxであるようなi桁の文字列の数
# i=3での初期値
for x in range(64):
    if x in [6,9,33]:
        a[x][3]=0
    else:
        a[x][3]=1

# 漸化式
for i in range(3,N):
    for x in range(64):
        if x in [9,33,6]: # XAGC,XGAC,XACG
            a[x][i+1]=0
        elif x in [25,41,57,37,45]: # AXGC(A-:AGC(既出),CGC,GGC,TGC),AGXC(A-:GAC(既出),GCC,GGC(既出),GTC)
            a[x][i+1]=(a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p
        else:
            a[x][i+1]=(a[x//4][i]+a[x//4+16][i]+a[x//4+32][i]+a[x//4+48][i])%p

ans=0
for x in range(64):
    ans+=a[x][N]
print(ans%p)

Submission status: Accepted

Solution code:
from itertools import product
MOD = 10**9 + 7
N = int(input())
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
A=0; C=1; G=2; T=3
cur = [[[1]*4 for j in range(4)] for k in range(4)]
for i in range(4):
    cur[A][G][C] = cur[G][A][C] = cur[A][C][G] = 0

for _ in range(3,N):
    prev = cur
    cur = [[[0]*4 for j in range(4)] for k in range(4)]
    for i, j, k in product(range(4),repeat=3):
        if (j==A and k==G) or (j==G and k==A) or (i==A and k==G) or (i==A and j==G):
            for l in [A,G,T]:
                cur[j][k][l] += prev[i][j][k]
        elif j==A and k==C:
            for l in [A,C,T]:
                cur[j][k][l] += prev[i][j][k]
        else:
            for l in range(4):
                cur[j][k][l] += prev[i][j][k]
    for i, j, k in product(range(4),repeat=3):
        cur[i][j][k] %= MOD

ans = sum(sum(sum(cur[i][j]) for j in range(4)) for i in range(4)) % MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0]*16 for i in range(n)]
for j in range(16):
  dp[1][j] = 1

for i in range(2,n):
  for j in range(16):
    k = j//4
    dp[i][j] = dp[i-1][k]+dp[i-1][k+4]+dp[i-1][k+8]+dp[i-1][k+12]
    if j == 1:
      dp[i][j] -= dp[i-1][8]
    elif j == 6:
      dp[i][j] -= dp[i-1][1]
    elif j == 9:
      dp[i][j] -= dp[i-1][2]+dp[i-2][2]+dp[i-2][3]
    elif j == 13:
      dp[i][j] -= dp[i-2][2]
    else:
      continue

count = 0
for j in range(16):
  count += dp[n-1][j]

print(count%1000000007)

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
#A=0,C=1,G=2,T=3
table=[1]*(64)
data=[[] for i in range(64)]
for i in range(64):
    z=i
    num=""
    for j in range(3):
        if i//(4**(2-j))==1:
            num+="1"
            i%=(4**(2-j))
        elif i//(4**(2-j))==2:
            num+="2"
            i%=(4**(2-j))*2
        elif i//(4**(2-j))==3:
            num+="3"
            i%=(4**(2-j))*3
        else:
            num+="0"
    for j in range(4):
        a=num+str(j)
        b=a[1]+a[0]+a[2]+a[3]
        c=a[0]+a[2]+a[1]+a[3]
        d=a[0]+a[1]+a[3]+a[2]
        if "021" in a or "021" in b or "021" in c or "021" in d:
            continue
        else:
            data[z].append(16*int(a[1])+4*int(a[2])+int(a[3]))
table[6]=0
table[9]=0
table[33]=0
for i in range(n-3):
    h=[0]*64
    for j in range(64):
        for u in data[j]:
            h[u]=(h[u]+table[j])%mod
    table=h
ans=0
for i in range(64):
    ans=(ans+table[i])%mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0]*16 for i in range(n)]
for j in range(16):
  if j in [1,6,9]:
    dp[1][j] = 1
  else:
    dp[1][j] = 1

for i in range(2,n):
  for j in range(16):
    k = j//4
    dp[i][j] = dp[i-1][k]+dp[i-1][k+4]+dp[i-1][k+8]+dp[i-1][k+12]
    if j == 1:
      dp[i][j] -= dp[i-1][8]
    elif j == 6:
      dp[i][j] -= dp[i-1][1]
    elif j == 9:
      dp[i][j] -= dp[i-1][2]+dp[i-2][2]+dp[i-2][3]
    elif j == 13:
      dp[i][j] -= dp[i-2][2]
    else:
      continue

count = 0
for j in range(16):
  count += dp[n-1][j]

print(count%1000000007)

Submission status: Accepted

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

if N < 3 :
    print(0)
else :
    # A0 G1 C2 T3
    # AGC,ACG,GACはすぐ消す
    # AGx,AxGにはCを足しちゃいけないことにする
    
    dp = [1] * 64
    dp[6] = dp[9] = dp[18] = 0
     
    for _ in range(N-3) :
        dp_ = [0] * 64
        for i in range(64) :
            for j in range(4) :
                if j == 2 and i in [1, 4, 5, 7, 13] :
                    continue
                ni = (i*4+j)%64
                dp_[ni] += dp[i]
                dp_[ni] %= mod
        dp = dp_
        dp[6] = dp[9] = dp[18] = 0
        
    print(sum(dp) % mod)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n = int(input())
caps = ['A','G','C','T']
agct = []
for a in caps:
    for b in caps:
        for c in caps:
            if a+b+c not in ['AGC','GAC','ACG']:
                agct.append(a+b+c)

ngs = set(['AGC','GAC','ACG','AGGC','ATGC','AAGC','AGAC','AGTC'])           
dic = {}
for trio in agct:
        dic[trio] =1
for _ in range(n-3):
    dic2 = {x:0 for x in agct}
    for trio in agct:
        for cap in caps:
            quad = trio + cap
            if (not quad in ngs) and (not quad[1:] in ngs):
                dic2[quad[1:]] += dic[trio]
    dic = dic2

print(sum(dic.values())%mod)

Submission status: Accepted

Solution code:
N=int(input())
M=10**9+7
batu4=['AGG','AGT','ACG','ATG']
batu3=['AGC','ACG','GAC']
l=['A','G','C','T']
lx=['A','G','T']

def hash_index(s):
  num=0
  length=len(s)
  for i in range(length):
    letter=s[length-1-i]
    if letter=='A': k=0
    elif letter=='G': k=1
    elif letter=='C': k=2
    else: k=3
    num=num+k*4**i
  return num
hash_table=[]
for l1 in l:
  for l2 in l:
    for l3 in l:
      s_a=l1+l2+l3
      if s_a in batu3:
        hash_table.append([set()])
      elif s_a in batu4:
        s=set()
        for l4 in lx:
          s.add(l2+l3+l4)
        hash_table.append(s)
      else:
        s=set()
        for l4 in l:
            s_b=l2+l3+l4
            if not s_b in batu3:
              s.add(s_b)
        hash_table.append(s)
l_p=[1]*64
for l1 in l:
  for l2 in l:
    for l3 in l:
      s=l1+l2+l3
      if s in batu3:
        l_p[hash_index(s)]=0
  
#N>=4
for i in range(N-3):
  l_current=[0]*64
  for j in range(64):
    s_s=hash_table[j]
    for s in s_s:
      if not len(s)==0:
      	l_current[hash_index(s)]=(l_p[j]+l_current[hash_index(s)])%M
  l_p=l_current

num=0
for n in l_p:
  num=(num+n)%M
print(num)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
d = [{},{}]

def judge(s):
    if s[:3] == 'AGC' or s[:3] == 'GAC' or s[:3] == 'ACG' or s[0]+s[2:]=='AGC' or s[:2]+s[3]=='AGC':
        return False
    return True

d[0] = {'TTT':1}

for i in range(n):
    d[(i+1)%2] = {}
    for ne in 'AGCT':
        for elt in d[i%2]:
            if judge(ne+elt[:3]):
                if ne+elt[:2] in d[(i+1)%2]:
                    d[(i+1)%2][ne+elt[:2]] = (d[(i+1)%2][ne+elt[:2]]+d[i%2][elt])%mod
                else:
                    d[(i+1)%2][ne+elt[:2]] = d[i%2][elt]
res = 0
for e in d[n%2]:
    res = (res + d[n%2][e])%mod
print(res%mod)

Submission status: Accepted

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


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


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


print(dfs(0, 'TTT'))

Submission status: Accepted

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

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

def ok(last4):
#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):    #深さ優先探索
# cur   は 再帰回数 current?
#last3  は 末尾３文字
    if last3 in memo[cur]:  #memoにlast3が登録されていたら
        return memo[cur][last3] #dictはこれでvalueが出てくる
    if cur == N:    #求める回数再帰したら
        return 1    # ×1 して終了
    ret = 0 #Return(戻り値)の意味か
    for c in "ACGT":
        if ok(last3+c): #禁則事項を破ってないなら
            ret = (ret+dfs(cur+1, last3[1:]+c)) % M
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
N = int(input())

C = 10**9+7
n = 5
num = max(N+1, 6)
L = [0 for i in range(num)]
X = [0 for i in range(num)]
Y = [0 for i in range(num)]
Z = [0 for i in range(num)]
W = [0 for i in range(num)]
G = [0 for i in range(num)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
    L[n] = 4*L[n-1] - (X[n-1]+Y[n-1]+Z[n-1]+W[n-1])
    G[n] = L[n-1]-X[n-1]
    X[n] = L[n-2]-G[n-2]
    Y[n] = L[n-2]
    Z[n] = L[n-2]-X[n-2]
    if n > 5:
        W[n] = L[n-3]*3
    n += 1

print(L[N]%C)