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
A=[1] + [0]*(n-1)
G=[1] + [0]*(n-1)
C=[1] + [0]*(n-1)
for i in range(1,n):
    t=(2*A[i-1]+G[i-1]+C[i-1])%mod
    A[i]=t
    G[i]=(t-A[i-2]+G[i-3])%mod
    C[i]=(t-A[i-2]-G[i-2]-3*A[i-3])%mod
print((2*A[-1]+G[-1]+C[-1])%mod)

Submission status: Wrong Answer

Solution code:
# 記念提出
N = int(input())
AA = [0]*(N+1)
AG = [0]*(N+1)
AC = [0]*(N+1)
GG = [0]*(N+1)
GA = [0]*(N+1)
GC = [0]*(N+1)
CC = [0]*(N+1)
CA = [0]*(N+1)
CG = [0]*(N+1)
T_ = [0]*(N+1)
_T = [0]*(N+1)
TT = [0]*(N+1)

AA[2],AG[2],AC[2],GG[2],GA[2],GC[2],CC[2],CA[2],CG[2],T_[2],_T[2],TT[2] = 1,1,1,1,1,1,1,1,1,3,3,1
for i in range(3,N+1):
    AA[i] = AA[i-1] + GA[i-1] + CA[i-1] + T_[i-1]//3
    AG[i] = AA[i-1] + GA[i-1] + CA[i-1] + T_[i-1]//3
    AC[i] = AA[i-1] + CA[i-1] + T_[i-1]//3
    GG[i] = AG[i-1] + GG[i-1] + CG[i-1] + T_[i-1]//3
    GA[i] = AG[i-1] + GG[i-1] + CG[i-1] + T_[i-1]//3
    GC[i] = GG[i-1] + CG[i-1] + T_[i-1]//3 - AG[i-2] - _T[i-2]//3 
    CC[i] = AC[i-1] + GC[i-1] + CC[i-1] + T_[i-1]//3 
    CA[i] = AC[i-1] + GC[i-1] + CC[i-1] + T_[i-1]//3
    CG[i] = GC[i-1] + CC[i-1] + T_[i-1]//3
    T_[i] = _T[i-1]*3 + TT[i-1]*3 - AG[i-2]
    _T[i] = AA[i-1] + AG[i-1] + AC[i-1] + GG[i-1] + GA[i-1] + GC[i-1] + CC[i-1] + CA[i-1] + CG[i-1] + T_[i-1]
    TT[i] = _T[i-1] + TT[i-1]

ans = AA[N] + AG[N] + AC[N] + GG[N] + GA[N] + GC[N] + CC[N] + CA[N] + CG[N] + T_[N] + _T[N] + TT[N]
print(ans%(10**9+7))
print(AA[N] , AG[N] , AC[N] , GG[N] , GA[N] , GC[N] , CC[N] , CA[N] , CG[N] , T_[N] , _T[N] , TT[N])

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n = getN()
    dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # Free, A, G, AG, AC, AT, GA, AGA, AGG, AGT, ATG, (OUT)
    #   0   1  2   3   4   5   6   7    8    9    10

    for i in range(n):
        tmp = [0] * 11

        tmp[3] = dp[1] + dp[6] + dp[7]
        tmp[4] = dp[1]
        tmp[5] = dp[1] + dp[6]
        tmp[6] = dp[2] + dp[8] + dp[10]
        tmp[7] = dp[3]
        tmp[8] = dp[3]
        tmp[9] = dp[3]
        tmp[10] = dp[5]
        # out = dp[3] + dp[4] + dp[6] + dp[7] + dp[8] + dp[9] + dp[10]
        tmp[1] = dp[0] + dp[1] + dp[4] + dp[5] + dp[6] + dp[7] + dp[9]
        tmp[2] = dp[0] + dp[2] + dp[8] + dp[9] + dp[10]
        tmp[0] = dp[0] * 2 + dp[2] * 2 + dp[4] * 2 + dp[5] * 2 + dp[7] + dp[8] + dp[9] + dp[10]

        dp = [x % MOD for x in tmp]
        # print(dp)
    print(sum(dp)%MOD)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

# 文字を添え字に
def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

# 添え字を文字に
def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

# 部分文字列として含んではいけないものを正規表現で判定
def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

# 行列作成　各状態からの各遷移が有効か確かめる
A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1
A = np.array(A, dtype = np.int64)


# 行列の二分累乗
def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = np.int64)
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

# ベクトル作成　TTTのみ立てておく
x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)

Submission status: Wrong Answer

Solution code:
import re
import sys

from collections import *
ddict=defaultdict

from functools import lru_cache
cache=lru_cache(None)

from heapq import *
from itertools import *
from statistics import *

from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits
)
alnum=letters+digits
xdigits='01234567890abcdefabcdef'

inf=float('inf')
mod=1000000007
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

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

N=ri()

def allowed(p):
    if len(p)<3:
        return True
    if p[-3]=='A' and p[-2]=='G' and p[-1]=='C':
        return False
    if p[-3]=='G' and p[-2]=='A' and p[-1]=='C':
        return False
    if p[-3]=='A' and p[-2]=='C' and p[-1]=='G':
        return False
    return True

ans=0
def dfs(p=[]):
    global ans
    if not allowed(p):
        return
    if len(p)==N:
        ans+=1
        return
    for c in 'ACGT':
        p.append(c)
        dfs(p)
        p.pop()
     

dfs()
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import copy

n = 100
MOD = 10**9+7

dp = [[[[0]*(5) for i in range(5)] for i in range(5)] for i in range(n+1)]

dp[0][0][0][0] = 1
# A:1, C:2, G:3, T:4
for cn in range(1, n+1):
    for c3 in range(5):
        if cn <= 3 and c3 > 0:
            continue
        for c2 in range(5):
            if cn <= 2 and c2 > 0:
                continue
            for c1 in range(5):
                if cn == 1 and c1 > 0:
                    continue
                
                if c2 == 1 and c1 == 3: # AGX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 1 and c1 == 2: # ACX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = 0
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c2 == 3 and c1 == 1: # GAX
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c1 == 3: # AXGY        
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                elif c3 == 1 and c2 == 3: # AGXY        
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = 0
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                else:
                    dp[cn][c2][c1][1] = (dp[cn][c2][c1][1] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][2] = (dp[cn][c2][c1][2] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][3] = (dp[cn][c2][c1][3] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    dp[cn][c2][c1][4] = (dp[cn][c2][c1][4] + copy.deepcopy(dp[cn-1][c3][c2][c1])) % MOD
                    
total = 0
for c3 in range(1, 5):
    for c2 in range(1, 5):
        for c1 in range(1, 5):
            total = (total + dp[n][c3][c2][c1]) % MOD
print(total)

Submission status: Wrong Answer

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

a = pow(4,n-2,mod)*(n-2)*3
b = pow(4,n-3,mod)*(n-3)*2
tot = pow(4,n,mod)

print((tot-a-b)%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 2回前までのを保存しておく全探索？
# -> ATGC ACGC AGGC の場合も条件を満たしてしまうので、3つ前までかも（気づくのに長時間かかった）
# -> AGxCの場合も気づかなかった...

# なぜかサンプル3が合わないがコードが間違ってるわけないので表記ミスと判断して提出（傲慢

n = int(input())
if n == 3:
    print(61)
    exit()

memo = {}


def rec(i, pre3, pre2, pre1, path):
    if pre3 == "A" and pre2 == "G" and pre1 == "C":
        return 0
    if pre3 == "G" and pre2 == "A" and pre1 == "C":
        return 0
    if pre3 == "A" and pre2 == "C" and pre1 == "G":
        return 0
    if (i, pre1, pre2, pre3) in memo:
        return memo[(i, pre1, pre2, pre3)]
    if i == n - 3:
        return 1
    else:
        ret = 0
        if (pre1 == "G" and pre2 == "A") or (pre1 == "A" and pre2 == "G"):
            ret = rec(i + 1, pre2, pre1, "A", path + "A") + rec(
                i + 1, pre2, pre1, "G", path + "G") + rec(
                    i + 1, pre2, pre1, "T", path + "T")
        elif pre1 == "C" and pre2 == "A":
            ret = rec(i + 1, pre2, pre1, "C", path + "C") + rec(
                i + 1, pre2, pre1, "A", path + "A") + rec(
                    i + 1, pre2, pre1, "T", path + "T")
        elif pre3 == "A" and pre1 == "G":
            ret = rec(i + 1, pre2, pre1, "A", path + "A") + rec(
                i + 1, pre2, pre1, "G", path + "G") + rec(
                    i + 1, pre2, pre1, "T", path + "T")
        elif pre3 == "A" and pre2 == "G":
            ret = rec(i + 1, pre2, pre1, "A", path + "A") + rec(
                i + 1, pre2, pre1, "G", path + "G") + rec(
                    i + 1, pre2, pre1, "T", path + "T")
        else:
            ret = rec(i + 1, pre2, pre1, "A", path + "A") + rec(
                i + 1, pre2, pre1, "G", path + "G") + rec(
                    i + 1, pre2, pre1, "C", path + "C") + rec(
                        i + 1, pre2, pre1, "T", path + "T")
        ret %= (10**9) + 7
        memo[(i, pre1, pre2, pre3)] = ret
        return ret


# 最初とりうるやつ（めんどい）
ans = 0
for i in ["A", "G", "C", "T"]:
    for j in ["A", "G", "C", "T"]:
        for k in ["A", "G", "C", "T"]:
            ans += rec(0, i, j, k, i + j + k)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

mod = 10 ** 9 + 7

from collections import defaultdict
from itertools import product
keys = []
for prod in product('AGCT', 'AGCT', 'AGCT', 'AGCT'):
    last = ''.join(prod)
    f = ('AGC' not in last)

    for i in range(len(last) - 1):
        last2 = list(last)
        last2[i], last2[i+1] = last2[i+1], last2[i]
        last2 = ''.join(last2)
        if 'AGC' in last2:
            f = False

    if f:
        keys.append(''.join(last))

dp = dict()
for key in keys:
    dp[key] = 1

for _ in range(4, n):
    dp_new = defaultdict(int)

    for key in keys:
        for char in 'AGCT':
            last = (key + char)[1:]
            f = ('AGC' not in last)

            for i in range(len(last) - 1):
                last2 = list(last)
                last2[i], last2[i+1] = last2[i+1], last2[i]
                last2 = ''.join(last2)
                if 'AGC' in last2:
                    f = False

            if f:
                dp_new[''.join(last)] += dp[key]

    dp = dict()
    for key in keys:
        dp[key] = dp_new[key] % mod

print(sum(list(dp.values())) % mod)

Submission status: Wrong Answer

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

n = int(input())

mod = 10**9+7

miss = set(["AGC", "ACG", "GAC"])
# miss = set([])


ans = {"AA": 1, "AC": 1, "AG": 1, "AT": 1,
       "CA": 1, "CC": 1, "CG": 1, "CT": 1,
       "GA": 1, "GC": 1, "GG": 1, "GT": 1,
       "TA": 1, "TC": 1, "TG": 1, "TT": 1}

ans_base = {"AA": 0, "AC": 0, "AG": 0, "AT": 0,
            "CA": 0, "CC": 0, "CG": 0, "CT": 0,
            "GA": 0, "GC": 0, "GG": 0, "GT": 0,
            "TA": 0, "TC": 0, "TG": 0, "TT": 0}

AG = [0, 1]
for i in range(2, n):
    ans_pre = copy.deepcopy(ans)
    ans = copy.deepcopy(ans_base)
    print(ans_pre)
    for key in ans_pre.keys():

        for l in ["A", "C", "G", "T"]:

            if key+l in miss:
                print(key+l)
                continue
            else:
                # print((key+l))
                ans[(key+l)[1:]] += ans_pre[key] % mod
    AG.append(ans["AG"])
    print(AG)
    ans["AC"] -= AG[-3]
    ans["GC"] -= AG[-3]
    ans["TC"] -= AG[-3]


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


# AA
# AC
# AG
# AT
# CA
# CC
# CG
# CT
# GA
# GC
# GG
# GT
# TA
# TC
# TG
# TT

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][-1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD
print(dp)    
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
MOD = 10**9 + 7
ACGT = ["A","C","G","T"]
dp = [ [ [ [0 for l in range(4) ] for k in range(4)] for j in range(4)] for i in range(N+1)]
dp[0][-1][-1][1] = 1

for i,p,q,r,s in itertools.product(range(N),range(4),range(4),range(4),range(4)):
  if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
  and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
  and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
    dp[i + 1][q][r][s] += dp[i][p][q][r]
    dp[i + 1][q][r][s] %= MOD
print(dp)    
print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())

MOD = 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
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans += dp[-1][i][j][k]
            ans %= MOD

print(dp)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
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 len in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[len][i][j][k] == 0: continue

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

Submission status: Wrong Answer

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

n = int(input())

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
c = [0, 1, 2, 3]
import itertools
pers = itertools.product(c, repeat=3)
for p in pers:
    if p in [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
        continue
    dp[3][p[0]][p[1]][p[2]] = 1
for i in range(4, n + 1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if (j, k, l) in [(0, 1, 2), (0, 2, 1), (1, 0, 2)]:
                    continue
                elif (j == 0 and l == 1) or (j == 0 and k == 1):
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4) if x != 2])
                else:
                    dp[i][j][k][l] = sum([dp[i - 1][k][l][x] for x in range(4)])
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[-1][j][k][l]
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N = int(input())
char = ['A','C','G','T']
NG1 = {"ACG","AGC","GAC"}
NG2 = {"AAGC", "ACGC", "AGGC", "ATGC", "AGAC", "AGCG", "AGGC", "AGTC"}
memo = [{} for i in range(110)]

def dfs(n, s):
    if s in memo[n]:
        return memo[n][s]
    if n == N:
        # 条件に当てはまるかどうかをチェックしてから、dfsを呼び出すので、nが作りたかった文字列の長さに到達した場合は、1を返却する
        return 1
    ret = 0
    for c in char:
        if s+c in NG2 or s[1:]+c in NG1: continue
        # 次に追加する文字列4つを全て試して足し合わせる
        ret += dfs(n+1, s[1:]+c)
        ret %= mod
    memo[n][s] = ret
    return ret

#print(dfs(0, 'TTT'))

Submission status: Wrong Answer

Solution code:
S = input()
#dp[i][four] =: i + 1番目まで見たとき,照合したケツがfourとなるものの総数
dp = [[0 for _ in range(4)] for _ in range(len(S)+1 )]
dp[0][0] = 1
mod = 10**9 + 7
for i in range(len(S)):
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] += dp[i][0] 
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] += dp[i][1]
        for k in range(4): dp[i+1][k] += dp[i][k]
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] += dp[i][2]
        for k in range(4): dp[i+1][k] += dp[i][k]
    for k in range(4): dp[i+1][k] %= mod
print(dp[len(S)][3])

Submission status: Wrong Answer

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

dp=[[[[0]*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]
ans=0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans +=dp[n][i][j][k]

print(ans)

Submission status: Wrong Answer

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

dp=[[[[0]*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(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+1][j][k][l]+dp[x][i][j][k])%mod
ans=0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans =(ans +dp[n][i][j][k])%mod

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 10**9 + 7
acgt = ["A", "C", "G", "T"]
dp = {acgt[i]+acgt[j]+acgt[k]: 1 for i in range(4) for j in range(4) for k in range(4)}
dp["AGC"] = 0
dp["ACG"] = 0
dp["GAC"] = 0

for i in range(n-3):
    next_dp = {key: 0 for key in dp.keys()}
    for key, val in dp.items():
        for item in acgt:
            next_key = key + item
            if next_key[1:] == "AGC" or next_key[1:] == "ACG" or next_key[1:] == "GAC":
                continue
            elif next_key[0] + next_key[2:] == "AGC" or next_key[:1] + next_key[3] == "AGC":
                continue
            else:
                dp[next_key[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= mod
print(sum(dp.values())%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
# {0:"A", 1:"C", 2:"G", 3:"T"}
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][3][3][3] = 1
mod = 10 ** 9 + 7

for i in range(n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    if m == 1 and l == 0 and k == 2:
                        continue
                    if m == 2 and l == 1 and k == 0:
                        continue
                    if m == 1 and l == 2 and k == 0:
                        continue
                    if m == 2 and k == 1 and j == 0:
                        continue
                    if m == 1 and l == 2 and k == 0:
                        continue
                    
                    dp[i+1][k][l][m] += dp[i][j][k][l]
                    dp[i+1][k][l][m] %= 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: Wrong Answer

Solution code:
n = int(input())

dp = [[[[0]*4 for i in range(4)] for j in range(4)] for j in range(101)]
big = 1000000007
#長さ、3個前の文字、2個前の文字、1個前の文字

for i in range(4):
    for j in range(4):
       for k in range(4):
            dp[3][i][j][k] = 1

#AGC,GAC,ACGはNG
dp[3][0][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

#*AC → Gダメなので ACGから減らす
#*AG → Cダメなので AGCから減らす
#*GA → Cダメなので GACから減らす

#AG* → Cダメなので G*Cから減らす
#(AGAのダブルカウントに注意)

#A*G → Cダメなので *GCから減らす
#(AAG,AGGのダブルカウントに注意)

for t in range(4,n+1):
    #基本的には…
    for i in range(4):
        for j in range(4):
            dp[t][i][j][0] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][1] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][2] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][3] = sum(dp[t-1][0:4][i][j])
    
    #例外を減らしていく
    dp[t][0][1][2] -= sum(dp[t-1][0:4][0][1])
    dp[t][0][2][1] -= sum(dp[t-1][0:4][0][2])
    dp[t][2][0][1] -= sum(dp[t-1][0:4][2][0])

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

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

    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[t][i][j][k] = dp[t][i][j][k] % big

ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[n][i][j][k]) % big

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

dp = [[[[0]*4 for i in range(4)] for j in range(4)] for j in range(101)]

#長さ、3個前の文字、2個前の文字、1個前の文字

for i in range(4):
    for j in range(4):
       for k in range(4):
            dp[3][i][j][k] = 1

#AGC,GAC,ACGはNG
dp[3][0][2][1] = 0
dp[3][2][0][1] = 0
dp[3][0][1][2] = 0

#*AC → Gダメなので ACGから減らす
#*AG → Cダメなので AGCから減らす

#*GA → Cダメなので GACから減らす
#AG* → Cダメなので G*Cから減らす
#(AGAのダブルカウントに注意)

#AC* → Gダメなので C*Gから減らす

for t in range(4,n+1):
    #基本的には…
    for i in range(4):
        for j in range(4):
            dp[t][i][j][0] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][1] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][2] = sum(dp[t-1][0:4][i][j])
            dp[t][i][j][3] = sum(dp[t-1][0:4][i][j])
    
    #例外を減らしていく
    dp[t][0][1][2] -= sum(dp[t-1][0:4][0][1])
    dp[t][0][2][1] -= sum(dp[t-1][0:4][0][2])
    dp[t][2][0][1] -= sum(dp[t-1][0:4][2][0])
    dp[t][2][1][1] -= dp[t-1][0][2][1]
    dp[t][2][2][1] -= dp[t-1][0][2][2]
    dp[t][2][3][1] -= dp[t-1][0][2][3]

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


    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[t][i][j][k] = dp[t][i][j][k] % 1000000007

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
# dp[i] iまでで完成した総数、ng[i] iまででちょうどngが完成した数
dp = [0] * (N+1)
dp[0] = 1; dp[1] = 4; dp[2] = 16; dp[3] = 61
ng = [0] * (N+1)
ng[3] = 3
for i in range(4, N+1):
    whole = dp[i-1] * 4  # 全体の数
    ng[i] = dp[i-3] * 3 + dp[i-4] * 2
    dp[i] = (whole - ng[i]) % MOD

answer = dp[N]
print(answer % MOD)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

N = int(input())

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

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

MOD = 10 ** 9 + 7
for l in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[l][i][j][k] == 0:
                    continue
                
                for n in range(4):
                    if j == 0 and k == 2 and n == 1: continue
                    if j == 0 and k == 1 and n == 2: continue
                    if j == 1 and k == 0 and n == 2: continue

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

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

Submission status: Wrong Answer

Solution code:
#A,G,C,T=0,1,2,3
#AGC,ACG,GACを含まない
#A?GC,AG?Cを含まない
n=int(input())
A=[[1,1,1,1],[1,1,0,1],[1,0,1,1],[1,1,1,1]] #3文字前がAのとき
B=[[3,3,2,3],[3,3,3,3],[3,3,3,3],[3,3,3,3]] #それ以外
mod=10**9+7

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