Day 091-Q3 — Aho-Corasick + オートマトン上DP（禁止パターン回避文字列数え上げ）

問題

$K$ 種類の文字からなる長さ $L$ の文字列のうち、$M$ 個の禁止パターンをいずれも部分文字列として含まないものの個数を $998244353$ で割った余りで求める。$L$ は最大 $10^{18}$。

入出力例

2 1 3
aa

5

文字 a,b の長さ3で aa を含まないのは $8-3=5$ 通り。

2 1 1
aa

2

長さ1では aa を含みようがなく a,b の2通り。

概念図

ヒント

bad[u] = bad[u] or bad[fail[u]]   # fail 継承で禁止伝播
# A[i][j] += 1  (goto(i,c)=j かつ not bad[j])
# 答え = (A^L) の根の行の総和

模範解答

import sys
from collections import deque
MOD = 998244353

def main():
    data = sys.stdin.buffer.read().split()
    K = int(data[0]); M = int(data[1]); L = int(data[2])
    patterns = [data[3 + i].decode() for i in range(M)]

    # --- Aho-Corasick 構築 ---
    children = [[-1] * K]     # ノード0 = 根
    fail = [0]
    bad = [False]
    for p in patterns:
        cur = 0
        for ch in p:
            c = ord(ch) - 97
            if children[cur][c] == -1:
                children[cur][c] = len(children)
                children.append([-1] * K)
                fail.append(0)
                bad.append(False)
            cur = children[cur][c]
        bad[cur] = True

    dq = deque()
    for c in range(K):
        if children[0][c] == -1:
            children[0][c] = 0
        else:
            fail[children[0][c]] = 0
            dq.append(children[0][c])
    while dq:
        u = dq.popleft()
        bad[u] = bad[u] or bad[fail[u]]      # fail 継承で禁止伝播
        for c in range(K):
            v = children[u][c]
            if v == -1:
                children[u][c] = children[fail[u]][c]   # goto 補完
            else:
                fail[v] = children[fail[u]][c]
                dq.append(v)

    S = len(children)
    good = [i for i in range(S) if not bad[i]]
    gid = {s: i for i, s in enumerate(good)}
    n = len(good)

    # 遷移行列（禁止状態は行き先から除外）
    A = [[0] * n for _ in range(n)]
    for s in good:
        i = gid[s]
        for c in range(K):
            t = children[s][c]
            if not bad[t]:
                A[i][gid[t]] = (A[i][gid[t]] + 1) % MOD

    def matmul(X, Y):
        p = len(X); r = len(Y); q = len(Y[0])
        Z = [[0] * q for _ in range(p)]
        for i in range(p):
            Xi = X[i]; Zi = Z[i]
            for k in range(r):
                x = Xi[k]
                if x:
                    Yk = Y[k]
                    for j in range(q):
                        Zi[j] = (Zi[j] + x * Yk[j]) % MOD
        return Z

    def matpow(X, e):
        m = len(X)
        R = [[1 if i == j else 0 for j in range(m)] for i in range(m)]
        while e:
            if e & 1:
                R = matmul(R, X)
            X = matmul(X, X)
            e >>= 1
        return R

    P = matpow(A, L)
    start = gid[0]
    ans = sum(P[start]) % MOD
    print(ans)

main()

Step-by-Step 解説

Step 1: トライ構築

各パターンをたどりノードを作り、終端に bad=True を立てる。

Step 2: fail リンクと goto 補完（BFS）

BFS 順に bad[u] |= bad[fail[u]] で「fail 先が禁止なら自分も禁止」を伝播（接尾辞マッチの取りこぼし防止）。子が無い文字は children[u][c]=children[fail[u]][c] で goto を完成。

Step 3: 禁止状態を除いた遷移行列

非禁止状態 good を列挙し、$A[i][j]$ に「1文字で $i\to j$ に遷移でき $j$ が禁止でない文字数」を積む。

Step 4: 行列累乗で $A^L$

長さ $L$ の経路数は $A^L$。根の行の総和が答え。$L=0$ なら単位行列で答え1（空文字列）。

よくあるミス

次のステップ

• 発展: 「ちょうど $t$ 回マッチ」を数える（状態に回数次元を追加）
• 発展: パターンごとに重み・確率を付けた期待値計算
• 次回予告: NTT（数論変換）

自己評価