Problem:


Score : 400 points

Problem Statement

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

The string does not contain characters other than A, C, G and T.

The string does not contain AGC as a substring.

The condition above cannot be violated by swapping two adjacent characters once.

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Sample Input 1

3

Sample Output 1

61

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

Be sure to print the number of strings modulo 10^9+7.



Sample input:
3


Sample output:
61

Submission status: Accepted

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


dp = [ [ [ [0] * 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):
            if (i == 0 and j == 1 and k == 2) or \
               (i == 0 and j == 2 and k == 1) or \
               (i == 1 and j == 0 and k == 2):
                   continue

            dp[3][i][j][k] += 1

# print(dp[3])
# exit()

restriction = "AGCT" #0: A, 1:G, 2:C, 3:T

for i in range(4, N+1):

    for i2 in range(4):
        for j in range(4):
            for k in range(4): # i2,j,k
                for p in range(4):

                    # AGC, ACG, GAC
                    if   (j == 0 and k ==  1 and p == 2) or \
                         (j == 0 and k ==  2 and p == 1) or \
                         (j == 1 and k ==  0 and p == 2) : #or \
                             continue

                    if   (i2 == 0 and k == 1 and p == 2) or \
                         (i2 == 0 and j == 1 and p == 2) :
                             continue

                    dp[i][j][k][p] = (dp[i][j][k][p] + dp[i-1][i2][j][k]) % mod


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

Submission status: Accepted

Solution code:
N = int(input())
p = 10 ** 9 + 7
DP = [[0 for j in range(16)] for i in range(N)]
for i in range(16):
  DP[1][i] = 1
for i in range(2, N):
  DP[i][0] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p #0:AA
  DP[i][1] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][12]) % p #1:AC
  DP[i][2] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p #2:AG
  DP[i][3] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p #3:AT
  DP[i][4] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p #4:CA
  DP[i][5] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p #5:CC
  DP[i][6] = (DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p #6:CG
  DP[i][7] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p #7:CT
  DP[i][8] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p #8:GA
  DP[i][9] = (DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14] - DP[i - 2][2] - DP[i - 2][3]) % p #9:GC
  DP[i][10] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p #10:GG
  DP[i][11] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p #11:GT
  DP[i][12] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p #12:TA
  DP[i][13] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15] - DP[i - 2][2]) % p #13:TC
  DP[i][14] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p #14:TG
  DP[i][15] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p #15:TT
print(sum(DP[N - 1]) % p)

Submission status: Accepted

Solution code:
MOD = pow(10,9) + 7
# print(MOD)
chars = ["A","C","G","T"]
dict = {
    "A":0,
    "C":1,
    "G":2,
    "T":3
}
invDict = ["A","C","G","T"]
illegalFours = []
for c in chars:
    illegalFours.append("AGC"+c)
    illegalFours.append(c+"AGC")
    illegalFours.append("ACG"+c)
    illegalFours.append(c+"ACG")
    illegalFours.append("GAC"+c)
    illegalFours.append(c+"GAC")
    illegalFours.append("AG"+c+"C")
    illegalFours.append("A"+c+"GC")
illegalFours = list(set(illegalFours))
# print(illegalFours,len(illegalFours))
def isLegal(value):
    f1,q = divmod(value,64)
    f2,q = divmod(q,16)
    f3,q = divmod(q,4)
    f4 = q
    # print(f1,f2,f3,f4)
    string = invDict[f1] + invDict[f2] + invDict[f3] + invDict[f4]
    return(string not in illegalFours)
valueIsLegal = [isLegal(i) for i in range(4**4)]
# print(sum(valueIsLegal))

def calcNextValue(value,x):
    return((value*4 + x)%256)
    
def solve(x):
    if x==3:
        return(61)
    dp = [[0 for _ in range(x+1)] for _ in range(256)]
    for value in range(256):
        if valueIsLegal[value]:
            dp[value][4] = 1
        else:
            dp[value][4] = 0
    for k in range(4,x):
        for v in range(256):
            for i in range(4):
                w = calcNextValue(v,i)
                if valueIsLegal[w]:
                    dp[w][k+1] += dp[v][k]
                    dp[w][k+1] %= MOD
    ans = 0
    for v in range(256):
        ans += dp[v][x]
        ans %= MOD
    return(ans)

N = int(input())
print(solve(N))

Submission status: Accepted

Solution code:
print([0, 0, 0, 61, 230, 865, 3247, 12185, 45719, 171531, 643550, 2414454, 9058467, 33985227, 127504505, 478366600, 794717734, 733354121, 261943303, 776803305, 580025381, 51688048, 44657419, 737209731, 604119499, 159693437, 858533109, 639056669, 549054109, 996291083, 531294469, 23314687, 783022045, 855462856, 649970414, 68697295, 409213624, 604356692, 88638656, 978442997, 534833116, 763737161, 785892908, 123883652, 639213333, 181836645, 998121103, 124885216, 501575626, 39816123, 113468411, 799008836, 775465589, 256852905, 664630886, 971550783, 751629411, 51018086, 702530485, 725438992, 696683714, 792638194, 221791721, 149602322, 414054379, 986519078, 981760191, 305799096, 515140586, 406959393, 975058685, 245601370, 324759692, 673385295, 191483611, 570246669, 427196161, 781042769, 569725155, 842176273, 25328739, 847501730, 206282374, 353770801, 323137024, 371653459, 940737264, 123820509, 915711339, 847205021, 252858375, 718889563, 866398347, 738390145, 133009077, 333099663, 170591295, 329869205, 616680192, 597534442, 388130742][int(input())])

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 10**9 + 7

n = int(input())
cnt = {}
cnt[3] = defaultdict(lambda: 0)

def ok_quad(s):
  if 'AGC' not in s and 'AGC' not in s[1]+s[0]+s[2]+s[3] and 'AGC' not in s[0]+s[2]+s[1]+s[3] and 'AGC' not in s[0]+s[1]+s[3]+s[2]:
    return True
  else:
    return False
l = list('AGCT')
i = 3
for c1 in l:
  for c2 in l:
    for c3 in l:
      s = c1 + c2 + c3
      if s != 'AGC' and s != 'GAC' and s != 'ACG':
        cnt[i][s] += 1

for nn in range(4,n+1):
  cnt[nn] = defaultdict(lambda: 0)
  for ss in cnt[nn-1].keys():
    for c in l:
      sq = ss + c
      if ok_quad(sq):
        st = sq[1:]
        cnt[nn][st] += cnt[nn-1][ss] % mod

sm = sum(cnt[n].values()) % mod
print(sm)

Submission status: Accepted

Solution code:
from itertools import product
MOD = 10 ** 9 + 7

N = int(input())
dp = {}
for s in product('ATCG', repeat=3):
  dp[s] = int(s not in [('A','G','C'), ('G','A','C'), ('A','C','G'),])

for _ in range(3, N):
  ndp = {}
  for s in product('ATCG', repeat=3):
    if s[2] in ['A', 'T']:
      ndp[s] = sum([
        v for k,v in dp.items()
        if k[1] == s[0] and k[2] == s[1]
      ]) % MOD
    elif s[2] == 'G':
      ndp[s] = sum([
        v for k,v in dp.items()
        if (
          k[1] == s[0] and k[2] == s[1] and
          (k[1] != 'A' or k[2] != 'C')
        )
      ]) % MOD
    else:
      ndp[s] = sum([
        v for k,v in dp.items()
        if k[1] == s[0] and k[2] == s[1] and not (
          (k[1] == 'A' and k[2] == 'G') or
          (k[0] == 'A' and k[2] == 'G') or
          (k[1] == 'G' and k[2] == 'A') or
          (k[0] == 'A' and k[1] == 'G')
        )
      ]) % MOD
  dp = ndp
print(sum(dp.values()) % MOD)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

D = ['AAGC', 'GAGC', 'CAGC', 'TAGC', 'AGGC', 'ACGC', 'ATGC', 'AGCA', 'AGCG', 'AGCC', 'AGCT', 'AGAC', 'AGGC', 'AGTC']
D += ['ACGA', 'ACGG', 'ACGC', 'ACGT', 'AACG', 'GACG', 'CACG', 'TACG']
D += ['GACA', 'GACG', 'GACC', 'GACT', 'AGAC', 'GGAC', 'CGAC', 'TGAC']
m = {}
for a, b, c in it.product('AGCT', repeat = 3):
    S = a + b + c
    if not S in ['AGC', 'ACG', 'GAC']:
        m[S] = 1
cnt = 0
for _ in range(3, N):
    m2 = {}
    for key in m:
        for c in 'AGCT':
            S = key + c
            if not S in D:
                cnt += 1
                if S[1:] in m2:
                    m2[S[1:]] += m[key]
                    m2[S[1:]] %= MOD
                else:
                    m2[S[1:]] = m[key]
    m = m2
ans = 0
for key in m:
    ans += m[key]
    ans %= MOD
print ans

Submission status: Accepted

Solution code:
sets=["A","T","G","C"]
outs = ["AGC", "ACG","GAC"]
outs2 = ["ATGC","AGGC","AGTC"]
N = int(input())

befs = {}
afts = {}
for s in sets:
	for t in sets:
		for  u in sets:
			v = s+t+u
			if not v in outs:
				afts[s+t+u] = 1
				befs[s+t+u] = 1
#print([a for a in afts.keys()])
for i in range(4,N+1):
	for a in afts.keys():
		afts[a]=0
	for s in sets:
		for b in befs.keys():
			t = s+b
			if not t[:3] in outs and not t in outs2:
				afts[t[:3]] += befs[b]
	#print([a for a in afts.values()])
	for a in afts.keys():
		befs[a] = afts[a] %1000000007

ans = 0
for a in afts.keys():
	ans += afts[a]
ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# A,C,G,T: 0/1/2/3
answer = [1]*64;
answer[9]=0; #AGC
answer[6]=0; #ACG
answer[33]=0;#GAC

if(N>3):
    for i in range(3,N):
        new_answer = [0]*64;
        for j in range(64):
            if j==25 or j==37 or j==41 or j==45 or j==57:
                #CGC / GCC / GGC / GTC / TGC
                for k in range(1,4):
                    new_answer[j] += answer[j//4 + 16*k];
            else:
                for k in range(4):
                    new_answer[j] += answer[j//4 + 16*k];
            new_answer[9]=0;
            new_answer[6]=0;
            new_answer[33]=0;
        for j in range(64):
            answer[j]=new_answer[j];

total = 0;

for j in range(64):
    total += answer[j];

print(total % 1000000007);

Submission status: Accepted

Solution code:
N = int(input())
if N==3:
    print(61)
    exit()

MOD = 10**9+7
dp = [[0]*64 for i in range(N-2)]

A,C,G,T = 0,1,2,3
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==A and j==G and k==C: continue
            if i==A and j==C and k==G: continue
            if i==G and j==A and k==C: continue
            dp[0][i*16 + j*4+ k] = 1

for i in range(N-3):
    for j in range(64):
        a,b = divmod(j,16)
        b,c = divmod(b,4)
        for d in range(4):
            if b==A and c==G and d==C: continue
            if b==A and c==C and d==G: continue
            if b==G and c==A and d==C: continue
            if a==A and b==G and d==C: continue
            if a==A and c==G and d==C: continue
            dp[i+1][b*16+c*4+d] += dp[i][j]
            dp[i+1][b*16+c*4+d] %= MOD
print(sum(dp[-1]) % MOD)

Submission status: Accepted

Solution code:
def no(x, y, z, k):
    return ([y, z, k] == [1, 2, 3]) or ([y, z, k] == [2, 1, 3]) or ([y, z, k] == [1, 3, 2]) or ([x, z, k] == [1, 2, 3]) or ([x, y, k] == [1, 2, 3])

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][0][0][0] = 1
for i in range(n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for k in range(4):
                    if not no(x, y, z, k):
                        dp[i + 1][y][z][k] += dp[i][x][y][z]
                        dp[i + 1][y][z][k] %= MOD
ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    w = "ATCG"
    INF = 10 ** 9 + 7

    table = {}
    for c1 in w:
        for c2 in w:
            for c3 in w:
                table[c1 + c2 + c3] = 1
    NG = ["AGC", "ACG", "GAC"]
    for ng in NG:
        table[ng] = 0

    for i in range(N - 3):
        t = table.copy()
        for c1 in w:
            for c2 in w:
                for c3 in w:
                    s = c1 + c2 + c3
                    if s in NG:
                        continue

                    if c1 == "G" and c3 == "C" or c2 == "G" and c3 == "C":
                        res = 0
                        for c4 in "TCG":
                            ss = c4 + c1 + c2
                            res += table[ss] % INF
                            res %= INF
                        t[s] = res
                        continue
                    res = 0
                    for c4 in w:
                        ss = c4 + c1 + c2
                        res += table[ss] % INF
                        res %= INF
                    t[s] = res
        table = t

    res = 0
    for v in table.values():
        res += v % INF
        res %= INF
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

D = [[0 for j in range(64)] for i in range(N-2)]

for i in range(64):
    if i%4==0 and (i//4)%4==1 and  (i//16)%4==2:
        D[0][i]=0
    elif i%4==0 and (i//4)%4==2 and  (i//16)%4==1:
        D[0][i]=0
    elif i%4==1 and (i//4)%4==0 and  (i//16)%4==2:
        D[0][i]=0
    else:
        D[0][i]=1
for i in range(N-3):
    for j in range(64):
        for k in range(4):
            if (j//4)%4==0 and (j//16)%4==1 and  k==2:
                add = 0
            elif (j//4)%4==0 and (j//16)%4==2 and  k==1:
                add = 0
            elif (j//4)%4==1 and (j//16)%4==0 and  k==2:
                add = 0
            elif j%4==0 and (j//4)%4==1 and  k==2:
                add = 0
            elif j%4==0 and (j//16)%4==1 and  k==2:
                add = 0
            else:
                new_index=(j//4)%4+((j//16)%4)*4 + k*16
                D[i+1][new_index]=(D[i+1][new_index]+D[i][j])%(10**9+7)
                
                
print(sum(D[N-3])%(10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD=10**9+7
def swaps(s):
    for i in xrange(1, len(s)):
        yield s[:i-1]+s[i]+s[i-1]+s[i+1:]

n=int(raw_input())
cur={'':1}
for i in xrange(1, n+1):
    new = defaultdict(int)
    for k, v in cur.iteritems():
        for c in 'ACGT':
            k_ = (k+c)[-5:]
            if 'AGC' in k_ or any('AGC' in s for s in swaps(k_)): continue
            new[k_] = (new[k_]+v)%MOD
    #print(new)
    cur = new

total=0
for v in cur.itervalues():
    total = (total+v)%MOD
print(total)

Submission status: Accepted

Solution code:
N = int(input())
AAA, AAG, AAC, AAT, AGA, AGG, AGC, AGT, ACA, ACG, ACC, ACT, ATA, ATG, ATC, ATT, GAA, GAG, GAC, GAT, GGA, GGG, GGC, GGT, GCA, GCG, GCC, GCT, GTA, GTG, GTC, GTT, CAA, CAG, CAC, CAT, CGA, CGG, CGC, CGT, CCA, CCG, CCC, CCT, CTA, CTG, CTC, CTT, TAA, TAG, TAC, TAT, TGA, TGG, TGC, TGT, TCA, TCG, TCC, TCT, TTA, TTG, TTC, TTT = 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
for i in range(N-3):
    AAA, AAG, AAC, AAT, AGA, AGG, AGC, AGT, ACA, ACG, ACC, ACT, ATA, ATG, ATC, ATT, GAA, GAG, GAC, GAT, GGA, GGG, GGC, GGT, GCA, GCG, GCC, GCT, GTA, GTG, GTC, GTT, CAA, CAG, CAC, CAT, CGA, CGG, CGC, CGT, CCA, CCG, CCC, CCT, CTA, CTG, CTC, CTT, TAA, TAG, TAC, TAT, TGA, TGG, TGC, TGT, TCA, TCG, TCC, TCT, TTA, TTG, TTC, TTT = AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAG + GAG + CAG + TAG, AAG + GAG + CAG + TAG, 0, AAG + GAG + CAG + TAG, AAC + GAC + CAC + TAC, 0, AAC + GAC + CAC + TAC, AAC + GAC + CAC + TAC, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AGA + GGA + CGA + TGA, AGA + GGA + CGA + TGA, 0, AGA + GGA + CGA + TGA, AGG + GGG + CGG + TGG, AGG + GGG + CGG + TGG, GGG + CGG + TGG, AGG + GGG + CGG + TGG, AGC + GGC + CGC + TGC, AGC + GGC + CGC + TGC, GGC + CGC + TGC, AGC + GGC + CGC + TGC, AGT + GGT + CGT + TGT, AGT + GGT + CGT + TGT, GGT + CGT + TGT, AGT + GGT + CGT + TGT, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACG + GCG + CCG + TCG, ACG + GCG + CCG + TCG, GCG + CCG + TCG, ACG + GCG + CCG + TCG, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATG + GTG + CTG + TTG, ATG + GTG + CTG + TTG, GTG + CTG + TTG, ATG + GTG + CTG + TTG, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT
print((AAA + AAG + AAC + AAT + AGA + AGG + AGC + AGT + ACA + ACG + ACC + ACT + ATA + ATG + ATC + ATT + GAA + GAG + GAC + GAT + GGA + GGG + GGC + GGT + GCA + GCG + GCC + GCT + GTA + GTG + GTC + GTT + CAA + CAG + CAC + CAT + CGA + CGG + CGC + CGT + CCA + CCG + CCC + CCT + CTA + CTG + CTC + CTT + TAA + TAG + TAC + TAT + TGA + TGG + TGC + TGT + TCA + TCG + TCC + TCT + TTA + TTG + TTC + TTT)%(10**9+7))

Submission status: Accepted

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

ATCG = "ATCG"

memo = {}
def dfs(i, last):
    if i == N:
        return 1
    key = (i, last)
    if key in memo:
        return memo[key]
    p = None
    l2 = last[-2:]
    if l2 == "AC":
        p = "G"
    elif l2 == "AG":
        p = "C"
    elif l2 == "GA":
        p = "C"
    elif last == "AGG" or last == "ATG" or last == "AGT":
        p = "C"
    res = 0
    for c in ATCG:
        if c == p:
            continue
        res += dfs(i+1, last[1:] + c)
    memo[key] = res = res % MOD
    return res
print(dfs(0, "***"))

Submission status: Accepted

Solution code:
N=int(input())
mod=10**9+7
acgt=['A','C','G','T']
bef=dict()
from collections import defaultdict
banc=['AGC','GAC','ACG']
for x in acgt:
    for y in acgt:
        for z in acgt:
            if x+y+z not in banc:
                bef[x+y+z]=1
ban=[]
for w in acgt:
    for v in banc:
        ban.append(w+v)
    ban.append('A'+w+'GC')
    ban.append('AG'+w+'C')
for i in range(3,N):
    befc=bef.copy()
    bef=defaultdict(int)
    for b in befc.keys():
        for nex in acgt:
            if b+nex not in ban:
                bef[b[1:]+nex]=(bef[b[1:]+nex]+befc[b])%mod
ans=0
for cnt in bef.values():
    ans=(ans+cnt)%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
dp = [[[1] * 4 for _ in [0] * 4] for _ in [0] * 4]
dp[0][2][1] = 0
dp[0][1][2] = 0
dp[2][0][1] = 0
for _ in range(n - 3):
    ndp = [[[0] * 4 for _ in [0] * 4] for _ in [0] * 4]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (i, k, l) == (0, 2, 1) or (i, j, l) == (0, 2, 1):
                        pass
                    else:
                        ndp[j][k][l] += dp[i][j][k]
    dp = ndp
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[j][k][l] %= MOD
print(sum(z for x in dp for y in x for z in y) % MOD)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
i = 3
ans = 61
dpm = {
    "".join(k): 1
    for k in product("ACGT", repeat=3)
}
for k in ("AGC", "ACG", "GAC"):
    dpm[k] = 0

MOD = 1000000007

while i < n:
    ndpm = {k: 0 for k in dpm}
    for k in dpm:
        for c in "ACGT":
            ns = k + c
            if ns[-3:] in ("AGC", "ACG", "GAC") or \
                    (ns[0] == "A" and ns[-2:] == "GC") or \
                    (ns[0:2] == "AG" and ns[-1] == "C"):
                continue
            ndpm[ns[-3:]] += dpm[k] % MOD
    dpm = ndpm
    i += 1

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict as ddic
from itertools import combinations, permutations, product
from heapq import heappush, heappop, heapify
import sys
stdout = sys.stdout
rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

MOD = 10**9 + 7
memo = {}
banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG', 'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

def dp(letters, state):
    if state in banned:
        return 0
    if letters == 0:
        return 1
    if (letters, state) in memo:
        return memo[letters, state]
    
    ans = 0
    for c in 'ACGT':
        ans += dp(letters - 1, (state + c)[-4:])
        ans %= MOD
    ans %= MOD
    memo[letters, state] = ans
    return ans

print(dp(rri(), ''))

Submission status: Runtime Error

Solution code:
from copy import deepcopy

def getval():
    n = int(input())
    return n

def main(n):
    mod = 10**9 + 7
    #A:0 C:1 G:2 T:3
    dp = [[[1 for i in range(4)] for i in range(4)] for i in range(4)]
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0

    def pow4(arr):
        ans = 0
        for i in range(4):
            ans += arr[i]*(4**(3-i))
        return ans 

    p = []
    for i in range(4):
        p.append(pow4([0,2,1,i]))
        p.append(pow4([0,1,2,i]))
        p.append(pow4([2,0,1,i]))
        p.append(pow4([i,0,2,1]))
        p.append(pow4([i,0,1,2]))
        p.append(pow4([i,2,0,1]))
        p.append(pow4([0,i,2,1]))
        p.append(pow4([0,2,i,1]))

    it1 = iter(p)
    it2 = iter(p)
    co = 0
    di = dict(zip(it1,it2))
    for i in range(n-3):
        temp = [[[0 for i in range(4)] for i in range(4)] for i in range(4)]
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for d in range(4):
                        if pow4([a,b,c,d]) in di:
                            temp[b][c][d] += 0
                        else:
                            temp[b][c][d] += dp[a][b][c]
                            temp[b][c][d] %= mod
        dp = temp

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

if __name__=="__main__":
    n = getval()
    main(n)

Submission status: Runtime Error

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
from decorator import stop_watch


@stop_watch
def solve(N):
    mod = 10 ** 9 + 7
    dp = [{} for _ in range(N + 1)]
    dp[0].setdefault('TTT', 1)

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

    for i in range(1, N + 1):
        for last3, count in dp[i - 1].items():
            for c in 'AGCT':
                if check(last3 + c):
                    new_last3 = last3[1:] + c
                    dp[i].setdefault(last3[1:] + c, 0)
                    dp[i][new_last3] = (dp[i][new_last3] + count) % mod

    print(sum(dp[-1].values()) % mod)


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Runtime Error

Solution code:
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: Runtime Error

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-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    print(memo)
    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: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

input_n = lambda: int(readline())
input_nn = lambda: map(int, readline().split())
input_s = lambda: readline().rstrip().decode('utf-8')
input_ss = lambda: readline().rstrip().decode('utf-8').split()

mod = 10 ** 9 + 7


@njit('(i4,i4,i4,i4)', cache=True)
def judge(a, b, c, k):

    ret = False
    ret |= (b == 0 and c == 2 and k == 1)
    ret |= (b == 0 and c == 1 and k == 2)
    ret |= (b == 2 and c == 0 and k == 1)
    ret |= (a == 0 and b == 2 and k == 1)
    ret |= (a == 0 and c == 2 and k == 1)

    return not ret


@njit('(i4,i4[:,:,:])', cache=True)
def solve(N, dp):

    for n in range(N - 3):
        next_dp = np.zeros((4, 4, 4), np.int32)
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for k in range(4):
                        if judge(a, b, c, k):
                            next_dp[b, c, k] += dp[a, b, c]
                            next_dp[b, c, k] %= mod
        dp = next_dp

    return dp


def main():

    N = input_n()
    dp = np.full((4, 4, 4), 1, np.int32)
    dp[0, 2, 1] = 0
    dp[0, 1, 2] = 0
    dp[2, 0, 1] = 0

    ans = solve(N, dp)
    print(ans.sum() % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
mod=10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)//3
    if n<0 or m<0 or n<m:
        print(0)
        exit()
    else:
        print(mod_combinations_count(n,m,mod)%mod)

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
mod=10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def mod_combinations_cont(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    m=(-x+2*y)/3
    if n<0 or m<0:
        print(0)
        exit()
    else:
        print(mod_combinations_cont(n,m,mod)%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce

MOD = 1_000_000_000 + 7
LETTERS = ["A", "C", "G", "T"]
PROHIBIT = ["AGC", "ACG", "GAC", "AGGC", "AGTC", "ATGC"]

def main():
    n = int(input().strip())

    table = {}

    for first in LETTERS:
        for second in LETTERS:
            for third in LETTERS:
                codon = first+second+third
                if not codon in PROHIBIT:
                    table[codon] = [1]

    for i in range(n-3):
        for codon in table.keys():
            table[codon].append(0)

        for codon in table.keys():
            for append in LETTERS:
                three_letters = codon[1:] + append
                four_letters = codon + append

                if (not four_letters in PROHIBIT) and (not three_letters in PROHIBIT):
                    table[three_letters][i+1] = (table[three_letters][i+1] + table[codon][i]) % MOD

    print(reduce(lambda acc, x: (acc + x[-1]) % MOD, table.values(), 0))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a