ABC122-D We Like AGC 解説

\(O( \log N )\) で解きます。

問題

AtCoder Beginner Contest 122 | D - We Like AGC

解法

editorial のDP解法をベースに考えます。 \(i\) 文字目を決める際の遷移は \(i\) の値によらず常に固定なので、漸化式を行列の累乗に落とし込むことができます。64次元線形空間の行列を手書きで入力するのは面倒なので、いい感じにプログラムを組みます。気合いで頑張ってください💪

始状態は "TTT" にあたる状態だけ1にしておくと特に調節が不要になります。また、しれっとオーバーフローを起こすのでPythonの多倍長整数演算に頼っています。

定数倍がとても大きいので、この問題の制約の範囲内では素直にDPやメモ化再帰を書くほうが断然早いです。

実装

提出コード（Python）

import numpy as np
import re

mod = 10**9 + 7
letters = "ACGT"

# 文字を添え字に
def to_int(s):
    res = 0
    for x in s:
        res <<= 2
        res += letters.index(x)
    return res

# 添え字を文字に
def to_str(x, digit):
    res = ""
    for _ in range(digit):
        res += letters[x&3]
        x >>= 2
    return res[::-1]

# 部分文字列として含んではいけないものを正規表現で判定
def is_ok(s):
    ng = [r"AGC", r"ACG", r"GAC", r"A.GC", r"AG.C"]
    for x in ng:
        if re.search(x, s):
            return False
    return True

# 行列の二分累乗
def mat_power(A, p, mod):
    res = np.eye(A.shape[0], dtype = "object")
    while p:
        if p & 1:
            res = np.dot(res, A) % mod
        A = np.dot(A, A) % mod
        p >>= 1
    return res

# 行列作成各状態からの各遷移が有効か確かめる
A = [[0]*64 for _ in range(64)]
for i in range(64):
    s = to_str(i, 3)
    for j in range(4):
        t = s + to_str(j, 1)
        if is_ok(t):
            A[i][to_int(t[1:])] = 1
A = np.array(A, dtype = "object")

# ベクトル作成TTTのみ立てておく
x = [0]*64
x[63] = 1
x = np.array(x)

N = int(input())
print((np.dot(mat_power(A, N, mod), x) % mod).sum() % mod)