問題描述

M×N 矩形網格（M,N≤100），從左上 (1,1) 走到右下 (M+1,N+1)，只能向右(R)或向下(D)。給定兩個模式串（長≤100，只含 R/D），要求路徑字符串同時包含這兩個模式串作為子串。求滿足條件的路徑數模 1e9+7。

解題思路：AC 自動機 + DP

1. 將兩個模式串插入 AC 自動機，構建失敗指針與輸出標記（out[u] 表示以節點 u 結尾匹配了哪些模式）。
2. DP 狀態：dp[i][j][u][mask] = 走到格點 (i,j)，自動機狀態為 u，已匹配模式集合為 mask（bit0: 模式1, bit1: 模式2）的路徑數。
3. 轉移：從 (i,j) 可走 R 到 (i,j+1) 或 D 到 (i+1,j)。自動機狀態沿邊轉移：v = go(u, ch)，new_mask = mask | out[v]。
4. 初始：dp[0][0][0][0] = 1。
5. 答案：Σ_u dp[M][N][u][3]（mask=3 表示兩模式全匹配）。

代碼實現要點

struct AC {
    int next[220][2], fail[220], out[220], sz;
    void init() { sz=1; memset(next[0],-1,sizeof(next[0])); out[0]=0; }
    int idx(char c) { return c=='D'?0:1; }
    void insert(const char* s, int id) {
        int u=0;
        for (;*s;++s) {
            int c=idx(*s);
            if (next[u][c]==-1) {
                next[u][c]=sz;
                memset(next[sz],-1,sizeof(next[sz]));
                out[sz]=0;
                ++sz;
            }
            u=next[u][c];
        }
        out[u] |= (1< q;
        for (int c=0;c<2;++c) {
            if (next[0][c]==-1) next[0][c]=0;
            else { fail[next[0][c]]=0; q.push(next[0][c]); }
        }
        while (!q.empty()) {
            int u=q.front(); q.pop();
            out[u] |= out[fail[u]]; // 繼承失敗指針的輸出
            for (int c=0;c<2;++c) {
                if (next[u][c]==-1) next[u][c]=next[fail[u]][c];
                else { fail[next[u][c]]=next[fail[u]][c]; q.push(next[u][c]); }
            }
        }
    }
} ac;

int dp[110][110][220][4];
const int MOD = 1e9+7;

void solve() {
    memset(dp,0,sizeof(dp));
    dp[0][0][0][0]=1;
    for (int i=0;i<=M;++i)
        for (int j=0;j<=N;++j)
            for (int u=0;u

關鍵細節

自動機狀態數：兩模式總長 ≤ 200，節點數 ≤ 201，dp[110][110][220][4] ≈ 100×100×220×4 ≈ 88M int ≈ 350MB，略大。優化：用 short 或滾動數組（只需上一行/列），或壓縮 mask 維度。實際可用 int dp[2][110][220][4] 滾動行。
模式串匹配：out[u] 用 bitmask 標記，合併失敗指針輸出 out[u] |= out[fail[u]]。
邊界：格點 (0,0) 到 (M,N)，共 (M+1)×(N+1) 個點，步數 M+N。


複雜度

時間：O(M·N·S·4) ，S=自動機狀態數 ≤ 200，M,N≤100 → 約 800 萬轉移，極快。
空間：滾動數組 O(N·S·4) ≈ 100×220×4 ≈ 88K int ≈ 350KB。


總結
HDU 4758 將「路徑包含多模式串」轉化為 AC 自動機上走路問題。關鍵步驟：

多模式串構建 AC 自動機，標記輸出。
DP 狀態融合網格座標、自動機狀態、匹配集合。
滾動數組優化空間，模數運算防溢出。

此「網格 DP + 自動機」模板廣泛適用於「路徑受正則語言約束」的計數問題。