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:
#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(A,B)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
#122_D
n=int(input())

dp=[[[[0 for _ in range(4)]for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
for k in range(4):
    for l in range(4):
        for m in range(4):
            flg=(k==0 and l==1 and m==2) or (k==0 and l==2 and m==1) or (k==2 and l==0 and m==1)
            if not flg:
                dp[3][k][l][m]=1
        

        
for i in range(4,n+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                for m in range(4):
                    flg=(j==0 and (k==2 or l==2) and m==1) or (k==0 and l==1 and m==2) or (k==0 and l==2 and m==1) or (k==2 and l==0 and m==1)
                    if not flg:
                        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[n][i][j][k]
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

g_cnt = 0
def main():
    N = I()
    dp = [[[0 for _ in range(4)] for __ in range(4)] for ___ in range(N)]
    s2i = {
        'A': 0,
        'G': 1,
        'C': 2,
        'T': 3,
    }
    for i in range(2):
        for j in range(4):
            for k in range(4):
                dp[i][j][k] = 1
    for i in range(1, N-1):
        for j in range(4):
            for k in range(4):
                dp[i][j][k] %= mod
                if j == s2i['A'] and k == s2i['G']:
                    dp[i+1][s2i['G']][s2i['A']] += dp[i][j][k]
                    dp[i+1][s2i['G']][s2i['T']] += dp[i][j][k]
                    dp[i+1][s2i['G']][s2i['G']] += dp[i][j][k]

                elif j == s2i['A'] and k == s2i['C']:
                    dp[i+1][s2i['C']][s2i['A']] += dp[i][j][k]
                    dp[i+1][s2i['C']][s2i['T']] += dp[i][j][k]
                    dp[i+1][s2i['C']][s2i['C']] += dp[i][j][k]

                elif j == s2i['G'] and k == s2i['A']:
                    dp[i+1][s2i['A']][s2i['A']] += dp[i][j][k]
                    dp[i+1][s2i['A']][s2i['G']] += dp[i][j][k]
                    dp[i+1][s2i['A']][s2i['T']] += dp[i][j][k]

                else:
                    for X in range(4):
                        dp[i+1][k][X] += dp[i][j][k]
    cnt = 0
    for j in range(4):
        for k in range(4):
            cnt += (dp[N-1][j][k] % mod)
    print(cnt)
main()

Submission status: Wrong Answer

Solution code:
n=int(input())
alph=["A","C","G","T"]
a=[alph[i]+alph[j]+alph[k] for i in range(4) for j in range(4) for k in range(4)]
d1={l:0 for l in a}
for i in d1:
    if i!="AGC" and i!="ACG" and i!="GAC":
        d1[i]=1
d2={l:0 for l in a}
for i in range(n-3):
    for j in d1:
        next=[j+alph[k] for k in range(4)]
        for k in range(4):
            l=next[k]
            check1=l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC"
            check2=l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC"
            if (not check1) and (not check2):
                d2[l[1:]]+=d1[j]
    for j in d1:
        d1[j]=d2[j]%1000000007
        d2[j]=0
print(sum(d1.values())%1000000007)

Submission status: Wrong Answer

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


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

def check1(a,b,c):
    t=[a,b,c]
    if t==[1,2,4] or t==[1,4,2] or t==[2,1,4]:
        return False
    return True

def check2(a,b,c,m):
    if ([b,c]==[2,4] and m==1) or ([a,c]==[2,4] and m==1):
        return False
    return check1(a,b,c)
    
    
#初期化
for n in range(min(4,N+1)):
    for i in range(A):
        for j in range(A):
            for k in range(A):
                if check1(i,j,k):
                    dp[n][i][j][k]=1
                    
for n in range(4,N+1):
    for i in range(1,A):
        for j in range(1,A):
            for k in range(1,A):
                for m in range(1,A):
                    if check2(i,j,k,m):
                        dp[n][i][j][k]+=dp[n-1][m][i][j]
                dp[n][i][j][k]%=mod
                        
ans=0
if N>=4:
    for i in range(1,A):
            for j in range(1,A):
                for k in range(1,A):
                    ans+=dp[N][i][j][k]

if N==1:
    ans=4
elif N==2:
    ans=16

print(ans%mod)

Submission status: Wrong Answer

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

agc = [[1, 1, 1, 1], [4, 4, 4, 4], [16, 15, 14, 16]]

for i in range(n-3):
    sm = sum(agc[-1])
    s = sm % mod
    c = agc[-2][0] + agc[-3][0] * 2
    g = agc[-2][0] + agc[-2][2]

    cc,gg = sm, sm
    while cc < c:
        cc += sm
    while gg < g:
        gg += sm
    # if c > sm:
    #     c -= c // sm * sm
    # if g > sm:
    #     g -= g // sm * sm
    a = [s, (cc - c) % mod, (gg - g) % mod, s]
    # while a[1] < 0:
    #     a[1] += sm
    # while a[2] < 0:
    #     a[2] += sm
    agc.append(a)
    # print(agc)

print(sum(agc[-1]))
# [61, 51, 57, 61]

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==3:
    print(61)
    exit()
z=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in z:
        for k in list('AGCT'):
            tmp.append(j+k)
    z=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
    if not z[i] in ng:
        dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            if not z[k] in ng:
                if z[j][1:]==z[k][:3]:
                    dp[i+1][k]+=dp[i][j]
print(sum(dp[-1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0

if N == 3:
  ans = 4**N
  ans -= 3
elif N == 4:
  ans = 4**N
  ans -= 2*3*4 # 3つのNGパターンに対し、右か左に4つのいずれかが入ったパターン
  ans -= 2 # AGTC,ATGC
else:
  ans = 4**N
  ans -= (N-2)*3*4**(N-3)
  ans -= 2
  ans -= (N-4)*2

print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
n -= 3
tmp = 61
for i in range(n):
    tmp = tmp*4 - 14
    tmp %= mod
print(tmp)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

print(m)

Submission status: Wrong Answer

Solution code:
n=int(input())

l=[1,4,16]


for i in range(3,n+1):
    m=0
    k=0
    s=0
    for j in range(i-4+1):
        m+=l[j]*l[i-4-j]

    for p in range(i-3+1):
        k+=l[p]*l[i-3-p]

    for q in range(i-5+1):
        s+=l[q]*l[i-5-q]
    
    l.append(4**i-(m*2+k*3-s*1))

print(l[n]%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [1, 4, 16, 61]

for i in range(3, N):
    A.append(A[i] * 4 - A[i - 2] * 2 - A[i - 3] * 6)

print(A[N] % (10**9 + 7))

Submission status: Wrong Answer

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_aga = [0,0,0,1]
end_agt = [0,0,0,1]
end_agg = [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] - end_aga[i])%mod)
    end_ga.append(end_g[i]%mod)
    end_aga.append(end_ag[i]%mod)
    end_agt.append(end_ag[i]%mod)
    end_agg.append(end_ag[i]%mod)
    taboo = (end_ag[i] + end_ac[i] + end_ga[i] + end_aga[i] + end_agt[i] + end_agg[i])%mod
    ans.append((taboo*3 + (ans[i]-taboo)*4)%mod)
print(ans[n]%mod)

Submission status: Wrong Answer

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

print(dfs(0, 'TTT') % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
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):
            x = dfs(cur+1, last3[1:] + c)
            memo[cur][last3] = x
            ret += x
    return ret

print(dfs(0, 'TTT'))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
from itertools import product
N = int(input())
# XAGC, XGAC, AXGC, 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] = 1

for i 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):
            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))
print(ans)

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
    print(memo)
    return ret


print(dfs(0, 'TTT'))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def sol(n): return int(4**n - (4**(n-3))*(n-2)*3 - (4**(n-4))*(n-3)*2)
print(sol(int(input()))%MOD)

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)]
print(dp)

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import re

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

N = int(input())

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


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

N -= 3

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import re
MOD = 10**9+7
AGCT = "AGCT"
memo = ["",]
for a in [0,1,5,21]:
    hoge = []
    for i in memo[a:]:
        for j in AGCT:
            hoge.append(i+j)
    memo += hoge
AGC = []
pattern = [r"AGC",r"ACG",r"GAC",r"A\wGC",r"AG\wC"]
for i in range(len(memo)):
    for p in pattern:
        if re.compile(p).search(memo[i]) != None:
            AGC.append(i)
            break

N = int(input())
DP = [[0]*len(memo) for i in range(N+1)]
DP[0][0] = 1
for i in range(N):
    for j in range(1,5):
        DP[i+1][j] = DP[i][0]
    for j in range(5,21):
        DP[i+1][j] = DP[i][(j-5)//4+1]
    for j in range(21,85):
        DP[i+1][j] = DP[i][(j-21)//(4)+5]
    for j in range(85,341):
        for k in [j,(j-85)//(4)+21,(j-85)//(4)+21+64*1,(j-85)//(4)+21+64*2,(j-85)//(4)+21+64*3,(j-85)//(4)+21+64*4]:
            DP[i+1][j] += DP[i][k]
        DP[i+1][j] %= MOD
    for j in AGC:
        DP[i+1][j] = 0

print(sum(DP[-1])%MOD)

Submission status: Wrong Answer

Solution code:
import re
MOD = 10**9+7
AGCT = "AGCT"
memo = ["",]
for a in [0,1,5,21]:
    hoge = []
    for i in memo[a:]:
        for j in AGCT:
            hoge.append(i+j)
    memo += hoge
AGC = []
pattern = [r"AGC",r"ACG",r"GAC",r"A\wGC",r"AG\wC"]
for i in range(len(memo)):
    for p in pattern:
        if re.compile(p).search(memo[i]) != None:
            AGC.append(i)
            break

N = int(input())
DP = [[0]*len(memo) for i in range(N+1)]
DP[0][0] = 1
for i in range(N):
    for j in range(1,5):
        DP[i+1][j] = DP[i][0]
    for j in range(5,21):
        DP[i+1][j] = DP[i][(j-5)//4+1]
    for j in range(21,85):
        DP[i+1][j] = DP[i][(j-21)//(4**2)+7]
    for j in range(85,341):
        for k in [j,(j-85)//(4)+21,(j-85)//(4)+21+64*1,(j-85)//(4)+21+64*2,(j-85)//(4)+21+64*3,(j-85)//(4)+21+64*4]:
            DP[i+1][j] += DP[i][k]
        DP[i+1][j] %= MOD
    for j in AGC:
        DP[i+1][j] = 0

print(sum(DP[-1])%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD_NUM = 10**9 + 7
dp = [1, 4, 4**2] + [0] * 98

for i in range(3, N+1):
  if i == 3:
    dp[i] = dp[i-1]*4 - dp[i-3]*3
  else:
    dp[i] = dp[i-1]*4 - dp[i-3]*3 - 2
print(dp[N]%MOD_NUM)

Submission status: Wrong Answer

Solution code:
import copy

def ok(len_4):    
    for i in range(3):
        alpha = list(copy.deepcopy(len_4))
        alpha[i], alpha[i + 1] = alpha[i + 1], alpha[i]
        if "AGC" in "".join(alpha):
            return False
    if "AGC"in len_4:
        return False
    return True


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
check("TTT", 0)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input().strip())

i2s = [''.join(s) for s in itertools.product('ACGT', 'ACGT', 'ACGT')]

dp = [{s:0 for s in i2s} for _ in range(N)]

def update(i, prev_str, next_char):
  dp[i][prev_str[1:]+next_char] += dp[i-1][prev_str]

# init
for k in i2s:
  if k in ['AGC', 'GAC', 'ACG']: continue
  dp[2][k] = 1
  
for i in range(3, N):
  for k in i2s:
    if (k[0] == 'A' and k[2] == 'G') or k[1:] == 'GA' or k[1:] == 'AC' or k[:2] == 'AG' or k[1:] == 'AG':
      for n in 'ATG':
        update(i, k, n)
    elif k[:2] == 'AG':
      for n in 'ATC':
        update(i, k, n)
    else:
      for n in 'ATGC':
        update(i, k, n)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = (10 ** 9) + 7
ans = 0
k = []
d = []
def calc(l, ans):
    if len(l) == n:
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        return ans + 1
    for alphabet in "AGCT":
        ll = l + alphabet
        ans = calc(ll, ans)
    return ans
calc("", ans) % mod

Submission status: Wrong Answer

Solution code:


from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

num = [4,4,4,4,4,4,4,4,3,4,4,4,3,4,3,4,1,1,1]

for i in range(N - 3):
	num2 = [0]*19
	num2[0] = num[0] + num[1] + num[2] + num[3]
	num2[4] = num2[0]
	num2[5] = num2[0]
	num2[6] = num2[0] - num[17]
	num2[1] = num[4] + num[7] + num[10] + num[13]
	num2[7] = num2[1]
	num2[8] = num2[1] - num[13]
	num2[9] = num2[1]
	num2[2] = num[5] + num[8] + num[11] + num[14]
	num2[10] = num2[2]
	num2[11] = num2[2] - num[8]
	num2[12] = num2[2]
	num2[3] = num[6] + num[9] + num[12] + num[15]
	num2[13] = num2[3]
	num2[14] = num2[3] - num[9] - num[16] - num[18]
	num2[15] = num2[3]
	num2[16] = num[9]
	num2[17] = num[9]
	num2[18] = num[1]
	for i in range(19):
		num2[i] = num2[i] % 1000000007
	num = copy.deepcopy(num2)


print(sum(num[0:16]))

Submission status: Wrong Answer

Solution code:
# We Like AGC

N = int(input())
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

mod = 1e+9+7
for l 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==1 and c2 == 0 and c3 == 2:
						continue
					if a==2 and c2 == 1 and c3 == 0:
						continue
					if a==2 and c1 == 0 and c2 == 1:
						continue
					if a==2 and c1 == 0 and c3 == 1:
						continue
					dp[l][c2][c3][a] += dp[l-1][c1][c2][c3]

cnt = 0
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: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
XAA = 1
XAT = 1
XAG = 1
XAC = 1
XTA = 1
XTT = 1
XTG = 1
XTC = 1
XGA = 1
XGT = 1
XGG = 1
XGC = 1
XCA = 1
XCT = 1
XCG = 1
XCC = 1
m = 1000000007
N = int(input())

for i in range(N-2):
  XAA, XAT, XAG, XAC, XTA, XTT, XTG, XTC, XGA, XGT, XGG, XGC, XCA, XCT, XCG, XCC = (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XCA)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAG + XTG + XGG + XCG)%m, (XAG + XTG + XGG + XCG)%m, (XAG + XTG + XGG + XCG)%m, (XTG + XGG + XCG)%m, (XAC + XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m, (XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m

print((XAA+XAT+XAG+XAC+XTA+XTT+XTG+XTC+XGA+XGT+XGG+XGC+XCA+XCT+XCG+XCC)%m)

Submission status: Wrong Answer

Solution code:
XAA = 1
XAT = 1
XAG = 1
XAC = 1
XTA = 1
XTT = 1
XTG = 1
XTC = 1
XGA = 1
XGT = 1
XGG = 1
XGC = 1
XCA = 1
XCT = 1
XCG = 1
XCC = 1
m = 1000000007
N = int(input())

for i in range(N-2):
  XAA, XAT, XAG, XAC, XTA, XTT, XTG, XTC, XGA, XGT, XGG, XGC, XCA, XCT, XCG, XCC = (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XCA)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAG + XTG + XGG)%m, (XAG + XTG + XGG + XCG)%m, (XAG + XTG + XGG + XCG)%m, (XTG + XGG + XCG)%m, (XAC + XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m, (XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m

print((XAA+XAT+XAG+XAC+XTA+XTT+XTG+XTC+XGA+XGT+XGG+XGC+XCA+XCT+XCG+XCC)%m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
M = (10**9)+7
dic = {}
pdic = {}
pdic['AAA'] = 1
pdic['AAC'] = 1
pdic['AAG'] = 1
pdic['AAT'] = 1
pdic['ACA'] = 1
pdic['ACC'] = 1
pdic['ACG'] = 0
pdic['ACT'] = 1
pdic['AGA'] = 1
pdic['AGC'] = 0
pdic['AGG'] = 1
pdic['AGT'] = 1
pdic['ATA'] = 1
pdic['ATC'] = 1
pdic['ATG'] = 1
pdic['ATT'] = 1
pdic['CAA'] = 1
pdic['CAC'] = 1
pdic['CAG'] = 1
pdic['CAT'] = 1
pdic['CCA'] = 1
pdic['CCC'] = 1
pdic['CCG'] = 1
pdic['CCT'] = 1
pdic['CGA'] = 1
pdic['CGC'] = 1
pdic['CGG'] = 1
pdic['CGT'] = 1
pdic['CTA'] = 1
pdic['CTC'] = 1
pdic['CTG'] = 1
pdic['CTT'] = 1
pdic['GAA'] = 1
pdic['GAC'] = 0
pdic['GAG'] = 1
pdic['GAT'] = 1
pdic['GCA'] = 1
pdic['GCC'] = 1
pdic['GCG'] = 1
pdic['GCT'] = 1
pdic['GGA'] = 1
pdic['GGC'] = 1
pdic['GGG'] = 1
pdic['GGT'] = 1
pdic['GTA'] = 1
pdic['GTC'] = 1
pdic['GTG'] = 1
pdic['GTT'] = 1
pdic['TAA'] = 1
pdic['TAC'] = 1
pdic['TAG'] = 1
pdic['TAT'] = 1
pdic['TCA'] = 1
pdic['TCC'] = 1
pdic['TCG'] = 1
pdic['TCT'] = 1
pdic['TGA'] = 1
pdic['TGC'] = 1
pdic['TGG'] = 1
pdic['TGT'] = 1
pdic['TTA'] = 1
pdic['TTC'] = 1
pdic['TTG'] = 1
pdic['TTT'] = 1
for i in range(N-3):
  for k in pdic.keys():
    k = str(k)
    if k=='ACG' or k=='AGC' or k=='GAC':
      dic[k] = 0
    elif k[1:]=='GC':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    elif k[0]=='G' and k[2]=='C':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    else:
      dic[k] = pdic['A'+k[:-1]]+pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
  for k in pdic.keys():
    pdic[k] = dic[k]
for v in dic.values():
  ans += v
  ans = ans % M
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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


for k in range(5):
    if k == 0 :
        dp[0][k]=3
    elif k == 1 :
        dp[0][k]=4
    elif k == 2 :
        dp[0][k]=4
    elif k == 3 :
        dp[0][k]=3
    elif k == 4 :
        dp[0][k]=4


for i in range(1,N):
    dp[i][0]=(dp[i-1][0] + dp[i-1][2] + dp[i-1][3])              %1000000007
    dp[i][1]=(dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) %1000000007
    dp[i][2]=(2*dp[i-1][1] + dp[i-1][2] + dp[i-1][4])            %1000000007
    dp[i][3]=(dp[i-1][0] + dp[i-1][2] + dp[i-1][4])              %1000000007
    dp[i][4]=(dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][4]) %1000000007



answer = 2*dp[N-3][0] + 2*dp[N-3][1] + 8*dp[N-3][2] + 1*dp[N-3][3] + 3*dp[N-3][4]    
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
MOD = 10**9 + 7

s = "ATGC"
t = ["AGC", "ACG", "GAC"]
# d = [defaultdict(int), {x+y+z: 1 for x in s for y in s for z in s if x+y+z not in t}]
d = [{"": 1}, defaultdict(int)]

# print(d[0])
for i in range(1, n+1):
    a = i%2
    b = (i-1)%2

    d[a] = defaultdict(int)
    for k in d[b]:
        for c in s:
            if len(k) < 2:
                d[a][k+c] += d[b][k]
                d[a][k+c] %= MOD
            elif len(k) == 2:
                if "AGC" not in [k+c, k[1]+k[0]+c, k[0]+c+k[1]]:
                    d[a][k+c] += d[b][k]
                    d[a][k+c] %= MOD
            elif "AGC" not in [k[1:]+c, k[0]+k[2]+c, k[2]+k[1]+c, k[1]+c+k[2], k[0]+k[1]+c]:
                # if len(set(k+c)) >= 3:
                #     print(k+c)
                d[a][k[1:]+c] += d[b][k]
                d[a][k[1:]+c] %= MOD
    # print(len(d[a]), sum(d[a].values()))
    # print(d[a])

print(sum(d[n%2].values()))

Submission status: Wrong Answer

Solution code:
N = int(input())
ptn1 = (N-3) * 2 * 4**(N-4)
ptn2 = (N-2) * 4**(N-3)
ptn3 = (N-3) * 4**(N-4) * 3 + 4**(N-3)

ans = ptn1 * 2 + ptn2 + ptn3 * 2
print((4**N-ans)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
ptn1 = (N-3) * 2 * 4**(N-3)
ptn2 = (N-2) * 4**(N-2)
ptn3 = (N-3) * 4**(N-3) * 3 + 4**(N-2)

ans = ptn1 * 2 + ptn2 + ptn3 * 2
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())

bad = []
bad.append('AGC')
bad.append('ACG')
bad.append('GAC')

def concat(li):
  return ''.join([str(l) for l in li])

import itertools
def init_dp(n):
  dp = {}
  for s in itertools.product(['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T'],['A', 'G', 'C', 'T']):
    st = concat(s)
    if st not in bad:
        dp[st] = n
  return dp

def update_dp(dp, next_dp, k, s):
  next4 = k + s
  
  # 3文字アウト
  for b in bad:
    if b in next4:
      return next_dp
    
  # 4文字アウト
  if next4[0] == 'A' and next4[2:] == 'GC':
    return next_dp
  if next4[0:2] == 'AG' and next4[3] == 'C':
    return next_dp
  
  # OK
  next_dp[next4[1:]] += dp[k]
  return next_dp

dp = init_dp(1)
for i in range(3, N):
  next_dp = init_dp(0)
  for k in dp.keys():
    for s in ['A', 'G', 'C', 'T']:
      next_dp = update_dp(dp, next_dp, k, s)
  dp = next_dp.copy()

mx = 10**9 + 7
ans = 0
for k in dp.keys():
  ans += dp[k] % mx
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

mod = 10**9*7

dp = [ [ [ [0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+1) ]


dp[0][3][3][3] = 1
#A=0,G=1,C=2,T=3とする

for len in range(N):
    #最後から1文字目
    for c1 in range(4):
        #最後から2文字目
        for c2 in range(4):
            #最後から3文字目
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0:
                    continue
                for c0 in range(4):
                    if c0 ==2 and c1 == 1 and c2 == 0:
                        continue
                    if c0 ==1 and c1 == 2 and c2 == 0:
                        continue
                    if c0 ==2 and c1 == 0 and c2 == 1:
                        continue
                    if c0 ==2 and c1 == 1 and c3 == 0:
                        continue
                    if c0 ==2 and c2 == 1 and c3 == 0:
                        continue
                    dp[len+1][c0][c1][c2] += dp[len][c1][c2][c3]
                    dp[len+1][c0][c1][c2] %= mod


ans = 0

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

Submission status: Wrong Answer

Solution code:
N = int(input())
c = 'AGC'
p = ['A', 'C', 'G', 'T']
s = 'XXX'
memo = [{} for _ in range(N)]


def agc_check(t):
    t1 = t[1] + t[0] + t[2] + t[3]
    t2 = t[0] + t[2] + t[1] + t[3]
    t3 = t[0] + t[1] + t[3] + t[2]
    if (c in t) or (c in t1) or (c in t2) or (c in t3):
        return 0
    else:
        return 1


def agc_plus(t, cur):
    if cur == N:
        return 1
    if t in memo[cur]:
        return memo[cur][t]
    else:
        r = 0
        for tt in p:
            if agc_check(t + tt):
                r += agc_plus(t[1:] + tt, cur + 1)
        memo[cur][t] = r
    return memo[cur][t]


ans = agc_plus(s, 0)
print(ans)