BZOJ 3530 [SDOI2014] 數數：AC自動機 + 數位DP 計數幸運數

題目大意

給定上限 N（長度 ≤ 1200）和禁忌字符串集合 S（共 M ≤ 100 個，總長度 L ≤ 1500）。若一個正整數的十進制表示不包含 S 中任一字符串作為子串，則稱為「幸運數」。求不超過 N 的幸運數個數，答案模 10⁹+7。

核心思路：AC自動機 + 數位DP

這是「敏感詞過濾」與「數位DP」的經典結合：

1. 將所有禁忌串插入 Trie 字典樹
2. 構建 失配指針，形成 AC 自動機（有向圖）
3. 在自動機上跑 數位 DP，狀態包含：
   • 位置 pos（已處理前幾位）
   • 自動機節點 node（當前匹配狀態）
   • 是否受 N 限制 tight（前綴是否等於 N 的前綴）
   • 是否已出現禁忌串 matched（實際上只要避開標記為禁忌的節點即可）
4. 特殊處理：無前導零，即第一位不能走 t[1][0]

狀態轉移

dp[pos][node][tight] 表示前 pos 位、自動機處於 node、受限狀態為 tight 的合法方案數。

• tight = 0：已經比 N 的前綴小，後續位可任選 0-9
• tight = 1：前綴與 N 完全相同，當前位上限為 N[pos]

轉移時枚舉下一位數字 d，沿自動機邊 go[node][d] 跳轉，若目標節點被標記為禁忌（v[target]），則跳過。

關鍵代碼片段

// AC自動機構建（BFS構建失配指針）
void bfs() {
    queue q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        v[u] |= v[fail[u]]; // 繼承失配節點的禁忌標記
        for (int c = 0; c < 10; ++c) {
            if (trie[u][c]) {
                fail[trie[u][c]] = trie[fail[u]][c];
                q.push(trie[u][c]);
            } else {
                trie[u][c] = trie[fail[u]][c]; // 補全轉移邊
            }
        }
    }
}

// 數位DP
// f[i][j][k]: 前i位，自動機節點j，tight=k的方案數
// 分兩階段：位數 < len(N) 和位數 == len(N)
// 詳見原代碼完整實現

複雜度分析

• 自動機節點數：≤ 總長度 L + 1 ≤ 1501
• DP 狀態數：位數(≤1200) × 節點數(≤1501) × 2 ≈ 3.6M
• 轉移：每狀態枚舉 10 個數字
• 總時間：~3.6×10⁷ 次操作，配合優化可通過
• 空間：滾動數組優化至 2 × 節點數 × 2

易錯點提醒

1. 前導零處理：第一位只能 1-9，不能走 trie[1][0]
2. 禁忌標記傳遞：v[u] |= v[fail[u]] 確保失配路徑上的禁忌也被標記
3. 模運算：每次加法後取模 1e9+7
4. 邊界：N 本身可能是幸運數，需包含在內