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())
aaa = [1]
aat = [1]
aac = [1]
aag = [1]
ata = [1]
att = [1]
atc = [1]
atg = [1]
aca = [1]
act = [1]
acc = [1]
aga = [1]
agt = [1]
agg = [1]
taa = [1]
tat = [1]
tac = [1]
tag = [1]
tta = [1]
ttt = [1]
ttc = [1]
ttg = [1]
tca = [1]
tct = [1]
tcc = [1]
tcg = [1]
tga = [1]
tgt = [1]
tgc = [1]
tgg = [1]
caa = [1]
cat = [1]
cac = [1]
cag = [1]
cta = [1]
ctt = [1]
ctc = [1]
ctg = [1]
cca = [1]
cct = [1]
ccc = [1]
ccg = [1]
cga = [1]
cgt = [1]
cgc = [1]
cgg = [1]
gaa = [1]
gat = [1]
gag = [1]
gta = [1]
gtt = [1]
gtc = [1]
gtg = [1]
gca = [1]
gct = [1]
gcc = [1]
gcg = [1]
gga = [1]
ggt = [1]
ggc = [1]
ggg = [1]
for i in range(n-3):
    aaa.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aat.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aac.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    aag.append((aaa[i]+taa[i]+caa[i]+gaa[i])%(10**9+7))
    ata.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    att.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    atc.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    atg.append((aat[i]+tat[i]+cat[i]+gat[i])%(10**9+7))
    aca.append((aac[i]+tac[i]+cac[i])%(10**9+7))    
    act.append((aac[i]+tac[i]+cac[i])%(10**9+7))   
    acc.append((aac[i]+tac[i]+cac[i])%(10**9+7))   
    aga.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7)) 
    agt.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7)) 
    agg.append((aag[i]+tag[i]+cag[i]+gag[i])%(10**9+7))
    taa.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tat.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tac.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7))
    tag.append((ata[i]+tta[i]+cta[i]+gta[i])%(10**9+7)) 
    tta.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttt.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttc.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7))
    ttg.append((att[i]+ttt[i]+ctt[i]+gtt[i])%(10**9+7)) 
    tca.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tct.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tcc.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7))
    tcg.append((atc[i]+ttc[i]+ctc[i]+gtc[i])%(10**9+7)) 
    tga.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgt.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgc.append((ttg[i]+ctg[i]+gtg[i])%(10**9+7))
    tgg.append((atg[i]+ttg[i]+ctg[i]+gtg[i])%(10**9+7)) 
    caa.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cat.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cac.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cag.append((aca[i]+tca[i]+cca[i]+gca[i])%(10**9+7))
    cta.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctt.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctc.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    ctg.append((act[i]+tct[i]+cct[i]+gct[i])%(10**9+7))
    cca.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    cct.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    ccc.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    ccg.append((acc[i]+tcc[i]+ccc[i]+gcc[i])%(10**9+7))
    cga.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgt.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgc.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    cgg.append((tcg[i]+ccg[i]+gcg[i])%(10**9+7))
    gaa.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gat.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gag.append((aga[i]+tga[i]+cga[i]+gga[i])%(10**9+7))
    gta.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtt.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtc.append((tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gtg.append((agt[i]+tgt[i]+cgt[i]+ggt[i])%(10**9+7))
    gca.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gct.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gcc.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gcg.append((tgc[i]+cgc[i]+ggc[i])%(10**9+7))
    gga.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggt.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggc.append((tgg[i]+cgg[i]+ggg[i])%(10**9+7))
    ggg.append((agg[i]+tgg[i]+cgg[i]+ggg[i])%(10**9+7))
print((aaa[-1]+aat[-1]+aac[-1]+aag[-1]+ata[-1]+att[-1]+atc[-1]+atg[-1]+aca[-1]+act[-1]
      +acc[-1]+aga[-1]+agt[-1]+agg[-1]+taa[-1]+tat[-1]+tac[-1]+tag[-1]+tta[-1]+ttt[-1]
      +ttc[-1]+ttg[-1]+tca[-1]+tct[-1]+tcc[-1]+tcg[-1]+tga[-1]+tgt[-1]+tgc[-1]+tgg[-1]
      +caa[-1]+cat[-1]+cac[-1]+cag[-1]+cta[-1]+ctt[-1]+ctc[-1]+ctg[-1]+cca[-1]+cct[-1]
      +ccc[-1]+ccg[-1]+cga[-1]+cgt[-1]+cgc[-1]+cgg[-1]+gaa[-1]+gat[-1]+gag[-1]+gta[-1]
      +gtt[-1]+gtc[-1]+gtg[-1]+gca[-1]+gct[-1]+gcc[-1]+gcg[-1]+gga[-1]+ggt[-1]+ggc[-1]+ggg[-1])%(10**9+7))

Submission status: Accepted

Solution code:
def check(s):
    c = False
    if s[:3] == "AGC" or s[1:] == "AGC" or s[0] + s[2:] == "AGC" or s[:2] + s[3] == "AGC" or s[:3] == "ACG" or s[1:] == "ACG" or s[:3] == "GAC" or s[1:] == "GAC":
        c = True
    return c

from collections import defaultdict
from itertools import product
N = int( input())
Q = 10**9 + 7
dp = [ defaultdict( int) for _ in range(N+1)]

for s in product("AGCT", repeat = 3):
    dp[3]["".join(s)] = 1
ans = 0
for i in range(4, N+1):
    for c in product("AGCT", repeat = 3):
        c = "".join(c)
        for t in "AGCT":
            if check(c+t):
                # print(c+t, dp[i-1][c])
                ans += (dp[i-1][c]*pow(4,N-i,Q))%Q
                ans %= Q
            else:
                dp[i][c[1:]+t] += dp[i-1][c]
                dp[i][c[1:]+t] %= Q
if N == 3:
    ans = 3
print( (pow(4,N,Q) - ans)%Q)

Submission status: Accepted

Solution code:
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]
memo = [{} for _ in range(N+1)]

def func(cur, S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    if S[-3:] in memo[cur]:
        return memo[cur][S[-3:]]
    else:
        if cur==N:
            return 1
        ret = 0
        for s in "ACGT":
            ret = ret + func(cur+1, S+s)
        memo[cur][S[-3:]] = ret
        return ret


print(func(0, "____")%(10**9+7))

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int):
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    # A:0, G:1, C:2, T:3
    chars = ['A', 'G', 'C', 'T']
    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[3][i][j][k] = 1
    dp[3][0][1][2] = 0
    dp[3][0][2][1] = 0
    dp[3][1][0][2] = 0
    cnt = 0
    for i in range(3, N):
        for j1, c1 in enumerate(chars):
            for j2, c2 in enumerate(chars):
                for j3, c3 in enumerate(chars):
                    for j4, c4 in enumerate(chars):
                        cs4 = c1+c2+c3+c4
                        cs3 = c2+c3+c4
                        if 'AGC'==cs3 or 'ACG'==cs3 or 'GAC'==cs3 or 'AAGC'==cs4 or 'ACGC'==cs4 or 'AGGC'==cs4 or 'ATGC'==cs4 or 'AGAC'==cs4 or 'AGGC'==cs4 or 'AGCC'==cs4 or 'AGTC'==cs4:
                            continue
                        cnt += 1
                        dp[i+1][j2][j3][j4] += dp[i][j1][j2][j3]
                        dp[i+1][j2][j3][j4] %= MOD
    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans += dp[N][i][j][k]
                ans %= MOD
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A=0;G=1;C=2;T=3
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)]
mod=10**9+7
dp[0][T][T][T]=1
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 (k==A and l==G and m==C):
                        continue
                    if (k==G and l==A and m==C):
                        continue
                    if (k==A and l==C and m==G):
                        continue
                    if (j==A and l==G and m==C):
                        continue
                    if (j==A and k==G and m==C):
                        continue
                    dp[i+1][k][l][m]+=dp[i][j][k][l]
                    dp[i+1][k][l][m]%=mod
ans=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans+=dp[N][i][j][k]
            ans%=mod
print(ans)

Submission status: Accepted

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

def ok(last4:str)->bool:
    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(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
import functools


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


@functools.lru_cache(maxsize=None)
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


@functools.lru_cache(maxsize=None)
def dfs(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
    return ret


print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())

#################
N = int(input())
mod = 1000000007
A=0
T=1
C=2
G=3
dp = [[[[0,0,0,0] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

for j in range(4):
    for k in range(4):
        for l in range(4):
            dp[3][j][k][l] = 1
dp[3][A][G][C],dp[3][A][C][G],dp[3][G][A][C] = 0,0,0

for i in range(4,N+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] += (dp[i-1][A][j][k]+dp[i-1][T][j][k]+dp[i-1][C][j][k]+dp[i-1][G][j][k]) % mod
                dp[i][j][k][l] %= mod



    dp[i][A][G][C],dp[i][A][C][G],dp[i][G][A][C] = 0,0,0

    dp[i][T][G][C] -= dp[i-1][A][T][G]

    dp[i][G][G][C] -= dp[i-1][A][G][G]
    #dp[i][G][A][C] -= dp[i-1][A][G][A]
    dp[i][G][T][C] -= dp[i-1][A][G][T]

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

Submission status: Accepted

Solution code:
def ok(last4):
    ret = True
    if last4 in ["ATGC","AGGC","AGTC"]:
        ret = False
    elif True in [s in last4 for s in ["AGC","ACG","GAC"]]:
        ret = False
    return ret
N = int(input())
mod = 10**9+7
memo = [{} for i in range(N+1)]

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

print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
I=1000000007
n=int(input())
s=["A","C","G","T"]
List=["AGCA","AGCC","AGCG","AGCT","ACGA","ACGC","ACGG","ACGT","GACA","GACC","GACG","GACT","AAGC","CAGC","GAGC","TAGC","CACG","AACG","TACG","AGAC","CGAC","GGAC","TGAC","ATGC","AGGC","AGTC"]
dp=[[0]*(64) for i in range(n-2)]
for i in range(64):
    if i not in {6,9,33}:
        dp[0][i]=1
if n==3:
    print(61)
else:
    for i in range(n-3):
        for a in range(len(s)):
            for b in range(len(s)):
                for c in range(len(s)):
                    for d in range(len(s)):
                        if s[a]+s[b]+s[c]+s[d] not in List:
                            dp[i+1][b*16+c*4+d]=(dp[i+1][b*16+c*4+d]+dp[i][a*16+b*4+c])%I

    print(sum(dp[-1])%I)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
A,T,G,C=[0]*(n+1),[0]*(n+1),[0]*(n+1),[0]*(n+1)
A[1],A[2],A[3]=1,4,16
T[1],T[2],T[3]=1,4,16
C[1],C[2],C[3]=1,4,14
G[1],G[2],G[3]=1,4,15
S=[0]*(n+1)
S[1],S[2],S[3]=4,16,61
for i in range(4,n+1):
    A[i],T[i]=S[i-1],S[i-1]
    C[i]=S[i-1]-(A[i-2]+G[i-2]+A[i-3]*3)
    G[i]=S[i-1]-(A[i-2]-G[i-3])
    S[i]=(A[i]+T[i]+C[i]+G[i])%mod
print(S[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product

def cnt(N):
    ret = 0
    for s in product('ACGT', repeat=N):
        s = ''.join(s)
        if 'AGC' in s or 'GAC' in s or 'ACG' in s:
            continue
        if 'AGGC' in s or 'ATGC' in s or 'AGTC' in s:
            continue
        ret += 1
    return ret

def main():
    N = II()
    ans = 0
    dp = {'':1, 'A':0, 'G':0, 'GA':0, 'AC':0, 'AT':0, 'AG':0,
        'ATG':0, 'AGT':0, 'AGG':0}
    for _ in range(N):
        tmp = {}
        tmp[''] = dp[''] * 2 + dp['G'] * 2 + \
            dp['AC'] * 2 + dp['AT'] * 2 + \
            dp['ATG'] * 1 + dp['AGT'] * 1 + dp['AGG'] * 1
        tmp['A'] = dp[''] + dp['A'] + dp['GA'] + dp['AC'] + dp['AT'] + dp['AGT']
        tmp['G'] = dp[''] + dp['G'] + dp['AGG'] + dp['ATG'] + dp['AGT']
        tmp['GA'] = dp['G'] + dp['AG'] + dp['ATG'] + dp['AGG']
        tmp['AC'] = dp['A']
        tmp['AT'] = dp['A'] + dp['GA']
        tmp['AG'] = dp['A'] + dp['GA']
        tmp['ATG'] = dp['AT']
        tmp['AGT'] = dp['AG']
        tmp['AGG'] = dp['AG']
        dp = tmp
    ans = sum(v for v in dp.values())

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
a=[[0 for i in range(64)] for j in range(101)]
a[3]=[1 for i in range(64)]
a[3][6],a[3][9],a[3][18]=0,0,0
for i in range(4,N+1):
  a[i][0]=(a[i-1][0]+a[i-1][16]+a[i-1][32]+a[i-1][48])%MOD
  a[i][1]=a[i][0]
  a[i][2]=a[i][0]
  a[i][3]=a[i][0]
  a[i][4]=(a[i-1][1]+a[i-1][17]+a[i-1][33]+a[i-1][49])%MOD
  a[i][5]=a[i][4]
  a[i][6]=0
  a[i][7]=a[i][4]
  a[i][8]=(a[i-1][2]+a[i-1][18]+a[i-1][34]+a[i-1][50])%MOD
  a[i][9]=0
  a[i][10]=a[i][8]
  a[i][11]=a[i][8]
  a[i][12]=(a[i-1][3]+a[i-1][19]+a[i-1][35]+a[i-1][51])%MOD
  a[i][13]=a[i][12]
  a[i][14]=a[i][12]
  a[i][15]=a[i][12]
  a[i][16]=(a[i-1][4]+a[i-1][20]+a[i-1][36]+a[i-1][52])%MOD
  a[i][17]=a[i][16]
  a[i][18]=0
  a[i][19]=a[i][16]
  a[i][20]=(a[i-1][5]+a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][21]=a[i][20]
  a[i][22]=(a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][23]=a[i][20]
  a[i][24]=(a[i-1][6]+a[i-1][22]+a[i-1][38]+a[i-1][54])%MOD
  a[i][25]=a[i][24]
  a[i][26]=a[i][24]
  a[i][27]=a[i][24]
  a[i][28]=(a[i-1][7]+a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][29]=a[i][28]
  a[i][30]=(a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][31]=a[i][28]
  a[i][32]=(a[i-1][8]+a[i-1][24]+a[i-1][40]+a[i-1][56])%MOD
  a[i][33]=a[i][32]
  a[i][34]=a[i][32]
  a[i][35]=a[i][32]
  a[i][36]=(a[i-1][9]+a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][37]=a[i][36]
  a[i][38]=(a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][39]=a[i][36]
  a[i][40]=(a[i-1][10]+a[i-1][26]+a[i-1][42]+a[i-1][58])%MOD
  a[i][41]=a[i][40]
  a[i][42]=a[i][40]
  a[i][43]=a[i][40]
  a[i][44]=(a[i-1][11]+a[i-1][27]+a[i-1][43]+a[i-1][59])%MOD
  a[i][45]=a[i][44]
  a[i][46]=a[i][44]
  a[i][47]=a[i][44]
  a[i][48]=(a[i-1][12]+a[i-1][28]+a[i-1][44]+a[i-1][60])%MOD
  a[i][49]=a[i][48]
  a[i][50]=a[i][48]
  a[i][51]=a[i][48]
  a[i][52]=(a[i-1][13]+a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][53]=a[i][52]
  a[i][54]=(a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][55]=a[i][52]
  a[i][56]=(a[i-1][14]+a[i-1][30]+a[i-1][46]+a[i-1][62])%MOD
  a[i][57]=a[i][56]
  a[i][58]=a[i][56]
  a[i][59]=a[i][56]
  a[i][60]=(a[i-1][15]+a[i-1][31]+a[i-1][47]+a[i-1][63])%MOD
  a[i][61]=a[i][60]
  a[i][62]=a[i][60]
  a[i][63]=a[i][60]
print(sum(a[N])%MOD)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc122/tasks/abc122_d

import itertools
import collections
import bisect

dp = [{} for _ in range(101)]

def is_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') > 0:
            return False
    return True


def solve(rest, lastt):
    if rest == 0:
        # print(lastt[2:])
        return 1
    if lastt in dp[rest]:
        return dp[rest][lastt]

    val = 0
    for c in 'AGCT':
        if is_ok(lastt + c):
            val += solve(rest - 1, lastt[1:] + c)
    dp[rest][lastt] = val
    return dp[rest][lastt]


def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    print(solve(N, 'ZZZ') % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import functools


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


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


@functools.lru_cache(maxsize=None)
def dfs(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
    return ret


print(dfs(0, 'TTT'))

Submission status: Accepted

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

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

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

print(dfs(0, 'TTT'))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


# inputs
N = 0


def set_inputs():
    global N
    N = get_int()
    return


DIVISOR = 1000000007


def main():
    setrecursionlimit(100000)
    set_inputs()

    # ACG, AGC, GAC, AGGC, AGTC, ATGC
    safe = [0] * (N+1)
    a = [0] * (N+1)
    g = [0] * (N+1)
    ac = [0] * (N+1)
    ag = [0] * (N+1)
    at = [0] * (N+1)
    ga = [0] * (N+1)
    agg = [0] * (N+1)
    agt = [0] * (N+1)
    atg = [0] * (N+1)

    safe[0] = 1
    for i in range(1, N+1):
        s = safe[i-1] * 2
        s += g[i-1] * 2
        s += ac[i-1] * 2
        s += at[i-1] * 2
        s += agg[i-1]
        s += agt[i-1]
        s += atg[i-1]
        safe[i] = s % DIVISOR

        a_ = safe[i-1]
        a_ += a[i-1]
        a_ += ac[i-1]
        a_ += at[i-1]
        a_ += ga[i-1]
        a_ += agt[i-1]
        a[i] = a_ % DIVISOR

        g_ = safe[i-1]
        g_ += g[i-1]
        g_ += agg[i-1]
        g_ += agt[i-1]
        g_ += atg[i-1]
        g[i] = g_ % DIVISOR

        ac[i] = a[i-1]
        ag[i] = ( a[i-1] + ga[i-1]) % DIVISOR
        at[i] = ( a[i-1] + ga[i-1]) % DIVISOR
        ga[i] = ( g[i-1] + ag[i-1] + agg[i-1] + atg[i-1]) % DIVISOR
        agg[i] = ag[i-1]
        agt[i] = ag[i-1]
        atg[i] = at[i-1]

        # dead = ( ac[i-1] + ag[i-1] + ga[i-1] + agg[i-1] + agt[i-1] + atg[i-1]) % DIVISOR
    print((safe[N] + a[N] + g[N] + ac[N] + ag[N] + at[N] + ga[N] + agg[N] + agt[N] + atg[N]) % DIVISOR)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n = int(input())

x = ['A','G','C','T']

dame = ['AGC','GAC','ACG']

o = 'AGC'

for ap in x:
    dame.append(o[0]+ap+o[1:])
    dame.append(o[:-1]+ap+o[-1])


l = list(itertools.product(x,x,x))

ll = len(l)
D = 10**9+7
for i in range(ll):
    l[i] = ''+l[i][0]+l[i][1]+l[i][2]
cnt = [1]*len(l)

for i in range(3,n):
    new_cnt = [0]*ll
    for j in range(ll):
        for ap in x:
            s = l[j]+ap
            if s in dame or s[1:] in dame or s[:-1] in dame:
                continue
            else:
                new_cnt[l.index(s[1:])]+=cnt[j]
    cnt = new_cnt
    for j in range(ll):
        cnt[j] %= D
res = 0
for i in range(ll):
    if l[i] not in dame:
        res += cnt[i] 
print(res%D)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

import numpy as np

mod = 10 ** 9 + 7

def question():
    n = int(input())

    a = [0] * (n+1)
    a[1] = 1
    a[2] = 4
    a[3] = 16

    t = [0] * (n+1)
    t[1] = 1
    t[2] = 4
    t[3] = 16

    c = [0] * (n+1)
    c[1] = 1
    c[2] = 4
    c[3] = 14

    g = [0] * (n+1)
    g[1] = 1
    g[2] = 4
    g[3] = 15

    for i in range(3, n):
        a[i + 1] = a[i] + t[i] + c[i] + g[i]
        t[i + 1] = a[i] + t[i] + c[i] + g[i]
        c[i + 1] = a[i] + t[i] + c[i] + g[i] - (a[i-1] + 3 * a[i-2] + g[i-1])
        g[i + 1] = a[i] + t[i] + c[i] + g[i] - (a[i-1] - g[i-2])

        #a[i+1] = a[i+1] % mod
        #t[i+1] = t[i+1] % mod
        #c[i+1] = c[i+1] % mod
        #g[i+1] = g[i+1] % mod

    print((a[n]+t[n]+c[n]+g[n]) % mod)


question()

Submission status: Accepted

Solution code:
n=int(input())
x=10**9+7
sa=[1,4,16]
sg=[1,4,15]
sc=[1,4,14]
st=[1,4,16]
for i in range(3,n):
    sa.append(sa[i-1]+sg[i-1]+sc[i-1]+st[i-1])
    sg.append(sa[i-1]+sg[i-1]+(sc[i-1]-sa[i-2]+sg[i-3])+st[i-1])
    sc.append((sa[i-1]-sg[i-2])+(sg[i-1]-sa[i-2]-sa[i-3]-sa[i-3])+(sc[i-1])+(st[i-1]-sa[i-3]))
    st.append(sa[i-1]+sg[i-1]+sc[i-1]+st[i-1])
n=n-1
print((sa[n]+sg[n]+sc[n]+st[n])%x)

Submission status: Accepted

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

dp_A = [1] + [0] * (N + 5)
dp_G = [1] + [0] * (N + 5)
dp_C = [1] + [0] * (N + 5)
dp_T = [1] + [0] * (N + 5)
dp_AG = [0] * (N + 5)
dp_AC = [0] * (N + 5)
dp_GA = [0] * (N + 5)
dp_AGA = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_AGT = [0] * (N + 5)
dp_AAG = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_ATG = [0] * (N + 5)
dp_ok = [4] + [0] * (N + 5)
#ng=AGC,ACG,GAC,AG*C,A*GC
for i in range(1, N):
    dp_A[i] = dp_ok[i - 1]
    dp_C[i] = dp_ok[i - 1] - dp_AG[i - 1] - dp_GA[i - 1] - dp_AGG[
        i - 1] - dp_AGT[i - 1] - dp_ATG[i - 1]
    dp_C[i] %= mod
    dp_G[i] = dp_ok[i - 1] - dp_AC[i - 1]
    dp_G[i] %= mod
    dp_T[i] = dp_ok[i - 1]
    dp_T[i] %= mod
    dp_AG[i] = dp_A[i - 1]
    dp_AG[i] %= mod
    dp_AC[i] = dp_A[i - 1] - dp_GA[i - 1]
    dp_AC[i] %= mod
    dp_GA[i] = dp_G[i - 1]
    dp_GA[i] %= mod
    dp_AGG[i] = dp_AG[i - 1]
    dp_AGG[i] %= mod
    dp_AGT[i] = dp_AG[i - 1]
    dp_AGT[i] %= mod
    dp_ATG[i] = dp_A[i - 2]
    dp_ATG[i] %= mod
    dp_ok[i] = dp_A[i] + dp_C[i] + dp_G[i] + dp_T[i]
    dp_ok[i] %= mod
print(dp_ok[N - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m
    
    def add(self, a, b):
        return (a + b ) % self.m

    def sub(self, a, b):
        return (a - b) % self.m
    
    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    def pow(self, x, y):
        if y == 0: 
            return 1
        elif y == 1: 
            return x % self.m
        elif y % 2 == 0: 
            return self.pow(x, y//2)**2 % self.m
        else: 
            return self.pow(x, y//2)**2 * x % self.m


@mt
def slv(N):
    if N==3:
        return 61

    m = Mod(10**9+7)
    dp = {}
    iv = [
        'agc',
        'acg',
        'gac',
        'aggc'
        'acgc',
        'atgc',
        'agac',
        'aggc',
        'agtc',
    ]
    for s in product('agct', repeat=4):
        s = ''.join(s)
        if not any(map(lambda x: x in s, iv)):
            dp[s] = 1

    for _ in range(N-4):
        dp_ = Counter()
        for k, v in dp.items():
            for c in 'agct':
                s = k + c
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        dp = dp_
    
    ans = 0
    for k, v in dp.items():
        ans = m.add(ans, v)


    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D
N = int(input())

res_dict = dict()
for i0 in "ACGT":
    for i1 in "ACGT":
        for i2 in "ACGT":
            s = i0+i1+i2
            if s in ["AGC", "ACG", "GAC"]:
                res_dict[s] = [0, 0, 0, 0] + [0]*(N-3)
            else:
                res_dict[s] = [0, 0, 0, 1] + [0]*(N-3)

for i in range(3, N):
    for k in res_dict.keys():
        for add in "ACGT":
            s = k + add
            if k[1:] + add in ["AGC", "ACG", "GAC"] or k[:2] + add == "AGC" or k[0] + k[2] + add == "AGC":
                pass
            else:
                res_dict[s[1:]][i+1] += res_dict[k][i]
                
print(sum([res_dict[s][N] for s in res_dict.keys()]) % (10**9+7))

Submission status: Accepted

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

mp=['A','C','G','T']
out=['AGC','ACG','GAC']

dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if mp[k]+mp[j]+mp[i] in out:continue
            dp[2][i][j][k]=1

for k in range(3,N):
    for x in range(4):
        for y in range(4):
            for i in range(4):
                for j in range(4):
                    if mp[i]+mp[y]+mp[x] in out:continue
                    if mp[j]+mp[y]+mp[x] == 'AGC': continue
                    if mp[j]+mp[i]+mp[x] == 'AGC': continue
                    #print(mp[j]+mp[i]+mp[y]+mp[x])
                    dp[k][x][y][i] = (dp[k][x][y][i] + dp[k-1][y][i][j])%MOD
#for d in dp:
#    print(d)
res=0
for d in dp[-1]:
    for row in d:
        res=(res+sum(row))%MOD
print(res)

"""
print('------------')
cnt=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                if (mp[a]+mp[b]+mp[c] in out) or (mp[b]+mp[c]+mp[d] in out): continue
                print(mp[a]+mp[b]+mp[c]+mp[d])
                cnt+=1
print(cnt)
"""

Submission status: Accepted

Solution code:
N = int(input())

S = 'AGCT'  # AGCT = 0123
num = [[[1]*4 for _ in range(4)] for _ in range(4)]

count = 0
if N == 3:
    print(61)
    exit()
for i in range(4, N+1):
    num_now = [[[0] * 4 for _ in range(4)] for _ in range(4)]
    for pre3 in range(4):
        for pre2 in range(4):
            for pre1 in range(4):
                for now in range(4):
                    now_S = S[pre2] + S[pre1] + S[now]
                    now_S2 = S[pre3] + S[pre2] + S[pre1]
                    if now_S2 != 'AGC' and now_S2 != 'GAC' and now_S2 != 'ACG' and now_S != 'AGC' and now_S != 'GAC' and now_S != 'ACG' and S[pre3] + S[pre1] + S[now] != 'AGC' and S[pre3] + S[pre2] + S[now] != 'AGC':
                        num_now[now][pre1][pre2] += num[pre1][pre2][pre3]
                        if i == N:
                            count += num[pre1][pre2][pre3]

    num = num_now.copy()


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