abc 122 d (python)

i 文字目を A にした時の文字列の作り方の総数を f(i,0) = dp[i-1][0] として f(n) = sum(dp[n-1]) を求める。
例えば７文字の作り方の総数 f(7) を考えるときは新たに条件を満たさなくなるのは、
○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C、
となるものであるから、 f(3) までは総数としてすべて使えるので
dp[i] の遷移を考えるのは dp[i-3] まででよい

基本的に dp[i][j] = sum(dp[i-1]) となり、そこから消さないといけない
○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C たちを過不足なく考えると、
dp[i-2] から引くのは ○○○○AGC、○○○○GAC、○○○○ACG
dp[i-3] から引くのは ○○○ATGC、○○○AGTC、○○○AGGC、となる
そして ○○○GACG を余分に１回引いていることになるので（これだけはそもそも f(6) の時点で○○○GACとなり消されているので引く必要がない）
○○○GACG 分を足す。
（末尾が C, G になる dp[i][1], dp[i][2] だけ dp[i] = sum(dp[i-1]) をした後に足し引きする工程が発生する）
これはサンプル１と２を見て、 61*4-230 = 14 個分減っていることから
n=3 から 4 になる時に条件を満たさなくなる 14 パターンを全部調べたときに分かった。

n = int(input())
mod = 10**9+7
# dp[i][0] が i+1 文字で末尾がAとなる総数、dp[i][1] がC、dp[i][2] がG、dp[i][3]がT
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] #○○○○AGC 分を引く
  dp[i][1] -= dp[i-2][2] #○○○○GAC 分を引く
  dp[i][1] -= dp[i-3][0]*3 #AGTC, AGGC, ATGC を引く
  dp[i][2] -= dp[i-2][0] #○○○○ACG 分を引く
  dp[i][2] += dp[i-3][2] #○○○GACG 分を足す
  
print(sum(dp[n-1])%mod)