HDU 2825 Wireless Password：AC 自動機 + DP 狀態壓縮

狀態壓縮優化

• m ≤ 10，mask 最大 1024，狀態總數 25 × 150 × 1024 ≈ 380 萬，時間空間均可接受。
• 預計算 popcount[mask] 加速最終統計。

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MOD = 20090717;
const int MAXN = 150, SIGMA = 26, MAXM = 11, MAXL = 30;
int ch[MAXN][SIGMA], val[MAXN], fail[MAXN], last[MAXN], sz;
int dp[MAXL][MAXN][1<>1] + (i&1);
    int n, m, k;
    while (cin >> n >> m >> k, n||m||k) {
        sz = 1; memset(ch[0], 0, sizeof ch[0]); val[0]=0;
        for (int i = 0; i < m; ++i) {
            string s; cin >> s; insert(s, i);
        }
        build();
        cout << solve(n, m, k) << '\n';
    }
}

複雜度分析

• 時間：O(n × sz × 2^m × Σ) ≈ 25 × 150 × 1024 × 26 ≈ 10⁸ 操作，常數較小，C++ 可過。
• 空間：dp 數組 25 × 150 × 1024 × 4B ≈ 15 MB，符合限制。

總結

本題是「多模式串匹配計數」的經典模型：AC 自動機處理重疊匹配，DP 狀態壓縮記錄已匹配集合。關鍵在於正確構建 fail 指針與輸出鏈合併，以及 DP 狀態設計無遺漏無重複。模板化後可解決所有「字符串包含至少 k 個給定模式」類問題。