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:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # open(0).read() is a convenient method:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')

    # ----------------------------------
    # main

    N = int(r())
    # AA => 0, AC => 1, AG => 2, AT => 3
    # CA => 4, CC => 5, CG => 6, CT => 7
    # GA => 8, GC => 9, GG => 10, GT => 11
    # TA => 12, TC => 13, TG => 14, TT => 15
    dp = [[0]*100 for _ in range(16)]
    anslist = [0] * N
    anslist[0] = 4
    anslist[1] = 16
    for i in range(16):
        dp[i][1] = 1
        dp[i][2] = 4
    dp[1][2] = 3
    dp[6][2] = 3
    dp[9][2] = 3
    for j in range(3, 100):
        for i in range(16):
            for k in range(4):
                dp[i][j] += dp[i//4+4*k][j-1] % MOD
            if i == 1:
                dp[i][j] -= dp[8][j-1] % MOD
            elif i == 6:
                dp[i][j] -= dp[1][j-1] % MOD
            elif i == 9:
                dp[i][j] -= dp[2][j-1] % MOD
            # case when AXGC where X in (G, T)
            if i == 9:
                dp[i][j] -= (dp[2][j-2]+dp[3][j-2])
            # case when AGXC where X in (T)
            if i == 13:
                dp[i][j] -= dp[2][j-2]
        
    if N == 1:
        print(4)
    elif N == 2:
        print(16)
    else:
        ans = 0
        for i in range(16):
            ans += dp[i][N-1]
        print(ans%MOD)
    
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # for
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10**9 + 7

def isValid(text) :  # 有効な4文字の文字列かチェック
    for i in range(4) :
        t = list(text)
        if i >= 1 :
            t[i] , t[i-1] = t[i-1] , t[i]  # swap
        if ''.join(t).count('AGC') >= 1 :
            return False
    return True

memo = [{} for _ in range(N+1)]

def search(currentIndex, prevText) :
    if currentIndex >= N :
        return 1
    if prevText in memo[currentIndex] :
        return memo[currentIndex][prevText]
    ret = 0

    for addText in 'ACGT' :
        if isValid(prevText + addText) :
            ret = (ret + search(currentIndex + 1,prevText[1:] + addText)) % MOD  # 左にシフト

    memo[currentIndex][prevText] = ret
    return ret

print(search(0,'ZZZ'))

Submission status: Accepted

Solution code:
n = int(input())
memo = [dict() for _ in range(n+1)]

memo[0][""] = 1

def ok(last4):
  for ng in ["AGC","ACG","GAC"]:
    if last4.find(ng)>=0:
      return False
  if len(last4) < 4:
    return True
  if last4[0] =="A" and last4[2:]=="GC":
    return False
  if last4[:2]=="AG" and last4[3]== "C":
    return False
  return True

for i in range(1,n+1):
  for last3, v in memo[i-1].items():
    for c in "ATGC":
      if ok(last3+c):
        try:
          memo[i][last3[-2:]+c] += v
        except KeyError:
          memo[i][last3[-2:]+c] = v

MOD = int(10**9+7)
ans = 0
for v in memo[n].values():
  ans += v

print(ans%MOD)

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
#A=0,G=1,C=2,T=3とする

for len in range(N):
    #最後から1文字目
    for c1 in range(4):
        #最後から2文字目
        for c2 in range(4):
            #最後から3文字目
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0:
                    continue
                for c0 in range(4):
                    if c0 ==2 and c1 == 1 and c2 == 0:
                        continue
                    if c0 ==1 and c1 == 2 and c2 == 0:
                        continue
                    if c0 ==2 and c1 == 0 and c2 == 1:
                        continue
                    if c0 ==2 and c1 == 1 and c3 == 0:
                        continue
                    if c0 ==2 and c2 == 1 and c3 == 0:
                        continue
                    dp[len+1][c0][c1][c2] += dp[len][c1][c2][c3]
                    dp[len+1][c0][c1][c2] %= 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 = ans % mod 
            
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m=10**9+7
dp=[{} for _ in range(n+1)]

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

def dfs(cur, last3):
    if last3 in dp[cur]:
        return dp[cur][last3]
    if cur==n:
        return 1

    ret=0
    for c in "AGCT":
        if ok(last3+c):
            ret=ret+dfs(cur+1, last3[1:]+c)
            ret%=m
        dp[cur][last3]=ret
    return ret

print(dfs(0, "___"))

Submission status: Accepted

Solution code:
N = int(input())

MOD = 10**9 + 7

dp =  [ [ [ [ 0 for i in range(5) ] for j in range(5)] for p in range(5)] for q in  range(N+1)]
dp[0][0][0][0] = 1

# 1:A 2:G 3:C 4:T
for n in range(N):
    for i in range(5):
        for j in range(5):
            for p in range(5):
                for q in range(1,5):
                    if i == 1 and j == 2 and q == 3:
                        continue
                    if j == 1 and p == 3 and q == 2:
                        continue
                    if j == 2 and p == 1 and q == 3:
                        continue
                    if j == 1 and p == 2 and q == 3:
                        continue
                    if i == 1 and p == 2 and q == 3:
                        continue

                    dp[n+1][j][p][q] =(dp[n+1][j][p][q] + dp[n][i][j][p]) % MOD

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for p in range(1,5):
            ans = (ans + dp[N][i][j][p]) % MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
DP=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      DP[3][i][j][k]=1
DP[3][0][1][2]=0
DP[3][0][2][1]=0  
DP[3][2][0][1]=0  
for i in range(3,n):
  DP[i+1][0][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][0][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][0][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][0][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][0][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][0][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][0][1][2]=0
  DP[i+1][0][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][0][2][0]=DP[i][2][0][0]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][0][2][1]=0
  DP[i+1][0][2][2]=DP[i][2][2][0]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][0][2][3]=DP[i][2][3][0]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][0][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][0][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][0][3][2]=DP[i][3][2][0]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][0][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][1][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][1][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][1][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][1][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][1][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][1][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][1][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][1][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][1][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][1][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][1][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][1][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][1][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][1][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][1][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][1][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][2][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][2][0][1]=0
  DP[i+1][2][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][2][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][2][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][2][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][2][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][2][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][2][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][2][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][2][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][2][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][2][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][2][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][2][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][2][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][3][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][3][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][3][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][3][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][3][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][3][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][3][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][3][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][3][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][3][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][3][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][3][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][3][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][3][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][3][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][3][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=DP[n][i][j][k]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
DP=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      DP[3][i][j][k]=1
DP[3][0][1][2]=0
DP[3][0][2][1]=0  
DP[3][2][0][1]=0  
for i in range(3,n):
  DP[i+1][0][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][0][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][0][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][0][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][0][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][0][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][0][1][2]=0
  DP[i+1][0][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][0][2][0]=DP[i][2][0][0]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][0][2][1]=0
  DP[i+1][0][2][2]=DP[i][2][2][0]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][0][2][3]=DP[i][2][3][0]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][0][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][0][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][0][3][2]=DP[i][3][2][0]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][0][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][1][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][1][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][1][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][1][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][1][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][1][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][1][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][1][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][1][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][1][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][1][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][1][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][1][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][1][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][1][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][1][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][2][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][2][0][1]=0
  DP[i+1][2][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][2][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][2][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][2][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][2][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][2][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][2][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][2][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][2][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][2][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][2][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][2][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][2][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][2][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][3][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][3][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][3][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][3][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][3][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][3][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][3][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][3][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][3][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][3][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][3][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][3][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][3][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][3][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][3][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][3][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=DP[n][i][j][k]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def elongation(n):
    NG=["AAGC","GAGC","TAGC","CAGC","AGAC","GGAC","CGAC","TGAC","AACG","GACG","CACG","TACG","AGGC","ATGC","AGTC"]
    trinucleotide={"TTT":1}
    new_trinucleotide={}
    MOD=10**9+7
    for k in range(n):
        for i in trinucleotide:
            for j in "AGCT":
                new=i+j
                if new in NG:
                    pass
                else:
                    if new[1:] in new_trinucleotide:
                         new_trinucleotide[new[1:]]=(new_trinucleotide[new[1:]]+trinucleotide[i])
                    else:
                         new_trinucleotide[new[1:]]=trinucleotide[i]
        trinucleotide=new_trinucleotide
        new_trinucleotide={}
    return(sum(trinucleotide.values())%MOD)

print(elongation(int(input())))

Submission status: Accepted

Solution code:
N = int(input())
c = 'AGC'
p = ['A', 'C', 'G', 'T']
s = 'XXX'
memo = [{} for _ in range(N)]
MOD = 10 ** 9 + 7


def agc_check(t):
    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 (c in t) or (c in t1) or (c in t2) or (c in t3):
        return 0
    else:
        return 1


def agc_plus(t, cur):
    if cur == N:
        return 1
    if t in memo[cur]:
        return memo[cur][t]
    r = 0
    for tt in p:
        if agc_check(t + tt):
            r += agc_plus(t[1:] + tt, cur + 1)
    memo[cur][t] = r % MOD
    return memo[cur][t]


ans = agc_plus(s, 0)
print(ans)

Submission status: Accepted

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

def d(s):
    if "AGC" in s:
        return False
    for i in range(3):
        l=list(s)
        l[i],l[i+1]=l[i+1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

m=[{} for i in range(n+1)]
def f(num,s):
    if s in m[num]:
        return m[num][s]
    if num==n:
        return 1
    ans=0
    for c in "ACGT":
        if d(s+c):
            ans=(ans+f(num+1,s[1:3]+c))%mod
    m[num][s]=ans
    return ans

print(f(0,"PPP"))

Submission status: Accepted

Solution code:
N = int(input())
dpA = [0, 1, 4]
dpC = [0, 1, 4]
dpG = [0, 1, 4]
dpT = [0, 1, 4]
dpAG = [0, 0, 1]
dpGA = [0, 0, 1]
dpAC = [0, 0, 1]
dpAT = [0, 0, 1]
dpAGG = [0, 0, 0]
dpATG = [0, 0, 0]
dpAGT = [0, 0, 0]

for i in range(2, N):
	newA = dpA[i] + dpC[i] + dpG[i] + dpT[i]
	newC = dpA[i] + dpC[i] + dpG[i] + dpT[i] - dpAG[i] - dpGA[i] - dpAGG[i] - dpATG[i] - dpAGT[i]
	newG = dpA[i] + dpC[i] + dpG[i] + dpT[i] - dpAC[i]
	newT = dpA[i] + dpC[i] + dpG[i] + dpT[i]
	newAG = dpA[i]
	newGA = dpG[i]
	newAC = dpA[i] - dpGA[i]
	newAT = dpA[i]
	newAGG = dpAG[i]
	newATG = dpAT[i]
	newAGT = dpAG[i]
	dpA.append(newA)
	dpC.append(newC)
	dpG.append(newG)
	dpT.append(newT)
	dpAG.append(newAG)
	dpGA.append(newGA)
	dpAC.append(newAC)
	dpAT.append(newAT)
	dpAGG.append(newAGG)
	dpATG.append(newATG)
	dpAGT.append(newAGT)
print((dpA[N]+dpC[N]+dpG[N]+dpT[N])%1000000007)

Submission status: Accepted

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

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

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1
    ret=0
    for c in "ACGT":
        if ok(last3+c):
            ret=(ret+dfs(cur+1,last3[1:]+c))%mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,"TTT"))

Submission status: Accepted

Solution code:
"""
1.4種類の文字ATGC
2.AGCを作ってはならない
3.隣り合う文字を1箇所だけ入れ替えても、AGCになってはならない

3. が厄介
変えないAGC 
0-1 A*GC
1-2 GAC
2-3 ACG
3-4 AG*C

とりあえず3文字分テーブルに持たせながらdp？
"""

mod = 10**9 + 7
N = int(input())
dp =[[[[0]*5 for i in range(5)] for j in range(5)] for n in range(108)]

nul = 0
A = 1
G = 2
C = 3
T = 4

"""
AGC
0-1 A*GC
1-2 GAC
2-3 ACG
3-4 AG*C
"""
dp[0][0][0][0] = 1
for n in range(N):
    for n3 in range(5):             # 3つ前
        for n2 in range(5):         # 2つ前
            for n1 in range(5):     # 1つ前
                for s in range(1,5):  # 今
                    if n2 == A and n1 == G and s == C: continue
                    if n3 == A and n1 == G and s == C: continue
                    if n2 == G and n1 == A and s == C: continue
                    if n2 == A and n1 == C and s == G: continue
                    if n3 == A and n2 == G and s == C: continue
                    # print(n,n1,n2,n3,s)
                    dp[n+1][n2][n1][s] += dp[n][n3][n2][n1]                    
ans = 0
for i in range(5):
    for j in range(5):
        for k in range(5):
            ans += dp[N][i][j][k]
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
mod = 10 ** 9 + 7

dp[0][0][0][0] = 1
for i in range(n):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                for s in range(1, 5):
                    if l == 3 and k == 1 and s == 2:
                        continue
                    if l == 2 and k == 1 and s == 3:
                        continue
                    if l == 1 and k == 3 and s == 2:
                        continue
                    if k == 3 and j == 1 and s == 2:
                        continue
                    if l == 3 and j == 1 and s == 2:
                        continue
                    dp[i + 1][s][l][k] += dp[i][l][k][j]
                    dp[i + 1][s][l][k] %= mod
ans = 0
for j in range(1, 5):
    for k in range(1, 5):
        for l in range(1, 5):
            ans += dp[n][j][k][l]
print(ans % mod)

Submission status: Accepted

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


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


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


print(dfs(0, 'TTT'))