POJ 2778 DNA Sequences：AC 自動機 + 矩陣快速冪

題目描述

DNA 序列由 {A,C,T,G} 組成。給定 m (≤10) 個禁止模式串（長度 ≤10），求長度為 n (≤2e9) 的合法序列數（不含任何禁止串作為子串），模 100000。

解題思路：AC 自動機構建狀態轉移圖 + 矩陣快速冪

1. 將所有禁止串插入 Trie，構建 AC 自動機（失敗指針、輸出標記）。
2. 自動機每個非終止狀態對應一個合法前綴狀態。狀態數 ≤ 總節點數 ≤ 100。
3. 構建轉移矩陣 M[S][S]：M[i][j] 為從狀態 i 經一字符轉移到狀態 j 的方式數（0 或 1，四字符）。若 j 為終止狀態（匹配到禁止串），則不建立轉移。
4. 答案為 M^n 中從根狀態 0 到所有非終止狀態的路徑數之和。矩陣快速冪 O(S³ log n)，S ≤ 100，log n ≤ 31，極快。

關鍵代碼結構

struct ACNode {
    int next[4], fail;
    bool end; // 是否匹配到禁止串
} ac[110];

int charId(char c) { // A,C,T,G -> 0,1,2,3
    if (c=='A') return 0;
    if (c=='C') return 1;
    if (c=='T') return 2;
    return 3;
}

void buildAC() {
    queue q;
    for (int i=0;i<4;++i) {
        if (ac[0].next[i]==-1) ac[0].next[i]=0;
        else { ac[ac[0].next[i]].fail=0; q.push(ac[0].next[i]); }
    }
    while(!q.empty()) {
        int u=q.front(); q.pop();
        ac[u].end |= ac[ac[u].fail].end; // 繼承失敗指針的終止性
        for (int i=0;i<4;++i) {
            if (ac[u].next[i]==-1) ac[u].next[i]=ac[ac[u].fail].next[i];
            else { ac[ac[u].next[i]].fail=ac[ac[u].fail].next[i]; q.push(ac[u].next[i]); }
        }
    }
}

// 矩陣乘法與快速冪
using Matrix = array, 110>;
Matrix mul(const Matrix& A, const Matrix& B, int S) { ... }
Matrix mpow(Matrix base, long long exp, int S) { ... }

int main() {
    int m; long long n;
    while (scanf("%d%lld", &m, &n) == 2) {
        // 初始化 AC
        // 插入禁止串
        buildAC();
        // 構建轉移矩陣
        Matrix M = {};
        int S = nodeCnt;
        for (int i=0;i