題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟣 ABC458F Critical Misread

Problem Statement

題目簡述

給定 $K$ 個只含小寫英文字母的字串。請計算有多少個長度為 $N$ 、只含小寫英文字母的字串，不包含任一給定字串作為連續子字串。
答案需對 $998244353$ 取模。

Constraints

約束條件

$1 \le N \le 10^9$ 。
$1 \le K \le 10$ 。
$1 \le |S_i| \le 10$ 。
$S_i$ 只包含小寫英文字母。

思路：AC 自動機 + 矩陣快速冪

先從最樸素的想法開始。如果當前狀態為 $s$ （先不管要如何得出狀態），那麼下一步就是考慮在字串後面增加一個小寫字母。假設增加字母 $c$ 後會轉移到狀態 $t$ ，且這個過程沒有讓任何禁字串出現，那麼目前狀態的方案數就可以貢獻給下一個狀態。

也就是說，可以定義：

f_i[s] = \text{填了 } i \text{ 個字元後，位於狀態 } s \text{ 的方案數}

若從狀態 $s$ 加上某個字元後能合法走到狀態 $t$ ，就有轉移：

f_{i+1}[t] \leftarrow f_{i+1}[t] + f_i[s]

初始時還沒有填任何字元，只在起始狀態有一種方案。

這個想法已經初具雛形，但還有兩個問題需要解決：

狀態 $s$ 要如何表示，才能判斷加入一個字元後是否出現禁字串？
$N$ 可以到 $10^9$ ，不能真的推進 $N$ 輪，要如何加速？

第一個問題可以用 AC 自動機解決：將給定的禁字串視為模式串，建構 AC 自動機。讓目前狀態記錄「目前字串後綴」對應到哪個模式串前綴。只要再加入一個字元後沒有匹配到任何模式串，就可以轉移。

前置知識

AC 自動機可以看成「Trie + fail 指標」的多模式匹配工具。把所有模式串放進 Trie 後，每個節點都對應到某個模式串的前綴。

掃描目前構造出的字串時，所在節點表示「目前字串的一個後綴」等於「某個模式串的前綴」。如果這個前綴剛好是一整個模式串，或沿著 fail 指標能找到一整個模式串，就代表目前字串已經包含模式串。

這裡只使用 AC 自動機提供的匹配狀態來做 DP，不詳細展開說明；具體的原理可以見 OI Wiki。

在確認使用 AC 自動機後，狀態數量就是 Trie 的節點數。根據限制條件，模式串最多有 $10$ 個、每個長度最多 $10$ ，所以除了根節點以外，節點數不超過所有模式串總長，也就是至多 $100$ 個左右。

而對於任意的 $i$ ，從 $f_i$ 到 $f_{i+1}$ 的轉移規則完全相同，和 $i$ 無關，因此可以用矩陣快速冪加速。

標記非法狀態

根據題意，任何包含模式串的字串都不合法。也就是說，當前狀態如果已經匹配到某個模式串，就不能再繼續延伸。

透過 AC 自動機的特性，當前狀態如果滿足以下任一條件，就代表目前字串已經包含模式串：

節點本身有完整模式串結尾。
節點的 last 指標不是根節點，表示某個後綴已經匹配到模式串。

如何列出轉移矩陣

注意上面的轉移只和目前狀態與加入字元有關，和 $t$ 無關。因此可以把「走一步」寫成固定矩陣。

令轉移矩陣為 $T$ ，並採用 column vector 表示狀態計數。也就是說：

F_{t+1} = T F_t

那麼矩陣中的元素應該這樣定義：

T_{v,u} = \#\{c \in \texttt{a..z} \mid \delta(u,c)=v,\ u,v \text{ 都是合法狀態}\}

其中 $\delta(u,c)$ 表示在 AC 自動機上，從狀態 $u$ 加入字元 $c$ 後到達的狀態。

最後答案

算出 $F_N$ 後，每個合法狀態都代表一批長度為 $N$ 、且尚未包含任何模式串的字串。因此答案就是所有合法狀態的方案數總和：

\sum_{u \text{ is valid}} F_N[u]

不過非法狀態不會被放進轉移，所以它們最後仍然是 $0$ ，因此也能直接對所有狀態求和。

複雜度分析

時間複雜度： $\mathcal{O}(L|\Sigma| + L^3\log N)$ ，其中 $L=\sum |S_i|$ ，且本題有 $L \le 10\times 10=100$ ， $|\Sigma|=26$ 。
AC 自動機節點數至多為 $L+1$ ，可視為 $\mathcal{O}(L)$ ；建自動機與建立轉移矩陣需要 $\mathcal{O}(L|\Sigma|)$ ，矩陣快速冪為 $\mathcal{O}(L^3\log N)$ 。
空間複雜度： $\mathcal{O}(L|\Sigma| + L^2)$ ，分別來自 AC 自動機轉移與矩陣。

Code

from collections import deque

MOD = 998244353


class Node:
    def __init__(self):
        self.child = [None] * 26
        self.fail = None  # fail pointer
        self.last = None  # suffix link，用來快速跳到一定是某個 word 結尾的節點
        self.length = 0  # 可以取代 is_end 和 depth
        self.id = -1


class AhoCorasick:
    def __init__(self):
        self.root = Node()
        self.root.id = 0
        self.nodes = [self.root]  # 保留所有節點

    def insert(self, word: str):
        node = self.root
        for ch in word:
            c = ord(ch) - ord("a")
            if not node.child[c]:
                node.child[c] = Node()
                node.child[c].id = len(self.nodes)
                self.nodes.append(node.child[c])
            node = node.child[c]
        node.length = len(word)

    def build(self):  # O(|Σ|N)，N 是節點數；若 |Σ|=26 視為常數，則為 O(N) = O(L)
        self.root.fail = self.root.last = self.root
        # BFS
        q = deque()
        for i, v in enumerate(self.root.child):
            if v is None:
                # 添加虛擬子節點
                self.root.child[i] = self.root
            else:
                v.fail = v.last = self.root
                q.append(v)
        while q:
            u = q.popleft()
            for i, v in enumerate(u.child):
                if v is None:
                    # 添加虛擬子節點
                    u.child[i] = u.fail.child[i]
                else:
                    # 失配位置
                    v.fail = u.fail.child[i]
                    # 上一個一定是某個 word 結尾的節點
                    v.last = v.fail if v.fail.length else v.fail.last
                    q.append(v)


class Matrix:
    def __init__(self, mat):
        self.mat = mat

    def __mul__(self, other):
        A, B = self.mat, other.mat
        assert len(A[0]) == len(B)
        n, p, m = len(A), len(B), len(B[0])
        res = [[0] * m for _ in range(n)]
        for i in range(n):
            ri = res[i]
            Ai = A[i]
            for k in range(p):
                if Ai[k] == 0:
                    continue
                x = Ai[k]
                Bk = B[k]
                for j in range(m):
                    ri[j] = (ri[j] + x * Bk[j]) % MOD
        return Matrix(res)

    def __pow__(self, k):
        assert len(self.mat) == len(self.mat[0])
        n = len(self.mat)
        res = Matrix([[int(i == j) for j in range(n)] for i in range(n)])
        base = self
        while k > 0:
            if k & 1:
                res *= base
            base *= base
            k >>= 1
        return res

    def mul_pow(self, k, x):
        assert len(self.mat[0]) == len(x.mat)
        res = x
        base = self
        while k > 0:
            if k & 1:
                res = base * res
            base *= base
            k >>= 1
        return res

    def __getitem__(self, i):
        return self.mat[i]

    def __str__(self):
        return "\n".join(map(lambda x: " ".join(map(str, x)), self.mat))


def solve():
    n, k = map(int, input().split())

    ac = AhoCorasick()
    for _ in range(k):
        ac.insert(input().strip())
    ac.build()

    nodes = ac.nodes
    m = len(nodes)

    bad = [False] * m
    for node in nodes:
        if node.length > 0 or node.last != ac.root:
            bad[node.id] = True

    # T[v][u] 表示從 u 狀態加入一個字元後，到達 v 狀態的方案數
    T = [[0] * m for _ in range(m)]
    for u in nodes:
        if bad[u.id]:
            continue
        for v in u.child:
            if bad[v.id]:
                continue
            T[v.id][u.id] += 1

    T = Matrix(T)
    f = Matrix([[1] if i == 0 else [0] for i in range(m)])
    f = T.mul_pow(n, f)

    ans = sum(f[i][0] for i in range(m) if not bad[i]) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @梅原生（せい）. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.