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: Wrong Answer

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

dp = [[[[0] * 4 for ___ in range(4)]for __ in range(4)]for _ in range(N + 1)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[0][i][j][k] = 0
            dp[1][i][j][k] = 1
            dp[2][i][j][k] = 1
            if i == 2 and j == 1 and k == 0:
                continue
            elif i == 1 and j == 0 and k == 2:
                continue
            elif i == 2 and j == 0 and k == 1:
                continue
            dp[3][i][j][k] = 1


for n in range(3, N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for c in range(4):
                    if c == 1 and i == 2 and j == 0:
                        continue
                    elif c == 2 and i == 1 and j == 0:
                        continue
                    elif c == 2 and i == 0 and j == 1:
                        continue
                    elif c == 2 and i == 1 and k == 0:
                        continue
                    elif c == 2 and j == 1 and k == 0:
                        continue
                    dp[n + 1][c][i][j] += dp[n][i][j][k]
                    dp[n + 1][c][i][j] %= MOD

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

Submission status: Wrong Answer

Solution code:
def dfs(index, last, string, memo):
    mod = 10 ** 9 + 7
    if string in memo[index]:
        return memo[index][string]
    if index == last:
        return 1

    ret = 0
    for s in "ACGT":
        if check(string + s):
            ret = (ret + dfs(index + 1, last, string[1:] + s, memo)) % mod
    memo[index][string] = ret
    return ret


def check(string):
    for i in range(4):
        s_list = list(string)
        if i >= 1:
            s_list[i-1], s_list[i] = s_list[i], s_list[i-1]
        if "".join(s_list).count("AGC") >= 1:
            return False
    return True


def main():
    n = int(input())
    memo = [{} for _ in range(n+1)]

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, MOD = int(input()), 10**9 + 7
memo = [{} for x 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: Wrong Answer

Solution code:
N, MOD = int(input()), 10**9 
memo = [{} for x 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: Wrong Answer

Solution code:
N, MOD = int(input()), 10**9 
memo = [{} for x 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: Wrong Answer

Solution code:
n = int(input())
dp = [[[[0 for i in range(4)] for i in range(4)] for i in range(4)] for i in range(n+1)]

#A=0, C=1, G=2, T=3
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 a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    if [b,c,d] not in ([0,2,1],[2,0,1],[0,1,2]):
                        if [a,c,d] != [0,2,1] and [a,b,d] != [0,2,1]:
                                dp[i][b][c][d] += dp[i-1][a][b][c]
                                
count = 0
for i in range(4):
    for j in range(4):
            count += sum(dp[n][i][j]) % (10**9+7)
print(count)

Submission status: Wrong Answer

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
for i in range(N+1):
    if i == 0:
        memo[0]["****"] = 1
    elif i == 1:
        memo[1]["***A"] = 1
        memo[1]["***C"] = 1
        memo[1]["***G"] = 1
        memo[1]["***T"] = 1
    else:
        #print("aa")
        for c in 'ACGT':
            for j in memo[i-1]:
                #print(j)
                if ok(j[1:] + c):
                    if j[1:] + c not in memo[i]:               
                        memo[i][j[1:] + c] = memo[i-1][j] % MOD
                    else:
                        memo[i][j[1:] + c] += memo[i-1][j] % MOD

s = 0
for i in memo[N].values():
    s += i % MOD
print(s)

Submission status: Wrong Answer

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
for i in range(N+1):
    if i == 0:
        memo[0]["****"] = 1
    elif i == 1:
        memo[1]["***A"] = 1
        memo[1]["***C"] = 1
        memo[1]["***G"] = 1
        memo[1]["***T"] = 1
    else:
        #print("aa")
        for c in 'ACGT':
            for j in memo[i-1]:
                #print(j)
                if ok(j[1:] + c):
                    if j[1:] + c not in memo[i]:               
                        memo[i][j[1:] + c] = memo[i-1][j] % MOD
                    else:
                        memo[i][j[1:] + c] += memo[i-1][j] % MOD

s = 0
for i in memo[N].values():
    s += i
print(s)

Submission status: Wrong Answer

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

def dfs(cur, last3):
	if last3 in memo[cur]:
		return memo[cur][last3]
	if cur == n:
		return 1
	ret = 0
	for c in "AGCT":
		if ok(last3 + c):
			ret = ret + dfs(cur + 1, last3[1:] + c) % mod
	memo[cur][last3] = ret
	return ret


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

print(dfs(0, 'TTT'))

Submission status: Wrong Answer

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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

print(dfs(0, "TTT"))

Submission status: Wrong Answer

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 "AGCT":
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % mod
    memo[cur][last3] = ret
    return ret

print(memo)

Submission status: Wrong Answer

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

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

for len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for a in range(4):
                    if j==0 and k==2 and a==1:continue
                    if j==0 and k==1 and a==2:continue
                    if j==2 and k==0 and a==1:continue
                    if i==0 and k==2 and a==1:continue
                    if i==0 and j==2 and a==1:continue
                    dp[len+1][j][k][a]+=dp[len][i][j][k]
                    dp[len+1][j][k][a]%=P

ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[N][i][j][k]
print(ans)

Submission status: Wrong Answer

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

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

for len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for a in range(4):
                    if j==0 and k==2 and a==1:continue
                    if j==0 and k==1 and a==2:continue
                    if j==2 and k==0 and a==1:continue
                    if i==0 and k==2 and a==1:continue
                    if i==0 and j==2 and a==1:continue
                    dp[len+1][j][k][a]+=dp[len][i][j][k]%P

ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[N][i][j][k]
print(ans)

Submission status: Wrong Answer

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

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        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 "ATGC":
        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: Wrong Answer

Solution code:
N = int(input())
answer = 0
if(N == 3):
    answer = 61
else:
    answer = (4**N - 26 * (N - 3) * 4**(N - 4)) % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

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


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


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


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


print(ans % mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 10**9 + 7
dp = [[0, 0, 0, 0] for _ in range(n + 1)]
dp[1] = [1, 1, 1, 1]
dp[2] = [4, 4, 4, 4]
dp[3] = [16, 15, 14, 16]
for i in range(4, n + 1):
    dp[i][0] = sum(dp[i - 1]) % mod
    dp[i][1] = (sum(dp[i - 1]) - dp[i - 2][0] - dp[i - 2][2] - dp[i - 3][0] * 2) % mod
    dp[i][2] = (sum(dp[i - 1]) - dp[i - 2][0]) % mod
    dp[i][3] = sum(dp[i - 1]) % mod
print(sum(dp[n]) % mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
print((4**N - N) % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
N = int(input())
print((4**N - (N-2)) % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

total=(pow(4, N))%MOD
wrong=(pow(4, N-3)*3*(N-2) + pow(4, N-4)*2*(N-3))%MOD

print((total-wrong)%MOD)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from math import factorial

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

total=(pow(4, N))%MOD
wrong=(pow(4, N-3)*3*factorial(N-2) + pow(4, N-4)*2*factorial(N-3))%MOD

print((total-wrong)%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())

mod = 10 ** 9 + 7

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

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

print(dp)
for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= mod

ans = 0
print(dp)
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: Wrong Answer

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*int(input()));print(g%(1e9+7))

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

A = ("A", "C", "G", "T")

array = []
dellist = []


for i in itertools.product(A, repeat=N):
    key = ""
    for k in range(len(i)):
        key = key + i[k]
    array.append(key)

for j in range(len(array)):
    if ("AGC" in array[j]) or ("GAC" in array[j]) or ("ACG" in array[j]) or ("ATGC" in array[j]) or ("AGTC" in array[j]):
        dellist.append(array[j])

print((len(array)-len(dellist)) % 1000000007)

Submission status: Wrong Answer

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, 'AAA'))

Submission status: Wrong Answer

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):
    print((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: Wrong Answer

Solution code:
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
for i in range(1,n+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if m==0 and l==1 and k==2: continue
                    elif k==0 and l==2 and m==1: continue
                    elif k==0 and l==1 and m==2: continue
                    elif j==0 and l==2 and m==1: continue
                    elif j==0 and k==2 and m==1: continue
                    else: dp[i][k][l][m]+=dp[i-1][j][k][l]
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[-1][i][j][k]
print(ans%(10**9+7))

Submission status: Wrong Answer

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


def cal(n):
    if n == 3:
        return 3
    else:
        return (cal(n-1)*2)*(4-1)+8


ans = 4**n - cal(n)
print(ans % x)

Submission status: Wrong Answer

Solution code:
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

print(memo)
# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))

Submission status: Wrong Answer

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

dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3] = 1

for i in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):        
        for new in range(4):
          if new == 2 and c1 == 1 and c2 == 0:
            continue
          if new == 2 and c1 == 0 and c2 == 1:
            continue
          if new == 1 and c1 == 2 and c2 == 0:
            continue
          if new == 2 and c1 == 1 and c3 == 0:
            continue
          if new == 2 and c2 == 1 and c3 == 0:
            continue
          dp[i+1][new][c1][c2] += dp[i][c1][c2][c3]

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

print(int(res%mod))

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10 ** 9 + 7
D = [[[[0] * 4 for i in range(4)] for i in range(4)] for i in range(101)]

D[0][3][3][3] = 1
for i in range(100):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for x in range(4):
                    if k == 0 and l == 1 and x == 2:
                        continue
                    if k == 0 and l == 2 and x == 1:
                        continue
                    if k == 1 and l == 0 and x == 2:
                        continue
                    if j == 0 and l == 1 and x == 2:
                        continue
                    if j == 0 and k == 1 and x == 2:
                        continue
                    D[i + 1][k][l][x] += D[i][j][k][l] % mod
                    D[i + 1][k][l][x] %= mod
                    
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += D[N][j][k][l]
                    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10 ** 9 + 7
D = [[[[0] * 4 for i in range(4)] for i in range(4)] for i in range(101)]

D[0][3][3][3] = 1
for i in range(N):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for x in range(4):
                    if k == 0 and l == 1 and x == 2:
                        continue
                    if k == 0 and l == 2 and x == 1:
                        continue
                    if k == 1 and l == 0 and x == 2:
                        continue
                    if j == 0 and l == 1 and x == 2:
                        continue
                    if j == 0 and k == 1 and x == 2:
                        continue
                    D[i + 1][k][l][x] += D[i][j][k][l] % mod
                    D[i + 1][k][l][x] %= mod
                    
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += D[N][j][k][l]
                    
print(ans)

Submission status: Wrong Answer

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

def check(last4):
    t = list(last4)
    for i in range(4):
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).count('AGC') == 1:
            return False
    return True
    
def dfs(cur, last3):
    if last3 in D[cur]:
        return D[cur][last3]
    if cur == N:
        return 1
    res = 0
    for c in 'ACGT':
        if check(last3 + c):
            res = (res + dfs(cur + 1, last3[1:] + c)) % mod
    D[cur][last3] = res
    return res
    
print(dfs(0, '000'))

Submission status: Wrong Answer

Solution code:
N = int(input())

def to_bit(num,digit = 3,N = 2):
    bit = [0] * digit
    for i in range(digit):
        bit[i] = num % N
        num = int((num - (num % N)) / N)
    bit[0],bit[2] = bit[2],bit[0] 
    return bit

DP_map = [[0] * 64 for _ in range(100)]
'''
A = 0
C = 1
G = 2
T = 3

NG in 3 char
AGC = 0 * 16 + 2 * 4 + 1 * 1 = 9
ACG = 0 * 16 + 1 * 4 + 2 * 1 = 6
GAC = 2 * 16 + 0 * 4 + 1 * 1 = 33
'''
DP_map[0] = [1] * 64
DP_map[0][6] = 0
DP_map[0][9] = 0
DP_map[0][33] = 0

C_NG = [9,33]
for i in range(N - 2):
    for j in range(64):
        bit = to_bit(j)
        now = DP_map[i][j]
        added_A = bit[1] * 16 + bit[2] * 4 + 0
        added_C = bit[1] * 16 + bit[2] * 4 + 1
        added_G = bit[1] * 16 + bit[2] * 4 + 2
        added_T = bit[1] * 16 + bit[2] * 4 + 3
        DP_map[i + 1][added_A] = (DP_map[i + 1][added_A] + now) % (int(1e9 + 7))
        DP_map[i + 1][added_T] = (DP_map[i + 1][added_T] + now) % (int(1e9 + 7))
        if added_G != 6:
            DP_map[i + 1][added_G] = (DP_map[i + 1][added_G] + now) % (int(1e9 + 7))

        if (added_C not in C_NG) and (bit[0] != 0 or bit[2] != 2) and (bit[0] != 0 or bit[1] != 2):
            DP_map[i + 1][added_C] = (DP_map[i + 1][added_C] + now) % (int(1e9 + 7))


print(sum(DP_map[N-3]) % (int(1e9 + 7)))

Submission status: Wrong Answer

Solution code:
N = int(input())
N = 100
def to_bit(num,digit = 3,N = 2):
    bit = [0] * digit
    for i in range(digit):
        bit[i] = num % N
        num = int((num - (num % N)) / N)
    bit[0],bit[2] = bit[2],bit[0] 
    return bit

DP_map = [[0] * 64 for _ in range(100)]
'''
A = 0
C = 1
G = 2
T = 3

NG in 3 char
AGC = 0 * 16 + 2 * 4 + 1 * 1 = 9
ACG = 0 * 16 + 1 * 4 + 2 * 1 = 6
GAC = 2 * 16 + 0 * 4 + 1 * 1 = 33
'''
DP_map[0] = [1] * 64
DP_map[0][6] = 0
DP_map[0][9] = 0
DP_map[0][33] = 0

C_NG = [9,33]
for i in range(N - 2):
    for j in range(64):
        bit = to_bit(j)
        now = DP_map[i][j]
        added_A = bit[1] * 16 + bit[2] * 4 + 0
        added_C = bit[1] * 16 + bit[2] * 4 + 1
        added_G = bit[1] * 16 + bit[2] * 4 + 2
        added_T = bit[1] * 16 + bit[2] * 4 + 3
        DP_map[i + 1][added_A] = (DP_map[i + 1][added_A] + now) % (int(1e9 + 7))
        DP_map[i + 1][added_T] = (DP_map[i + 1][added_T] + now) % (int(1e9 + 7))
        if added_G != 6:
            DP_map[i + 1][added_G] = (DP_map[i + 1][added_G] + now)# % (int(1e9 + 7))

        if not(added_C in C_NG) and (bit[0] != 0 or bit[2] != 2) and (bit[0] != 0 or bit[1] != 2):
            DP_map[i + 1][added_C] = (DP_map[i + 1][added_C] + now) % (int(1e9 + 7))


print(sum(DP_map[N-3]) % (int(1e9 + 7)))

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 10**9+7
A,G,C,T = 0,1,2,3
dp = [[[[0]*4 for _ in range(4)] 
       for _ in range(4)] for _ in range(111)]
dp[0][T][T][T] = 1
for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for nex in range(4):
                    if b==A and c==G and nex==C: continue
                    if b==A and c==C and nex==G: continue
                    if b==G and c==A and nex==C: continue
                    if a==A and b==G and nex==C: continue
                    if a==A and c==G and nex==C: continue
                    dp[i+1][b][c][nex] += dp[i][a][b][c]
                    dp[i+1][b][c][nex] %= MOD
    
ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += dp[N][a][b][c]
            
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 1000000000+7

import numpy as np
dp=np.zeros((N+1, 4, 4, 4), dtype=np.int64)

dp[0,3,3,3] = 1
for length in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                if dp[length, c1, c2, c3]==0:
                    continue
                for a in range(4):
                    if a==2 and c1==1 and c2==0:
                        continue
                    if a==2 and c1==0 and c2==1:
                        continue
                    if a==1 and c1==2 and c2==0:
                        continue
                    if a==2 and c1==1 and c3==0:
                        continue
                    if a==2 and c2==1 and c3==0:
                        continue     
                    dp[length+1, a, c1, c2] += dp[length, c1, c2, c3] 
                    dp[length+1, a, c1, c2] %= mod
print(dp[N].sum())

Submission status: Wrong Answer

Solution code:
dp=[[[[0]*4 for i in range(4)] for i in range(4)] for i in range(5)]
print(dp)