【POJ-2778】DNA Sequence（DP转移+矩阵快速幂+AC自动机）

题目连接：https://vjudge.net/problem/POJ-2778

题目大意

给定 (m) 个字符串，问构造一个长度为 (n) 的字符串，使其不含 (m) 个字符串，问构造方法种类。

思路

AC自动机和矩阵快速幂部分这篇博客已经说的很好了，个人主要是 AC自动机病毒后缀的转移 和 DP递推式 卡了很久。

首先是AC自动机上病毒后缀的转移，AC自动机的fail指针指向的是指以节点 (x) 结尾的文本串在其他模式串中所能匹配的最长前缀的地方。

若其fail指针所指向的地方为 (m)个字符串的结尾，那么其也不可达，在 (build) 时能够保证顺序。

然后是DP递推式，设 (dp[i][j]) 为走了(j) 步到达节点 (i) 的方案数，显然 (dp[0][0]=1)，当 (i eq 0) 时，(dp[i][0]=0)。

设 (a[i][j]) 为从节点 (i) 到达节点 (j) 是否存在边。

最终得 (dp[i][j] = sum_{x=0}^{N} a[x][i] * dp[x][j-1])，这部分可以用矩阵快速幂解决。

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

typedef long long ll;
using namespace std;

const int MAXN = 1e6 + 5;
const int MAXM = 110;
const int mod = 100000;

class mat {
public:
    int n, m;
    int v[MAXM][MAXM];

    mat(int n, int m) : n(n), m(m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                v[i][j] = 0;
        }
    }

    void init() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                v[i][j] = 0;
        }
    }

    void init1() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                v[i][j] = (i == j); //单位矩阵
    }

    mat operator*(const mat &B) const {//矩阵乘法 A(n,k)*B(k,m)=C(n,m);
        mat C(n, B.m);
        C.init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < B.m; j++)
                for (int k = 0; k < m; k++)
                    C.v[i][j] = (C.v[i][j] + (ll) v[i][k] * B.v[k][j] % mod) % mod;//Mod
        return C;
    }

    mat operator^(int t) {//矩阵快速幂 n=m时可用
        mat ans(n, n), now(n, n);
        ans.init1();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                now.v[i][j] = v[i][j];
        while (t > 0) {
            if (t & 1) ans = ans * now;
            now = now * now;
            t >>= 1;
        }
        return ans;
    }

    void debug() {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                printf("%d ", v[i][j]);
            }
            printf("
");
        }
    }

};


int char2id(char ch) {
    switch (ch) {
        case 'A':
            return 0;
        case 'T':
            return 1;
        case 'G':
            return 2;
        case 'C':
            return 3;
    }
}

class AC {
public:
    int T[MAXN][4], top;
    bool endpos[MAXN];
    int fail[MAXN];
    queue<int> q;

    void init() {
        top = 1;
        memset(T[0], 0, sizeof(T[0]));
        endpos[0] = fail[0] = 0;
    }

    void insert(char str[], int lenstr) {
        int u = 0;
        for (int i = 1; i <= lenstr; i++) {
            int ch = char2id(str[i]);
            if (!T[u][ch]) {
                endpos[top] = fail[top] = 0;    // init a node
                memset(T[top], 0, sizeof(T[top]));
                T[u][ch] = top++;
            }
            u = T[u][ch];
        }
        endpos[u] = 1;
    }

    void build() {
        for (int i = 0; i < 4; i++)
            if (T[0][i]) {
                fail[T[0][i]] = 0;
                q.push(T[0][i]);
            }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (endpos[fail[u]]) endpos[u] = 1;
            for (int i = 0; i < 4; i++)
                if (T[u][i]) {
                    fail[T[u][i]] = T[fail[u]][i];
                    q.push(T[u][i]);
                } else T[u][i] = T[fail[u]][i];
        }
    }

    void build_mat(mat &mat) {
        mat.init();
        for (int i = 0; i < top; i++) {
            if (endpos[i]) continue;
            for (int j = 0; j < 4; j++) {
                if (!endpos[T[i][j]]) mat.v[i][T[i][j]]++;
            }
        }
    }

} ac;

char str[MAXN];


int main() {

    int m, n;
    while (~scanf("%d%d", &m, &n)) {
        ac.init();
        while (m--) {
            scanf("%s", str + 1);
            ac.insert(str, strlen(str + 1));

        }
        ac.build();


        mat ma(ac.top, ac.top);
        ac.build_mat(ma);

        ma = ma ^ n;
        int res = 0;
        for (int i = 0; i < ac.top; i++) {
            res = (res + ma.v[0][i]) % mod;
        }
        printf("%d
", res);
    }
}

/*
2 10
AG
CG
 */