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:
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 main():
    N = II()
    A, G, C, T = range(4)
    def code(c0, c1, c2):
        return c0 + 4 * c1 + 16 * c2
    dp = [0] * 64
    dp[code(T, T, T)] = 1
    for _ in range(N):
        tmp = [0] * 64
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                tmp[code(cur, p1, p2)] += dp[code(p1, p2, p3)]
                tmp[code(cur, p1, p2)] %= MOD
        dp = tmp
    ans = sum(dp)

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
dp = [[[[0 for k in range(4)] for k in range(4)] for j in range(4)] for i in range(101)]
' 長さ0の文字列は1である。        '
' 0,1,2に関する制約しかないので、 '
' Sは、333Sと考えても問題がない。 '
dp[0][3][3][3] = 1

for length in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if dp[length][c1][c2][c3] == 0: continue
        for c4 in range(4):
          ' ダメな5つの条件をカットする'
          if   True  and c2 == 0 and c3 == 1 and c4 == 2: continue
          if   True  and c2 == 1 and c3 == 0 and c4 == 2: continue
          if   True  and c2 == 0 and c3 == 2 and c4 == 1: continue
          if c1 == 0 and c2 == 1 and   True  and c4 == 2: continue
          if c1 == 0 and   True  and c3 == 1 and c4 == 2: continue

          ' ダメな条件を抜けたら、c4を足した文字列が作れる '
          ' S     = ...... c1 c2 c3                        '
          ' nextS = ...... c2 c3 c4                        '
          dp[length + 1][c2][c3][c4] += dp[length][c1][c2][c3]
          dp[length + 1][c2][c3][c4] %= MOD

ans = 0
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      ans += dp[N][c1][c2][c3]
      ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m=102
chars=['A','T','C','G']
mo=10**9+7
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)

dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1

t=1+n
for i in range(4,t):
    for ch in chars:
        for p in dp[i-1].keys():
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

if n==3:
    ans=61
    print(ans)
else:
    print(cnt[n])

Submission status: Accepted

Solution code:
#x=int(input())
n=int(input())
m=102
chars=['A','T','C','G']
mo=10**9+7
d3=set()
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            d3.add(i+j+k)
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)


dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1
    

t=101
for i in range(4,t):
    for ch in chars:
        for p in dp[i-1].keys():
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

#print(len(kinsoku4),kinsoku4)
#print(dp)

#for x in cnt:
    #print(x%mo)

if n==3:
    ans=61
    print(ans)
else:
    print(cnt[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
MOD = 10**9 + 7
N = int(input())

A, G, C, T = range(4)
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
      for _ in range(N + 1)]
dp[0][T][T][T] = 1
for k in range(N):
    for c0, c1, c2, c3 in product(range(4), repeat=4):
        if c1 == A and c2 == G and c3 == C: continue
        if c1 == G and c2 == A and c3 == C: continue
        if c1 == A and c2 == C and c3 == G: continue
        if c0 == A and c2 == G and c3 == C: continue
        if c0 == A and c1 == G and c3 == C: continue
        dp[k + 1][c1][c2][c3] += dp[k][c0][c1][c2]
        dp[k + 1][c1][c2][c3] %= MOD

ans = 0
for c0, c1, c2 in product(range(4), repeat=3):
    ans += dp[N][c0][c1][c2]
    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
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        dp = dp_
    
    return reduce(m.add, dp.values())


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

t = [0] * (n + 1)
a = [0] * (n + 1)
g = [0] * (n + 1)
ac = [0] * (n + 1)

t[0] = 1
t[1] = 4
t[2] = 16
a[1] = 1
a[2] = 4
g[1] = 1
g[2] = 4
ac[2] = 1

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

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

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_
    
    return reduce(lambda x, y: m.add(x, y), dp.values())


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = ["A","C","G","T"]
lis = ["AGC","ACG","GAC"]

d = {}
for i in s:
    for j in s:
        for k in s:
            if i + j + k in lis:
                d[i + j + k] = 0
            else:
                d[i + j + k] = 1

dd = {}
for _ in range(n-3):
    for i in s:
        for j in s:
            for k in s:
                num = 0
                for nu in s:
                    if nu + j + k != "AGC" and nu + i + k != "AGC":
                        num += d[nu + i + j]
                    if i + j + k in lis:
                        dd[i + j + k] = 0
                    else:
                        dd[i + j + k] = num % (10 ** 9 + 7)
    dd,d = d,dd

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [[[[0 for l in range(4)] for k in range(4)]
       for j in range(4)] for i in range(N)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not (j == 0 and k == 1 and l == 2)\
                    and not(j == 0 and k == 2 and l == 1)\
                    and not (j == 2 and k == 0 and l == 1):
                dp[2][j][k][l] = 1
for i in range(2, N-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] %= 10**9+7
                dp[i+1][k][l][0] += dp[i][j][k][l]
                # 0123: ACGT
                # AG?
                # ?GA
                # A?G
                # ?AG
                if not (j == 0 and k == 2) \
                   and not (k == 2 and l == 0)\
                   and not (j == 0 and l == 2)\
                   and not (k == 0 and l == 2):
                    dp[i+1][k][l][1] += dp[i][j][k][l]
                # ?AC
                if not (k == 0 and l == 1):
                    dp[i+1][k][l][2] += dp[i][j][k][l]
                dp[i+1][k][l][3] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N-1][j][k][l]
ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
if N==3:
  print(61)
  exit()
dp=[[0]*64 for i in range(N+1)]
dp[3]=[1]*64
dp[3][11],dp[3][14],dp[3][35]=0,0,0
NG=[]
mask=63
mod=10**9+7
for i in range(4):
  NG.append(64*i+16*0+4*2+3)
  NG.append(64*0+16*2+4*i+3)
  NG.append(64*0+16*i+4*2+3)
  NG.append(64*i+16*0+4*3+2)
  NG.append(64*i+16*2+4*0+3)
for i in range(3,N):
  for k in range(64):
    for s in range(4):
      flag=True
      for ng in NG:
        if ng==((k<<2)+s):
          flag=False
          break
      if flag:
        dp[i+1][((k<<2)+s)&mask]+=dp[i][k]
        dp[i+1][((k<<2)+s)&mask]%=mod
ans=0
for k in range(64):
  ans+=dp[N][k]
  ans%=mod
print(ans)

Submission status: Accepted

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

for length in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if dp[length][i][j][k] == 0: continue
        for a in range(4):
          if a == 2 and i == 1 and j == 0: continue
          if a == 2 and i == 0 and j == 1: continue
          if a == 1 and i == 2 and j == 0: continue
          if a == 2 and i == 1 and k == 0: continue
          if a == 2 and j == 1 and k == 0: continue

          dp[length + 1][a][i][j] += dp[length][i][j][k]
          dp[length + 1][a][i][j] %= MOD

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

print(ans)

Submission status: Accepted

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

DP=[1]+[0]*13

for i in range(N):
    NDP=[0]*14

    NDP[0]=DP[0]*2+DP[1]*2+DP[5]*2+DP[7]*2+DP[9]+DP[10]+DP[11]*2+DP[13]
    NDP[1]=DP[0]+DP[13]
    NDP[2]=DP[1]+DP[9]+DP[10]+DP[11]
    NDP[3]=DP[0]+DP[5]+DP[7]+DP[13]
    NDP[4]=DP[2]+DP[3]+DP[12]
    NDP[5]=DP[3]+DP[6]
    NDP[6]=DP[2]+DP[3]+DP[6]+DP[12]
    NDP[7]=DP[2]+DP[3]+DP[6]+DP[12]
    NDP[8]=DP[6]
    NDP[9]=DP[7]
    NDP[10]=DP[4]+DP[8]
    NDP[11]=DP[1]+DP[9]+DP[10]+DP[11]
    NDP[12]=DP[4]+DP[8]
    NDP[13]=DP[4]+DP[8]

    for i in range(14):
        NDP[i]=NDP[i]%mod


    DP=NDP
    #print(DP)

print(sum(DP)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# いっこ入力
n =int(input())
p = 10**9+7 

a=[[[[0]*4]*4]*4]*101
a=[[[[0 for i in range(4)] for j in range(4)] for j in range(4)] for j in range(101)]
a[3][0][0][0]= 1
a[3][0][0][1]= 1
a[3][0][0][2]= 1
a[3][0][0][3]= 1
a[3][0][1][0]= 1
a[3][0][1][1]= 1
a[3][0][1][2]= 0
a[3][0][1][3]= 1
a[3][0][2][0]= 1
a[3][0][2][1]= 0
a[3][0][2][2]= 1
a[3][0][2][3]= 1
a[3][0][3][0]= 1
a[3][0][3][1]= 1
a[3][0][3][2]= 1
a[3][0][3][3]= 1
 
a[3][1][0][0]= 1
a[3][1][0][1]= 1
a[3][1][0][2]= 1
a[3][1][0][3]= 1
a[3][1][1][0]= 1
a[3][1][1][1]= 1
a[3][1][1][2]= 1
a[3][1][1][3]= 1
a[3][1][2][0]= 1
a[3][1][2][1]= 1
a[3][1][2][2]= 1
a[3][1][2][3]= 1
a[3][1][3][0]= 1
a[3][1][3][1]= 1
a[3][1][3][2]= 1
a[3][1][3][3]= 1
 
a[3][2][0][0]= 1
a[3][2][0][1]= 0
a[3][2][0][2]= 1
a[3][2][0][3]= 1
a[3][2][1][0]= 1
a[3][2][1][1]= 1
a[3][2][1][2]= 1
a[3][2][1][3]= 1
a[3][2][2][0]= 1
a[3][2][2][1]= 1
a[3][2][2][2]= 1
a[3][2][2][3]= 1
a[3][2][3][0]= 1
a[3][2][3][1]= 1
a[3][2][3][2]= 1
a[3][2][3][3]= 1
 
a[3][3][0][0]= 1
a[3][3][0][1]= 1
a[3][3][0][2]= 1
a[3][3][0][3]= 1
a[3][3][1][0]= 1
a[3][3][1][1]= 1
a[3][3][1][2]= 1
a[3][3][1][3]= 1
a[3][3][2][0]= 1
a[3][3][2][1]= 1
a[3][3][2][2]= 1
a[3][3][2][3]= 1
a[3][3][3][0]= 1
a[3][3][3][1]= 1
a[3][3][3][2]= 1
a[3][3][3][3]= 1
 

for i in range(4,n+1):
    for s in range(4):
        for t in range(4):
            for u in range(4):
                if (s==0 and t==2 and u==1) or (s==2 and t==0 and u ==1) or (s==0 and t==1 and u ==2):
                    a[i][s][t][u]=0
                elif (s==2 and t==3 and u==1) or (s==2 and t==2 and u ==1) or (s==3 and t==2 and u ==1):
                    a[i][s][t][u] = a[i-1][1][s][t] + a[i-1][2][s][t] + a[i-1][3][s][t]
                else:
                    a[i][s][t][u] = a[i-1][0][s][t] + a[i-1][1][s][t] + a[i-1][2][s][t] + a[i-1][3][s][t]
#                print(a[i][s][t][u])

answer =0
for s in range(4):
    for t in range(4):
        for u in range(4):
            answer += a[n][s][t][u]

print(answer % p)
# print(a)

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
import numpy as np

def main():
    N = II()
    A, G, C, T = 0, 1, 2, 3
    dp = np.zeros((N + 1, 4, 4, 4), int)
    dp[0, T, T, T] = 1
    for n in range(N):
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[n + 1, cur, p1, p2] = \
                    (dp[n + 1, cur, p1, p2] + dp[n, p1, p2, p3]) % MOD
    ans = np.sum(dp[N])

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 20:51:04 2019

@author: Yamazaki Kenichi
"""

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

res = [[0 for j in range(14)] for i in range(N+1)]
res[1][0],res[1][1],res[1][2],res[1][3] = 1,1,1,1


for i in range(2,N+1):
    res[i][0] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][2]-res[i-1][4]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][1] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][10]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][2] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][7]-res[i-1][12]-res[i-1][5]
    res[i][3] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][12]
    res[i][4] = res[i-1][0]            +res[i-1][8]+res[i-1][9]
    res[i][5] = res[i-1][0]+res[i-1][6]
    res[i][6] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][7] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][8] = res[i-1][2]+res[i-1][11]+res[i-1][13]
    res[i][9] = res[i-1][4]+res[i-1][12]
    res[i][10] = res[i-1][4]+res[i-1][12]
    res[i][11] = res[i-1][4]+res[i-1][12]
    res[i][12] = res[i-1][6]
    res[i][13] = res[i-1][7]

print(sum(res[-1])%mod)

Submission status: Accepted

Solution code:
N = input()

T = [[[0]*4 for i in range(4)] for j in range(4)]
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      if (0, 1, 2) not in [
        (c1, c2, c3),
        (c2, c1, c3),
        (c1, c3, c2),
      ]:
        T[c1][c2][c3] = 1

for i in range(3, N):
  P = T
  T = [[[0]*4 for i in range(4)] for j in range(4)]
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for c4 in range(4):
          if (0, 1, 2) not in [
            (c2, c3, c4),
            (c3, c2, c4),
            (c2, c4, c3),
            (c1, c3, c4),
            (c1, c2, c4),
          ]:
            T[c2][c3][c4] += P[c1][c2][c3]
            T[c2][c3][c4] %= 1000000007
print sum(sum(sum(t2) for t2 in t1) for t1 in T) % 1000000007

Submission status: Accepted

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

for len in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if DP[len][i][j][k] == 0: continue
        for a in range(4):
          if (a, i, j) == (2, 1, 0): continue
          if (a, i, j) == (2, 0, 1): continue
          if (a, i, j) == (1, 2, 0): continue
          if (a, i, k) == (2, 1, 0): continue
          if (a, j, k) == (2, 1, 0): continue

          DP[len + 1][a][i][j] += DP[len][i][j][k]
          DP[len + 1][a][i][j] % MOD

Ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      Ans += DP[N][i][j][k]
      Ans %= MOD
                         
print(Ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import chain, product
from functools import reduce
from collections import OrderedDict, Counter, deque
import operator

IS = lambda: int(input())

N = IS()
p = 10**9+7

A, C, G, T = range(4)
prev = [1] * (4**2)
banned = set([
    (A << 4) + (G << 2) + C,
    (G << 4) + (A << 2) + C,
    (A << 4) + (C << 2) + G,
    ])

cur = [0] * (4**3)
for i in range(4):
    i4 = i << 2
    i8 = i << 4
    for j in range(4):
        j4 = j << 2
        for k in range(4):
            if (i8 + j4 + k) in banned: continue
            cur[i8 + j4 + k] += prev[i4 + j]
prev = [x % p for x in cur]

banned |= set(map(sum, product([x<<6 for x in range(4)], banned)))
banned |= set(map(sum, product([x<<4 for x in range(4)], [
    (A << 6) + (G << 2) + C,
    ])))
banned |= set(map(sum, product([x<<2 for x in range(4)], [
    (A << 6) + (G << 4) + C,
    ])))

for _ in range(3,N):
    cur = [0] * (4**3)
    for i in range(4):
        i4 = i << 2
        i8 = i << 4
        i16 = i << 6
        for j in range(4):
            j4 = j << 2
            j8 = j << 4
            for k in range(4):
                k4 = k << 2
                for l in range(4):
                    if (i16 + j8 + k4 + l) in banned: continue
                    cur[j8 + k4 + l] += prev[i8 + j4 + k]
    prev = [x % p for x in cur]

print(sum(prev) % p)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = not True
R = 1000000007
def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = c = g = t = 1
ac = ag = at = 0
ga  = 0
agg = agt = atg = 0

for i in range(n-1):
    xatg = at
    xagg = ag
    xagt = ag
    xat = a
    xag = a
    xac = a - ga
    xga = g
    xa = a + c + g + t
    xc = a + c + g + t - ga - ag - atg - agg - agt
    xg = a + c + g + t - ac
    xt = a + c + g + t
    a = xa % R
    c = xc % R
    g = xg % R
    t = xt % R
    ac = xac % R
    ag = xag % R
    at = xat % R
    ga = xga % R
    agg = xagg % R
    agt = xagt % R
    atg = xatg % R
    ddprint("i {}: a {} c {} g {} t {} ".format(i,xa,xc,xg,xt))
    ddprint("     ac {} ag {} at {} ga {} ".format(xac,xag,xat,xga))
    ddprint("     agg {} agt {} atg {} ".format(xagg,xagt,xatg))

print((a+c+g+t)%R)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
import itertools as itr

S = []

dp = [] #末尾3つのパターンで記憶

def init():
  dct = {}
  for i in ['A','C','G','T']:
    for j in ['A','C','G','T']:
      for k in ['A','C','G','T']:
        s = i+j+k
        if s not in ['AGC','ACG','GAC']:
          dct[s] = 1
  return dct


def chk(s):
  if ('AGC' in s) or ('ACG' in s) or ('GAC' in s):
    return False
  elif ('AGAC' in s) or ('AGCC' in s) or ('AGGC' in s) or ('AGTC' in s):
    return False
  elif ('AAGC' in s) or ('ACGC' in s) or ('AGGC' in s) or ('ATGC' in s):
    return False
  else:
    return True


n = int(input())-3

dp = init()
for i in range(n):
  dct = {}
  for s in dp:
    for c in ['A','C','G','T']:
      if chk(s+c):
        if s[1:]+c not in dct:
          dct[s[1:]+c] = dp[s] % (10**9+7)
        else:
          dct[s[1:]+c] += dp[s] % (10**9+7)
  dp = dct

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

Submission status: Accepted

Solution code:
import itertools as it

N=int(input())
dp=dict()
def ok(s):
    return all(['AGC' not in t for t in 
        [s, s[0:2]+s[3]+s[2], s[0]+s[2]+s[1]+s[3], s[1]+s[0]+s[2:4]]]) 

def n(j, s):
    if j == 3:
        return 1 if s not in ["AGC", "ACG", "GAC"] else 0
    if (j, s) in dp:
        return dp[(j, s)]
    ret = sum([
        n(j-1, "A"+s[:3]) if ok("A"+s[:3]) else 0,
        n(j-1, "C"+s[:3]) if ok("C"+s[:3]) else 0,
        n(j-1, "G"+s[:3]) if ok("G"+s[:3]) else 0,
        n(j-1, "T"+s[:3]) if ok("T"+s[:3]) else 0]
    )
    dp[(j, s)]=ret
    return ret

m=sum([n(N, "".join(s)) for s in it.product("ACGT", repeat=3)])
print(m%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
memo = [{} for _ in range(100)]

def ok(last4):
    if "AGC" in last4:
        return False
    for i in range(3):
        t = list(last4)
        t[i], t[i+1] = t[i+1], t[i]
        if "AGC" in "".join(t):
            return False
    return True
def dfs(cur, last3):
    if cur == N:
        return 1
    if last3 in memo[cur]:
        return memo[cur][last3]
    ret = 0
    for c in "ACGT":
        if ok(last3+c):
            ret += dfs(cur + 1, last3[1:] + c) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret % (10**9 + 7)
print(dfs(0, "TTT"))

Submission status: Accepted

Solution code:
import sys

def check(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, N, memo=[]):
    if last3 in memo[cur]:
        return memo[cur][last3]

    if cur == N:
        return 1

    ret = 0
    for c in 'AGCT':
        if check(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:]+c, N, memo)) % (10**9 + 7)
    memo[cur][last3] = ret
    return ret


def main():
    input = sys.stdin.readline
    N = int(input())

    memo = [{} for _ in range(N+1)]
    print(dfs(0, 'TTT', N, memo))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8-*-
if __name__ == '__main__':
    n = int(input())
    pd = {"   ": 1}
    d = {"   ": 1}
    for i in range(n):
        pd = d
        d = {}
        for k, v in pd.items():
            for j in "AGTC":
                t = k+j
                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 not ("AGC" in t or "AGC" in t1 or "AGC" in t2 or "AGC" in t3):
                    if t[1:] in d:
                        d[t[1:]] += v
                    else:
                        d[t[1:]] = v
                    d[t[1:]] %= 1000000007
    sum = 0
    for v in d.values():
        sum += v
    sum %= 1000000007
    print(sum)

Submission status: Accepted

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

#  ACG
#  AGC
#  GAC
#
# A?GC
#  AG?C
#         A  T  G  C
#            G  G
#            G  T

A=0
C=1
G=2
T=3
dp = [[[[0 for i4 in range(4)] for i3 in range(4)] for i2 in range(4)] for i in range(N+10)]
dp[0][T][T][T] = 1

for i1 in range(1,N+1):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                for i5 in range(4):
                    if i3==A and i4==C and i5==G: continue
                    if i3==A and i4==G and i5==C: continue
                    if i3==G and i4==A and i5==C: continue
                    if i2==A and i4==G and i5==C: continue
                    if i2==A and i3==G and i5==C: continue
                    dp[i1][i3][i4][i5] += dp[i1-1][i2][i3][i4]

ans=0
for i1 in range(4):
    for i2 in range(4):
        ans += sum(dp[N][i1][i2])

print(ans % mod)

Submission status: Accepted

Solution code:
import sys

N=int(input())
if N==3:
    print(61)
    sys.exit()
#dp[n][i][j][k]
dp=[[[[0 for i in range(4)] for i in range(4)] for i in range(4)] for i in range(N+1)]
A=0;G=1;C=2;T=3;
mod=10**9+7
dp[0][3][3][3]=1
def check(i,j,k,l):
    if i==A and k==G and l==C:
        return 0
    if j==A and k==G and l==C:
        return 0
    if j==G and k==A and l==C:
        return 0
    if j==A and k==C and l==G:
        return 0
    if i==A and j==G and l==C:
        return 0
    else:
        return 1

for n in range(1,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if check(i,j,k,l):
                        dp[n][j][k][l]+=dp[n-1][i][j][k]
                        dp[n][j][k][l]%=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)