Problem:


Score : 400 points

Problem Statement

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

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

The string does not contain AGC as a substring.

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

Notes

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

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

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

3

Sample Output 1

61

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

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

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



Sample input:
3


Sample output:
61

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())
#print(3*cmb(n-2,n-3)*4**(n-3))
print((4**n-3*cmb(n-2,n-3)*4**(n-3)- (n-3)*2 )%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())

mod = 10 ** 9 + 7

result = 3
for i in range(3, N):
    result = (4 * result + 2) % mod
print(result)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
N = int(input())
def m():
    if N == 3:
        return 4**N - 3
    if N >= 4:
        s = 4 ** N
        invalid = 3*4*(N-2) - 1*(N-3) + 3*(N-3)
        ans = s - invalid
        return ans % MOD

print(m())

Submission status: Wrong Answer

Solution code:
dp=[0]*101
dp[3]=61
p=10**9 +7
for i in range(4,101):
  dp[i]=(4*dp[i-1]-14*pow(4,i-4,p))%p
n=int(input())
print(dp[n])

Submission status: Wrong Answer

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

import itertools
import collections
import bisect

dp3 = [-1] * 101
dp_atg = [-1] * 101
dp_ag = [-1] * 101
dp_ac = [-1] * 101
dp_ga = [-1] * 101
dp_all = [-1] * 101


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

    # AGC, ACG, GAC は NG
    if lastt[-3:] in ['AGG', 'AGA', 'AGT']:
        if dp3[rest] != -1:
            return dp3[rest]
        dp3[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        return dp3[rest]
    elif lastt[-3:] in ['ATG']:
        if dp_atg[rest] != -1:
            return dp_atg[rest]
        dp_atg[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        return dp_atg[rest]
    elif lastt[-2:] == 'AG':
        return solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        # if dp_ag[rest] != -1:
        #     return dp_ag[rest]
        # dp_ag[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        # return dp_ag[rest]
    elif lastt[-2:] == 'AC':
        return solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'C') + solve(rest - 1, lastt + 'T')
        # if dp_ac[rest] != -1:
        #     return dp_ac[rest]
        # dp_ac[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'C') + solve(rest - 1, lastt + 'T')
        # return dp_ac[rest]
    elif lastt[-2:] == 'GA':
        return solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        # if dp_ga[rest] != -1:
        #     return dp_ga[rest]
        # dp_ga[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'T')
        # return dp_ga[rest]
    else:
        # everything ok
        return solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'C') + solve(rest - 1, lastt + 'T')
        # if dp_all[rest] != -1:
        #     return dp_all[rest]
        # dp_all[rest] = solve(rest - 1, lastt + 'A') + solve(rest - 1, lastt + 'G') + solve(rest - 1, lastt + 'C') + solve(rest - 1, lastt + 'T')
        # return dp_all[rest]

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())

    index = 3

    last_3s = {}

    for i in "AGCT":
        for j in "AGCT":
            for k in "AGCT":
                last_3s[i + j + k] = 1

    last_3s["AGC"] = 0
    last_3s["ACG"] = 0
    last_3s["GAC"] = 0

    while index < n:
        new_last_3s = {}
        for key in last_3s:
            new_last_3s[key] = 0

        for key in last_3s:
            for c in "AGCT":
                new_s = key + c
                new_key = new_s[1:]
                if new_key not in ["AGC", "ACG", "GAC"]:
                    new_last_3s[new_key] += last_3s[key]

        print(new_last_3s)
        last_3s = new_last_3s
        index += 1

    answer = 0
    for key in last_3s:
        answer += last_3s[key]

    print(answer % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
import itertools
import numpy as np

N = int(input())

mod = 1000000007

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

NGs = ['AGC','GAC','ACG','AGGC','ATGC','AGTC']

# for i in range(3,8):
#     print('N=',i)
#     NG_count = [0,0,0,0,0,0]
#     count = 0
#     for mozi in itertools.product(ATGC,repeat=i):
#         a = "".join(mozi)
#         for j in range(6):
#             if NGs[j] in a:
#                 # print(a)
#                 NG_count[j] += 1
#                 break
#     print(NG_count, sum(NG_count), i**4 - sum(NG_count))


count = 0
for mozi in itertools.product(ATGC,repeat=N):
    a = "".join(mozi)
    for j in range(6):
        if NGs[j] in a:
            print(a)
            count += 1
            break

print(N**4 - count)

Submission status: Wrong Answer

Solution code:
def pow_mod(a: int, n: int, mod: int)->int:
    ret = 1
    for _ in range(n):
        ret = (ret * a) % mod
    return ret


def we_like_agc(N: int)->int:
    MOD = 10**9 + 7
    A, G, C, T = [0] * (N+1), [0] * (N+1), [0] * (N+1), [0] * (N+1),
    AG, AC, GA = [0] * (N+1), [0] * (N+1), [0] * (N+1)
    ATG, AGT = [0] * (N+1), [0] * (N+1)

    A[1], G[1], C[1], T[1] = 1, 1, 1, 1

    for i in range(2, N+1):
        A[i] = A[i-1] + G[i-1] + C[i-1] + T[i-1]
        G[i] = A[i-1] + G[i-1] + (C[i-1] - AC[i-1]) + T[i-1]
        C[i] = (A[i-1] - GA[i-1]) + (G[i-1] - AG[i-1] -
                                     ATG[i-1]) + C[i-1] + (T[i-1] - AGT[i-1])
        T[i] = A[i-1] + G[i-1] + C[i-1] + T[i-1]

        AG[i] = A[i-1]
        AC[i] = A[i-1]
        GA[i] = G[i-1]

        ATG[i] = A[i-2]
        AGT[i] = A[i-2]

    # print(A)
    # print(G)
    # print(C)
    # print(T)

    return (A[N] + G[N] + C[N] + T[N]) % MOD


if __name__ == "__main__":
    N = int(input())
    ans = we_like_agc(N)
    print(ans)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
N = int(input())
# ACGTのみで作る
# AGCの並びが出ない
# 2文字入れ替えてもAGCにならない
#3:AGC, GAC, ACG
#4:ATGC, AGTC, AGGC

diff = N - 3
ng3 = 3
if diff > 0:
    ng3 = 3 * (4**diff)*2 - diff

diff = N - 4
ng4 = 0
if diff == 0:
    ng4 = 3
if diff > 0:
    ng4 = 3 * (4**diff)
print((4**N - ng3 - ng4)%(10**9+7))

Submission status: Wrong Answer

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) + nw * 16] += dp[i][w]
            dp[i+1][(w // 4) + nw * 16] %= mod

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

print(ans)

Submission status: Wrong Answer

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[0] = 1
    a[1] = 4
    a[2] = 16
    a[3] = 61

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

    print(a[n])


question()

Submission status: Wrong Answer

Solution code:
dp=[0]*101
dp[3]=61
p=10**9+7
for i in range(4,101):
  dp[i]=(dp[i-1]*4-pow(4,i-3,p)*3-pow(4,i-4,p))%p
print(dp[100])

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

print( (4**N-(3*(N**(N-3))*(N-2) + 2*(N-3) + max(0,N-4)))%mod )

Submission status: Wrong Answer

Solution code:
N = int(input())
ACGT = []

for i in range(N - 2):
  if i == 0:
    ACGT.append(61)
  elif i == 1:
    ACGT.append(230)
  elif i == 2:
    ACGT.append(ACGT[i - 1] * 4 - (4 ** 2) * 3)
  else:
    ACGT.append(ACGT[i - 1] * 4 - ACGT[i - 3] * 3)

print(ACGT[N - 3] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

print( (4**N-(3*(N**(N-3))*(N-2) + 2*(N-3)))%mod )

Submission status: Time Limit Exceeded

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

def ok(x, y, z, nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def f(num,A):
  if num==N:
    return 1
  else:
    x,y,z=A[0],A[1],A[2]
    if (x,y,z) in memo[num]:
      return  memo[num][(x,y,z)]
    else:
      s=0
      for i in ['A','C','G','T']:
        if ok(x,y,z,i):
          s+=f(num+1,(y,z,i))
      #memo[num][(x,y,z)]=s%mod
      return s%mod
print(f(0,'ZZZ'))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**9+7
if n == 3:
  print(61)
  exit()
  
st = ['AGC','GAC','ACG','AGTC','AGGC','ATGC']
from collections import deque
st = deque(st)
l = 3
cnt = 0
e = n-3

while st:
  if cnt == l:
    st = set(st)
    l = len(st)
    cnt = 0
    e -= 1
    st = deque(st)
  j = st.popleft()
  if e == 0:
    a = l%mod
    break
  else:
    st.append('A'+j)
    st.append('G'+j)
    st.append('C'+j)
    st.append('T'+j)
    st.append(j+'A')
    st.append(j+'C')
    st.append(j+'G')
    st.append(j+'T')
  cnt += 1
  
print(pow(4,n,mod)-a)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 


mod=10**9+7
def dfs(s,n):
    ans=0
    if "AGC"in s or "GAC" in s or "ACG" in s or "ACGC" in s or "ATGC" in s or "AGAC" in s or "AGTC" in s or "AGGC" in s:
        return 0
    elif len(s)==n:
        return 1
    
    for i in "ACGT":
        ans+=dfs(s+i,n)%mod
    return ans%mod


    
def main():
    n=int(input())
    print(dfs("",n))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
mod = 10**9 + 7
A, G, C, T = 'A', 'G', 'C', 'T'
count = 0


def seq(length, s3, s2, s1):
    if length == n:
        global count
        count += 1
        count %= mod
        return

    if [s2, s1] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s2, s1] == [A, C]:
        for x in [A, C, T]:
            seq(length+1, s2, s1, x)

    elif [s2, s1] == [G, A]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s3, s1] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    elif [s3, s2] == [A, G]:
        for x in [A, G, T]:
            seq(length+1, s2, s1, x)

    else:
        for x in [A, C, G, T]:
            seq(length+1, s2, s1, x)


seq(0, T, T, T)
print(count)

Submission status: Time Limit Exceeded

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

def calc(l, ans):
    if len(l) == n:
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        return ans + 1
    for alphabet in "AGCT":
        ll = l + alphabet
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        ans = calc(ll, ans)
    return ans

print(calc("", 0) % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def judge(x):
    for i in range(4):
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
        if ''.join(x).count('AGC') >= 1:
            return False
        if i >= 1:
            x[i-1], x[i] = x[i], x[i-1]
    return True
LI = ['A','G','C','T']
def dp(n,p,q,r):
    if n == 3:
        if [p,q,r] == ['A','G','C']:
            return 0
        elif [p,q,r] == ['A','C','G']:
            return 0
        elif [p,q,r] == ['G','A','C']:
            return 0
        else:
            return 1
    else:
        cnt = 0
        for l in LI:
            if judge([l,p,q,r]):
                cnt += dp(n-1,l,p,q)
        return cnt
ans = 0
for i in LI:
    for j in LI:
        for k in LI:
            ans += dp(N,i,j,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]


n = readInt()
M = 10 ** 9 + 7


dp = np.zeros((n + 1, 256), dtype=np.uint32)
dp[0, 255] = 1


for i in range(n):
    for l4 in range(4):
        for l3 in range(4):
            for l2 in range(4):
                for l1 in range(4):
                    j = 64 * l4 + 16 * l3 + 4 * l2 + l1
                    for l0 in range(4):
                        l = (64 * l3 + 16 * l2 + 4 * l1 + l0),

                        if 6 not in [
                            (16 * l2 + 4 * l1 + l0),
                            (16 * l3 + 4 * l1 + l0),
                            (16 * l1 + 4 * l2 + l0),
                            (16 * l2 + 4 * l0 + l1),
                            (16 * l3 + 4 * l2 + l0)
                        ]:
                            dp[i + 1, l] = (dp[i + 1, l] + dp[i, j]) % M

ret = 0
for v in dp[-1]:
    ret = (ret + v) % M
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def chk_agc(cur):
    l=len(cur)
    result = True
    if l>2:
        for_chk_3 = cur[l-3]+cur[l-2]+cur[l-1]
        if for_chk_3 == "AGC" or for_chk_3 == "ACG" or for_chk_3 == "GAC":
            #print(for_chk_3)
            result=False
        if l>3:
            for_chk_4 = cur[l-4]+cur[l-3]+cur[l-2]+cur[l-1]
            if for_chk_4[3]=="C" and for_chk_4[0]=="A" and (for_chk_4[1]=="G" or for_chk_4[2]=="G"):
                #print(for_chk_4)
                result=False
    return result

def count_agc(i,n,ans,cur,already):
    if i==n+1:
        if not already:
            ans+=1
        return ans
    for char in ["A","G","C","T"]:
        next_already = True
        temp_str = cur
        temp_str+=char
        #文字列の長さはNじゃないといけない
        if already:
            if not chk_agc(temp_str):
                next_already=False
        else:
            next_already=False
        ans = count_agc(i+1,n,ans,temp_str,next_already)
    return ans
n=int(input())
print((pow(4,n)-count_agc(1,n,0,"",True))%10000000007)

Submission status: Time Limit Exceeded

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for _ 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 x in 'ATGC':
        if ok(last3 + x):
            ret = (ret + dfs(cur + 1, last3[1:] + x)) % MOD
    #memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

memo = []
DNA = ["A","C","G","T"]
ng3 = ["AGC","ACG","GAC"]
ng4 = ["ACGC","AGGC","ATGC", "AGAC", "AGTC"]
memo2 = []
def main():
    N = int(input())
    # ACGTからなる
    # 部分文字列AGCを持たない
        # AGC
    # 隣接する2文字の入れかえを1回することでうえの条件に違反しない
        # ACG
        # GAC
        # A-GC
        # AG-C

    # 4^N個の通り

    # 動的計画法
        # 違反があったやつの打ち切り
        # すでに組み合わせの通りが分かっているやつの省略
    # 再帰
    # count = pow(4,N)
    string_check("",0,N)
    # print(memo2)
    print(len(memo))


def string_check(nowstr,i,N):
    slen = len(nowstr)
    if slen == 3:
        if nowstr in ng3:
            # memo2.append(nowstr)
            return
        # print(nowstr)
    if slen == 4:
        # print(nowstr)
        # print(nowstr[-3:])
        if nowstr[:3] in ng3:
            # memo2.append(nowstr)
            return
        elif nowstr[-3:] in ng3:
            # memo2.append(nowstr)
            return
        elif nowstr in ng4:
            # memo2.append(nowstr)
            return
    elif slen > 4:
        if nowstr[-3:] in ng3:
            return
        elif nowstr[-4:] in ng4:
            return
    if i == N:
        # print(nowstr)
        memo.append(nowstr)
        return
    else:
        i+=1
        for s in DNA:
            string_check(nowstr+s,i,N)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N = int(input())
MOD = 1e9+7

def chk_str (s):
  for i in range(4):
    tmp = list(s[-4:])
    if i > 0:
      tmp[i], tmp[i-1] = tmp[i-1], tmp[i]
    if ''.join(tmp).count("AGC") == 1:
      return False
  return True

def count_str (s="_"):
  if len(s) == N+1:
    return 1
  if len(s) < 3:
    return(sum(count_str(s + x) for x in 'ATCG'))
  else:
    cnt = 0
    for x in 'ATCG':
      if chk_str(s + x):
        cnt += count_str(s + x)
    return cnt
    
      
print(count_str())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = 10**9 + 7
def check(L4):
  for i in range(4):
    t = list(L4)
    if i > 0:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True
def dfs(d, L3):
  if d >= n:
    return 1
  ret = 0
  for L in list("ACGT"):
    L4 = "".join([L3, L])
    if check(L4):
      ret += dfs(d + 1, L4[1:])
  return ret
    
  
  
print(dfs(0, "TTT"))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def dfs(last3, c, n):
  str3 = last3[1:] + c
  str4 = last3 + c
  if str3 == "AGC" or str3 == "ACG" or str3 == "GAC" or str4 == "AGGC" or str4 == "ATGC" or str4 == "AGAC" or str4 == "AGTC":
    return 0
  if n == N:
    return 1
  ret = 0
  for a in "AGCT":
    ret += dfs(str3, a, n + 1)
  return ret

ans = 0
for a in "AGCT":
  ans += dfs("TTT", a, 1)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]

def func(S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    else:
        if len(S)-3==N:
            return 1
        return func(S+"A") + func(S+"C") + func(S+"G") + func(S+"T")


print(func("___"))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def match(s):
    if 'AGC' in s:
        return False
    if 'ACG' in s:
        return False
    if 'GAC' in s:
        return False
    for c in 'ATGC':
        if 'A' + c + 'GC' in s:
            return False
        if 'AG' + c + 'C' in s:
            return False
    return True


cache = dict()
def func(n):
    if n in cache:
        return cache[n]

    if n <= 100:
        import itertools
        candidates = itertools.product(*([{'A', 'T', 'G', 'C'}] * n))
        count = 0
        for candidate in candidates:
            if match(''.join(candidate)):
                count += 1
        
        cache[n] = count

    else:
        cache[n] = 4 * func(n-1) - func(n-3) - 8 * func(n-4)
    
    cache[n] = cache[n] % (10 ** 9 + 7)
    return cache[n]

print(func(N))

Submission status: Time Limit Exceeded

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

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

answer=0
for s in itertools.product('ATGC', repeat=N):
  answer += not repattern.search(''.join(s))

print(answer)

import numpy

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
black_list= [
    "GACA", "GACC", "GACG", "GACT",
    "ACGA", "ACGC", "ACGG", "ACGT",
    "AGAC", "AGCC", "AGGC", "AGTC",
    "AGCA", "AGCG", "AGCT",
    "AAGC", "ATGC",
    "CAGC", "GAGC", "TAGC",
    "CGAC", "GGAC", "TGAC",
    "AACG", "CACG", "TACG"
]

def func(S):
    if N==3:
        return 61
    if S[-4:] in black_list:
        return 0
    else:
        if len(S)-4==N:
            return 1
        return func(S+"A") + func(S+"C") + func(S+"G") + func(S+"T")


print(func("____"))

Submission status: Time Limit Exceeded

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


num = 0
def chk(s):
  if ('AGC' in s) or ('ACG' in s) or ('GAC' in s):
    return 1
  elif ('AGAC' in s) or ('AGGC' in s) or ('AGTC' in s):
    return 1
  elif ('ACGC' in s) or ('AGGC' in s) or ('ATGC' in s):
    return 1
  else:
    return 0

def solve(n, s):
  if n == 0:
    if chk(s) > 0:
      return 1
    else:
      return 0
  else:
    ret = 0
    for c in ['A','C','G','T']:
      ret += solve(n-1,s+c)
    return ret

N = int(input())
num = solve(N,"")
print(4**N-num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())

def DP(now, depth):
  cand = []
  for c in [now+'A', now+'G', now+'C', now+'T']:
    if 'AGC' in c or 'GAC' in c or 'ACG' in c or 'AGGC' in c or 'ATGC' in c or 'AGTC' in c:
      continue
    else:
      cand.append(c)
  if depth >= N-1:
    return len(cand)
  node_count = 0
  for c in cand:
    node_count += DP(c, depth=depth+1)
  return node_count

print(DP('', depth=0)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import re
def conv(cur, N):
    s = [0] * N
    ptr = 0
    while ptr < N:
        code = cur % 4
        if code == 0:
            s[ptr] = "A"
        elif code == 1:
            s[ptr] = "G"
        elif code == 2:
            s[ptr] = "T"
        elif code == 3:
            s[ptr] = "C"
        cur = cur // 4
        ptr += 1
    return s

    
def main():
    N = int(input())
    current = 0
    res = 4 ** N
    for i in range(4 ** N):
        S = "".join(conv(current, N))
        if "AGC" in S or "ACG" in S or "GAC" in S or len(re.findall("A.GC|AG.C", S)) == 1:
            res -= 1
            res = res % 1000000007
        current += 1
    print(res)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import itertools
import numpy as np

N = int(input())

mod = 1000000007

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

NGs = ['AGC','GAC','ACG','AGGC','ATGC','AGTC']

# for i in range(3,8):
#     print('N=',i)
#     NG_count = [0,0,0,0,0,0]
#     count = 0
#     for mozi in itertools.product(ATGC,repeat=i):
#         a = "".join(mozi)
#         for j in range(6):
#             if NGs[j] in a:
#                 # print(a)
#                 NG_count[j] += 1
#                 break
#     print(NG_count, sum(NG_count), i**4 - sum(NG_count))


count = 0
for mozi in itertools.product(ATGC,repeat=N):
    a = "".join(mozi)
    for j in range(6):
        if NGs[j] in a:
            count += 1
            break

print((4**N - count) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
N = int(input().strip())
c = 0
all = [''.join(p) for p in list(itertools.product(list('ACGT'), repeat=N))]
for p in all:
  if 'AGC' in p or 'GAC' in p or 'ACG' in p or 'AGGC' in p or 'ATGC' in p or 'AGTC' in p:
    continue
  c += 1
print(c%1000000007)

Submission status: Accepted

Solution code:
n = int(input()); x = 0
dp = [[[[0]*4 for q in range(4)] for p in range(4)] for i in range(n-2)]
ng = ["012", "021", "102", "0112", "0132", "0312"]
for p in range(4):
    for q in range(4):
        for r in range(4):
            if str(p)+str(q)+str(r) not in ng:
                dp[0][p][q][r] += 1
for i in range(n-3):
    for p in range(4):
        for q in range(4):
            for r in range(4):
                for s in range(4):
                    if str(p)+str(q)+str(r)+str(s) not in ng and str(q)+str(r)+str(s) not in ng:
                        dp[i+1][q][r][s] += dp[i][p][q][r]
for p in range(4):
    for q in range(4):
        for r in range(4):
            x = (x+dp[-1][p][q][r])%(10**9+7)
print(x)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

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

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

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

    ans = 0
    if n>=4:
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    ans += temp[i][j][k]
    elif n==3:
        ans = 61
    ans %= mod
    print(ans)

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

Submission status: Accepted

Solution code:
# 隣接する2文字の入れ替えでAGCとなるパターン(もしくはAGCそのもの)
# AGC
# ACG
# GAC
# AGGC
# ACGC
# ATGC
# AGAC
# AGGC
# AGTC
# 上記を含まない文字列を数える

import sys
readline = sys.stdin.readline

N = int(readline())
DIV = 10 ** 9 + 7

# dp[i][a][b][c] = i文字目について、2つ前がa,1つ前がb,i文字目がdの数で条件を満たすものの数
# 0:"A", 1:"G", 2:"C", 3:"T"
dp = [[[[0] * 4 for b in range(4)] for a in range(4)] for i in range(N)]

C = {0:"A", 1:"G", 2:"C", 3:"T", 4:""}
NG = set(["AGC","ACG","GAC","AGGC","ACGC","AGAC","AGGC","ATGC","AGTC"])

def check_ok(i,j,k,l = 4):
  if (C[i] + C[j] + C[k] + C[l]) in NG:
    return False
  return True

# 3文字目
for i in range(4):
  for j in range(4):
    for k in range(4):
      if check_ok(i,j,k):
        dp[2][i][j][k] += 1

# 4文字目以降を決める
for i in range(2, len(dp) - 1):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for k in range(4):
          if check_ok(a,b,c,k) and check_ok(b,c,k):
            dp[i + 1][b][c][k] += dp[i][a][b][c]
            dp[i + 1][b][c][k] %= DIV
        
ans = 0
for a in range(4):
  for b in range(4):
    for c in range(4):
      ans += dp[-1][a][b][c]
      ans %= DIV
      
print(ans)