BZOJ 1030 [JSOI2007] 文本生成器：AC自動機 + DP 計數可讀文本

題目大意

給定 N (≤ 60) 個已知單詞（大寫字母，長度 ≤ 100），文本生成器生成固定長度 M 的隨機文本（每位等概率 A-Z）。若文本包含至少一個已知單詞作為子串，則稱「可讀」。求可讀文本總數模 10007。

核心建模：AC自動機上的 DP

1. 將所有單詞插入 Trie，標記結尾節點為 terminal
2. 構建失配指針，形成 AC 自動機
3. 傳遞 terminal 標記：terminal[u] |= terminal[fail[u]]
4. 問題轉化為：從根節點出發，走 M 步，經過至少一個 terminal 節點的路徑數

DP 狀態設計

dp[step][node][flag]：走 step 步，到達 node，flag=0 表示從未經過 terminal，flag=1 表示已經經過 terminal 的方案數。

狀態轉移

// 初始：0 步在根節點，未經過 terminal
dp[0][1][0] = 1;

for (int i = 0; i < M; ++i) {
    for (int u = 1; u <= tot; ++u) {
        for (int c = 0; c < 26; ++c) {
            int v = trie[u][c];
            if (terminal[v]) {
                // 到達 terminal 節點，flag 變為 1（無論之前如何）
                dp[i+1][v][1] = (dp[i+1][v][1] + dp[i][u][0] + dp[i][u][1]) % MOD;
            } else {
                // 非 terminal，flag 保持不變
                dp[i+1][v][0] = (dp[i+1][v][0] + dp[i][u][0]) % MOD;
                dp[i+1][v][1] = (dp[i+1][v][1] + dp[i][u][1]) % MOD;
            }
        }
    }
}

// 答案：M 步後所有節點 flag=1 的和
int ans = 0;
for (int u = 1; u <= tot; ++u) ans = (ans + dp[M][u][1]) % MOD;

關鍵優化：滾動數組

M ≤ 100，tot ≤ 6000，dp[101][6001][2] ≈ 120 萬整數，約 5MB，可直接開靜態數組。也可用 dp[2][tot+1][2] 滾動優化空間。

複雜度

• 時間：O(M × 節點數 × 26) ≤ 100 × 6000 × 26 ≈ 1.56×10⁷
• 空間：O(節點數 × 2) 或 O(M × 節點數 × 2)

易錯點

1. 第一步不能走 'A' 以外？ 題目無前導零限制，但單詞均為大寫字母，根節點轉移正常
2. terminal 傳遞：terminal[u] |= terminal[fail[u]] 確保失配路徑上的單詞也被識別
3. 模數：10007（非質數，但僅做加法模運算無影響）
4. 初始狀態：dp[0][1][0]=1，其餘 0

Sample 驗證

Input:
2 2
A
B
所有長度 2 的大寫串：26² = 676
不含 A/B 的串：24² = 576
可讀 = 676 - 576 = 100 → 模 10007 = 100 ✓