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())
INF=10**9+7
"""
lst=[[
]][i-2][i-1][i]0=A,1=G,2=C,3=T
"""
lst1=[]
lst2=[]
for i in range(4):
    lst2.append((i,0,1))
    lst2.append((i,1,0))
    lst1.append((i,0,2))
for i in range(1,4):
    lst2.append((0,i,1))
    lst2.append((0,1,i))
lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
lst[3][3][3]=1
def LST(lst):
    Lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in lst2:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][2]=0
                elif (i,j,k) in lst1:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][1]=0
                else:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
    return Lst
for n in range(N):
    lst=LST(lst)
sum=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            sum+=lst[i][j][k]
print(sum%INF)

Submission status: Accepted

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

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

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

for i in range(4):
  for j in range(4):
    for m in range(4):
      if i==2 and j==0 and m==1:
        dp[0][m][i][j] = 0
      elif i==0 and j==2 and m==1:
        dp[0][m][i][j] = 0
      elif i==1 and j==0 and m==2:
        dp[0][m][i][j] = 0
      elif i==2 and k==0 and m==1:
        dp[0][m][i][j] = 0
      elif j==2 and k==0 and m==1:
        dp[0][m][i][j] = 0

# A=0, C=1, G=2, T=3
for l in range(1, n+1):
  for m in range(4):
    for i in range(4):
      for j in range(4):
        for k in range(4):
          if i==2 and j==0 and m==1:
            dp[l][m][i][j] = 0
          elif i==0 and j==2 and m==1:
            dp[l][m][i][j] = 0
          elif i==1 and j==0 and m==2:
            dp[l][m][i][j] = 0
          elif i==2 and k==0 and m==1:
            dp[l][m][i][j] = 0
          elif j==2 and k==0 and m==1:
            dp[l][m][i][j] = 0
          else:
            dp[l][m][i][j] += dp[l-1][i][j][k]%mod

print(dp[n][3][3][3]%mod)

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

DIV = (10**9) +7

def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]


N = int_raw()

dp = [0]*(N+1)
dp_a = [0]*(N+1)
dp_g = [0]*(N+1)

dp[0] = 1
dp[1] = 4
dp[2] = 16
dp[3] = 61

#dp_ng[3]=3

dp_a[1]=1
dp_a[2]=4
dp_a[3]=16

dp_g[1]=1
dp_g[2]=4
dp_g[3]=15

#dp_t[1]=1
#dp_t[2]=4
#dp_t[3]=16


for i in xrange(4,N+1):
    dp_a[i] = dp[i-1] %DIV
    dp_g[i] = (dp[i-1] - dp[i-3] + dp_g[i-3]) %DIV
    dp [i] = (dp[i-1] + dp_a[i] + dp_g[i] + dp[i-1] - dp_a[i-3]*3 -dp_a[i-2]  - dp_g[i-2]  )%DIV

print dp[N]

Submission status: Accepted

Solution code:
N = int(input())

DP = [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] for i in range(101)]

DP[2] = [4,3,4,4,4,4,3,4,4,3,4,4,4,4,4,4]

for i in range(3,101):
    DP[i][0] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][1] = DP[i-1][0] + DP[i-1][4] + DP[i-1][12]
    DP[i][2] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][3] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][4] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][5] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][6] = DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][7] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][8] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][9] = DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14] - DP[i - 2][3] - DP[i - 2][2]
    DP[i][10] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][11] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][12] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]
    DP[i][13] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15] - DP[i-2][2]
    DP[i][14] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]
    DP[i][15] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]

print(sum(DP[N-1]) % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())
dp = [dict() for i in range(2)]

big = 10 ** 9 + 7

for a in ['A', 'C', 'G', 'T']:
    for b in ['A', 'C', 'G', 'T']:
        for c in ['A', 'C', 'G', 'T']:
            seq = a + b + c
            if seq != 'AGC' and seq != 'GAC' and seq != 'ACG':
                dp[0][seq] = 1
            else:
                dp[0][seq] = 0

def sum_of_dict(d):
    ans = 0
    for a in ['A', 'C', 'G', 'T']:
        for b in ['A', 'C', 'G', 'T']:
            for c in ['A', 'C', 'G', 'T']:
                seq = a+b+c
                ans += d[seq]
    return ans

def sum_of_dict_with(d, latter):
    ans = 0
    for a in ['A', 'C', 'G', 'T']:
        seq = a+latter
        ans += d[seq]
    return ans

for i in range(3, N):
    n = i % 2
    for a in ['A', 'C', 'G', 'T']:
        for b in ['A', 'C', 'G', 'T']:
            for c in ['A', 'C', 'G', 'T']:
                seq = a + b + c
                if seq == 'AGC' or seq == 'GAC' or seq == 'ACG':
                    dp[n][seq] = 0
                elif seq == 'TGC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['ATG']) % big
                elif seq == 'GGC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['AGG']) % big
                elif seq == 'GTC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['AGT']) % big
                else:
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1) % 2], seq[:2])) % big

print(sum_of_dict(dp[(N-1)%2]) % big)

Submission status: Accepted

Solution code:
AAA = [1] * 101
AAC = [1] * 101
AAG = [1] * 101
AAT = [1] * 101
ACA = [1] * 101
ACC = [1] * 101
ACG = [0] * 101
ACT = [1] * 101
AGA = [1] * 101
AGC = [0] * 101
AGG = [1] * 101
AGT = [1] * 101
ATA = [1] * 101
ATC = [1] * 101
ATG = [1] * 101
ATT = [1] * 101
CAA = [1] * 101
CAC = [1] * 101
CAG = [1] * 101
CAT = [1] * 101
CCA = [1] * 101
CCC = [1] * 101
CCG = [1] * 101
CCT = [1] * 101
CGA = [1] * 101
CGC = [1] * 101
CGG = [1] * 101
CGT = [1] * 101
CTA = [1] * 101
CTC = [1] * 101
CTG = [1] * 101
CTT = [1] * 101
GAA = [1] * 101
GAC = [0] * 101
GAG = [1] * 101
GAT = [1] * 101
GCA = [1] * 101
GCC = [1] * 101
GCG = [1] * 101
GCT = [1] * 101
GGA = [1] * 101
GGC = [1] * 101
GGG = [1] * 101
GGT = [1] * 101
GTA = [1] * 101
GTC = [1] * 101
GTG = [1] * 101
GTT = [1] * 101
TAA = [1] * 101
TAC = [1] * 101
TAG = [1] * 101
TAT = [1] * 101
TCA = [1] * 101
TCC = [1] * 101
TCG = [1] * 101
TCT = [1] * 101
TGA = [1] * 101
TGC = [1] * 101
TGG = [1] * 101
TGT = [1] * 101
TTA = [1] * 101
TTC = [1] * 101
TTG = [1] * 101
TTT = [1] * 101


# AAA[4] は4文字で末尾がAAAの数
for i in range(4, 101):

	AAA[i] = AAA[i-1] + CAA[i-1] + GAA[i-1] + TAA[i-1]
	AAC[i] = AAA[i]
	AAG[i] = AAA[i]
	AAT[i] = AAA[i]
	ACA[i] = AAC[i-1] + CAC[i-1]  + TAC[i-1]
	ACC[i] = ACA[i]
	ACG[i] = 0
	ACT[i] = ACA[i]
	AGA[i] = AAG[i-1] + CAG[i-1] + GAG[i-1] + TAG[i-1]
	AGC[i] = 0
	AGG[i] = AGA[i]
	AGT[i] = AGA[i]
	ATA[i] = AAT[i-1] + CAT[i-1] + GAT[i-1] + TAT[i-1]
	ATC[i] = ATA[i]
	ATG[i] = ATA[i]
	ATT[i] = ATA[i]

	CAA[i] = ACA[i-1] + CCA[i-1] + GCA[i-1] + TCA[i-1]
	CAC[i] = CAA[i]
	CAG[i] = CAA[i]
	CAT[i] = CAA[i]
	CCA[i] = ACC[i-1] + CCC[i-1] + GCC[i-1] + TCC[i-1]
	CCC[i] = CCA[i]
	CCG[i] = CCA[i]
	CCT[i] = CCA[i]
	CGA[i] = 0 + CCG[i-1] + GCG[i-1] + TCG[i-1]
	CGC[i] = CGA[i]
	CGG[i] = CGA[i]
	CGT[i] = CGA[i]
	CTA[i] = ACT[i-1] + CCT[i-1] + GCT[i-1] + TCT[i-1]
	CTC[i] = CTA[i]
	CTG[i] = CTA[i]
	CTT[i] = CTA[i]

	GAA[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GAC[i] = 0 # AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GAG[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GAT[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GCA[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCC[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCG[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCT[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GGA[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGC[i] = 0        + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGG[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGT[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GTA[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTC[i] = 0        + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTG[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTT[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]

	TAA[i] = ATA[i-1] + CTA[i-1] + GTA[i-1] + TTA[i-1]
	TAC[i] = TAA[i]
	TAG[i] = TAA[i]
	TAT[i] = TAA[i]
	TCA[i] = ATC[i-1] + CTC[i-1] + GTC[i-1] +  TTC[i-1]
	TCC[i] = TCA[i]
	TCG[i] = TCA[i]
	TCT[i] = TCA[i]
	TGA[i] = ATG[i-1] + CTG[i-1] + GTG[i-1] + TTG[i-1]
	TGC[i] = 0        + CTG[i-1] + GTG[i-1] + TTG[i-1]
	TGG[i] = TGA[i]
	TGT[i] = TGA[i]
	TTA[i] = ATT[i-1] + CTT[i-1] + GTT[i-1] + TTT[i-1]
	TTC[i] = TTA[i]
	TTG[i] = TTA[i]
	TTT[i] = TTA[i]


n = int(input())
temp = 0 \
 + AAA[n] \
 + AAC[n] \
 + AAG[n] \
 + AAT[n] \
 + ACA[n] \
 + ACC[n] \
 + ACG[n] \
 + ACT[n] \
 + AGA[n] \
 + AGC[n] \
 + AGG[n] \
 + AGT[n] \
 + ATA[n] \
 + ATC[n] \
 + ATG[n] \
 + ATT[n] \
 + CAA[n] \
 + CAC[n] \
 + CAG[n] \
 + CAT[n] \
 + CCA[n] \
 + CCC[n] \
 + CCG[n] \
 + CCT[n] \
 + CGA[n] \
 + CGC[n] \
 + CGG[n] \
 + CGT[n] \
 + CTA[n] \
 + CTC[n] \
 + CTG[n] \
 + CTT[n] \
 + GAA[n] \
 + GAC[n] \
 + GAG[n] \
 + GAT[n] \
 + GCA[n] \
 + GCC[n] \
 + GCG[n] \
 + GCT[n] \
 + GGA[n] \
 + GGC[n] \
 + GGG[n] \
 + GGT[n] \
 + GTA[n] \
 + GTC[n] \
 + GTG[n] \
 + GTT[n] \
 + TAA[n] \
 + TAC[n] \
 + TAG[n] \
 + TAT[n] \
 + TCA[n] \
 + TCC[n] \
 + TCG[n] \
 + TCT[n] \
 + TGA[n] \
 + TGC[n] \
 + TGG[n] \
 + TGT[n] \
 + TTA[n] \
 + TTC[n] \
 + TTG[n] \
 + TTT[n]

print(temp % (1000000007))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
d = {}
cnt = 0
for i in 'ATGC':
  for j in 'ATGC':
    for k in 'ATGC':
      s = i+j+k
      d[s] = cnt
      cnt += 1
dp = [[0 for j in range(n-2)] for i in range(64)]
for i in 'ATGC':
  for j in 'ATGC':
    for k in 'ATGC':
      s = i+j+k
      if s!='AGC' and s!='ACG' and s!='GAC':
        dp[d[s]][0] = 1
for i in range(n-3):
  for x in 'ATGC':
    for y in 'ATGC':
      for z in 'ATGC':
        for w in 'ATGC':
          s = y+z+w
          if s!='AGC' and s!='ACG' and s!='GAC' and x+s!='AGAC' and x+s!='AGTC' and x+s!='AGGC' and x+s!='ATGC':
            dp[d[y+z+w]][i+1] += dp[d[x+y+z]][i]
            dp[d[y+z+w]][i+1] %= mod
ans = 0
for i in range(64):
  ans += dp[i][n-3]
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n = input()
    if n == "A":
        print("T")
    elif n == "C":
        print("G")
    elif n == "G":
        print("C")
    else:
        print("A")
    return

#B
def B():
    s = S()
    ans = 0
    n = len(s)
    for i in range(n):
        for j in range(i,n):
            f = 1
            for k in range(i,j+1):
                if s[k] not in list("AGCT"):f = 0
            if f:
                ans = max(ans,j+1-i)
    print(ans)
#C
def C():
    n,q = LI()
    s = S()
    f = [0 for i in range(n)]
    for i in range(n-1):
        if s[i:i+2] == ["A","C"]:
            f[i+1] += 1
    for i in range(n-1):
        f[i+1] += f[i]
    f.insert(0,0)
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l])
    return

#D
def D():
    n = I()
    dp = [[0]*64 for i in range(n+1)]
    dp[3] = [1]*64
    dp[3][6] = 0
    dp[3][9] = 0
    dp[3][18] = 0
    ng = [[0,1,2],[0,2,1],[1,0,2]]
    for i in range(3,n):
        for j in range(64):
            k = [0,0,0]
            m = j
            for o in range(3):
                k[2-o] = m%4
                m //= 4
            if k not in ng:
                for d in range(4):
                    l = k[1:]+[d]
                    m = k[:2]+[d]
                    o = [k[2]]+[k[1]]+[d]
                    o2 = [k[1]]+[d]+[k[2]]
                    o3 = [k[0]]+[k[2]]+[d]
                    if l not in ng and m != [0,1,2] and o != [0,1,2] and o2 != [0,1,2] and o3 != [0,1,2]:
                        q = 0
                        for o in range(3):
                            q += (4**o)*l[2-o]
                        dp[i+1][q] += dp[i][j]
                        dp[i+1][q] %= mod
    print(sum(dp[n])%mod)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
dp = [[[[0] * 4 for k in range(4)] for j in range(4)] for i in range(N + 4)]

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

for i in range(1, N + 1):
    for j in range(4):
        for k in range(4):
            for q in range(4):
                for p in range(4):
                    if i >= 3 and (k, q, p) in [(0, 1, 2), (1, 0, 2), (0, 2, 1)]:
                        continue
                    if i >= 4 and (j, q, p) == (0, 1, 2):
                        continue
                    if i >= 4 and (j, k, p) == (0, 1, 2):
                        continue
                    else:
                        dp[i][k][q][p] += dp[i - 1][j][k][q]
                        dp[i][k][q][p] %= MOD

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

Submission status: Accepted

Solution code:
N = int(input())
D = {}
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            D[c1+c2+c3] = [0] * 101
            D[c1+c2+c3][3] = 1
D["AGC"][3]=0
D["ACG"][3]=0
D["GAC"][3]=0

for i in range(4,101):
    for k in D:
        for c in "ACGT":
            D[k[1:]+c][i] += D[k][i-1]
            D[k[1:]+c][i] %= 10**9+7
    D["AGC"][i] = 0
    D["GAC"][i] = 0
    D["ACG"][i] = 0
    D["GGC"][i] -= D["AGG"][i-1]
    D["GGC"][i] %= 10**9+7
    D["GTC"][i] -= D["AGT"][i-1]
    D["GTC"][i] %= 10**9+7
    D["TGC"][i] -= D["ATG"][i-1]
    D["TGC"][i] %= 10**9+7

ans = 0
for k in D:
    ans += D[k][N]
    ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7

N = int(input())
DP = defaultdict(int)
for a, b, c in product(range(4), repeat=3):
    DP[(a, b, c)] = 1

DP[(0, 2, 1)] = 0
DP[(0, 1, 2)] = 0
DP[(2, 0, 1)] = 0

for i in range(N-3):
    DP2 = defaultdict(int)
    for a, b, c in product(range(4), repeat=3):
        DP2[(b, c, 0)] = (DP2[(b, c, 0)] + DP[(a, b, c)])%MOD

        if (b, c) != (0, 2) and (a, c) != (0, 2) and (a, b) != (0, 2) and (b, c) != (2, 0):
            DP2[(b, c, 1)] = (DP2[(b, c, 1)] + DP[(a, b, c)])%MOD
        if (b, c) != (0, 1):
            DP2[(b, c, 2)] = (DP2[(b, c, 2)] + DP[(a, b, c)])%MOD

        DP2[(b, c, 3)] = (DP2[(b, c, 3)] + DP[(a, b, c)])%MOD
    DP = DP2
print(sum(DP.values())%MOD)

Submission status: Accepted

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

P = np.empty((4,4,4),dtype=np.int64)
Q = np.ones((4,4,4),dtype=np.int64)
Q[0,2,1] = Q[2,0,1] = Q[0,1,2] = 0
for n in range(3,N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in [(0,2,1), (2,0,1), (0,1,2)]:
                    P[i,j,k] = 0
                elif (j,k) == (2,1) or (i,k) == (2,1):
                    P[i,j,k] = Q[1:,i,j].sum() % M 
                else:
                    P[i,j,k] = Q[:,i,j].sum() % M
    (P, Q) = (Q, P)

print(Q.sum() % M)

Submission status: Accepted

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

dp = [
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ]
]

dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[1][0][2][0] = 0

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[j][k][l][m+1] %= M
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

Submission status: Accepted

Solution code:
N = int(input().strip())
M = pow(10, 9) + 7
a = 1
g = 1
ag = 0
agg = 0
agt = 0
atg = 0
ac = 0
at = 0
aa = 0
ga = 0

al = 4
nal = 0

for i in range(N-1):
    nal = (al * 4) % M
    nal = (nal + M - (ag + ac + ga + agg + agt + atg) ) % M

    agg = ag
    agt = ag
    atg = at
    ag = a
    aa = a
    at = a
    nac = (a + M- ga) % M
    ga = g
    a = al
    g = (al + M - ac) % M
    ac = nac
    al = nal
print(al)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
n = int(input())
if n == 3:
    print('61')
    quit()

divide = 1000000007

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

out = set()
for c in agct:
    out.add('AGC' + c)
    out.add(c+'AGC')
    out.add( 'A' + c + 'GC')
    out.add('AG' + c + 'C')
    out.add('GAC' + c)
    out.add(c+'GAC')
    out.add('ACG' + c)
    out.add(c+'ACG')

##後ろ4文字を与えて，それがokかどうか
def isok(str):
    if str[-4:] in out:
        return False
    return True


#N文字で最後の4文字がstrの時の種類数
@lru_cache(maxsize=1000000)
def saiki(n,str):
    if n == 4:
        if isok(str):
            return 1
        return 0
    ret = 0
    if isok(str)==False:
        return 0
    for c in agct:
        next = c+str
        next = next[0:4]
        ret += saiki(n-1,next)
    return ret%divide

strlist = list(itertools.product(agct, repeat=4))
#print('len is ',len(strlist))
rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)

Submission status: Accepted

Solution code:
N = int(input())

s = ['A', 'C', 'G', 'T']
invs = ['AGC', 'ACG', 'GAC']

d = {}
for c1 in s:
    for c2 in s:
        for c3 in s:
            d[c1+c2+c3] = 1 if c1+c2+c3 not in invs else 0

dn = {}
for _ in range(N - 3):
    for c1 in s:
        for c2 in s:
            for c3 in s:
                cnt = 0
                for c0 in s:
                    if c0+c2+c3!='AGC' and c0+c1+c3!='AGC':
                        cnt += d[c0+c1+c2]
                dn[c1+c2+c3] = cnt%1000000007 if c1+c2+c3 not in invs else 0
    dn, d = d, dn

print(sum(d.values())%1000000007)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
dp[0][0][0][0] = 1
mod = 10**9+7
en = ["A","G","C","T"]
def han(mozi):
        if mozi.find("AGC") != -1:
                return 1
        mozi2 = mozi[1] + mozi[0] + mozi[2:]
        if mozi2.find("AGC") != -1:
                return 1    
        mozi3 = mozi[0] + mozi[2] + mozi[1] + mozi[3]
        if mozi3.find("AGC") != -1:
                return 1    
        mozi4 = mozi[0] + mozi[1] + mozi[3] + mozi[2]
        if mozi4.find("AGC") != -1:
                return 1             
        return 0
for i in range(n):
        for j in range(4):
                for k in range(4):
                        for l in range(4):
                                for o in range(4):
                                        if i== 2:
                                                if o == 0 and j ==1 and k == 2:
                                                        continue
                                                if o == 0 and j ==2 and k == 1:
                                                        continue
                                                if o == 1 and j ==0 and k == 2:
                                                        continue
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                        elif i < 2:
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                        else:
                                                mozi = en[o] + en[j] + en[k]+ en[l]
                                                if han(mozi):
                                                        continue
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                                dp[i+1][o][j][k] %= mod
print(np.sum(np.array(dp[n]))%mod)

Submission status: Accepted

Solution code:
n = int(input())

mod = 10**9 + 7

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

for w in range(4**3):
    if (w // 16) % 4 == 0 and (w // 4) % 4 == 2 and w % 4 == 3:
        continue
    if (w // 16) % 4 == 0 and (w // 4) % 4 == 3 and w % 4 == 2:
        continue
    if (w // 16) % 4 == 2 and (w // 4) % 4 == 0 and w % 4 == 3:
        continue
    dp[3][w] = 1

for i in range(3, n):
    for w in range(4**3):
        for nw in range(4):
            if (w // 4) % 4 == 0 and w % 4 == 2 and nw == 3:
                continue
            if (w // 4) % 4 == 0 and w % 4 == 3 and nw == 2:
                continue
            if (w // 4) % 4 == 2 and w % 4 == 0 and nw == 3:
                continue
            if (w // 16) % 4 == 0 and (w // 4) % 4 == 2 and nw == 3:
                continue
            if (w // 16) % 4 == 0 and w % 4 == 2 and nw % 4 == 3:
                continue
            dp[i+1][(((w // 4) % 4) * 16 + (w % 4) * 4) + nw] += dp[i][w]
            dp[i+1][(((w // 4) % 4) * 16 + (w % 4) * 4) + nw] %= mod

ans = 0
for w in range(4**3):
    ans += dp[n][w]
    ans %= mod

print(ans)

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
                if not any(map(lambda x: x in s, iv)):
                    dp_[s[1:]] = m.add(v, dp_[s[1:]])
        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:
from itertools import product

MOD = 10**9 + 7
N = int(input())
assert 3 <= N <= 100

char_to_idx = {"A": 0, "C": 1, "G": 2, "T": 3}
# chars = ("A", "C", "G", "T")

# dp[i][i1][i2][i3] = #valid strings of length i + 1 when s[i-3:] = c1c2c3
dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N)]

# init
invalid_seqs = set(["AGC", "ACG", "GAC"])
for chars in product(char_to_idx.keys(), repeat=3):
    string = "".join(chars)
    if string not in invalid_seqs:
        i1, i2, i3 = [char_to_idx[char] for char in string]
        dp[2][i1][i2][i3] = 1

invalied_indices = set()
for chars in product(char_to_idx.keys(), repeat=4):
    string = "".join(chars)
    if string[:3] == "AGC" or string[1:] == "AGC":
        invalied_indices.add(tuple(char_to_idx[char] for char in string))
        continue
    for i in range(3):
        new_string = list(string)
        new_string[i], new_string[i + 1] = string[i + 1], string[i]
        new_string = "".join(new_string)
        if new_string[:3] == "AGC" or new_string[1:] == "AGC":
            invalied_indices.add(tuple(char_to_idx[char] for char in string))
            break
# print(len(invalied_indices))

for i in range(3, N):
    for i0 in range(4):
        for i1 in range(4):
            for i2 in range(4):
                for i3 in range(4):
                    if (i0, i1, i2, i3) not in invalied_indices:
                        dp[i][i1][i2][i3] += dp[i - 1][i0][i1][i2]
                        dp[i][i1][i2][i3] %= MOD

num_strings = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            num_strings += dp[-1][i][j][k]
            num_strings %= MOD
print(num_strings)