POJ 2778 DNA Sequence (矩阵快速幂 + AC自动鸡)

题意：给你m个病毒串，只由(A、G、T、C) 组成，问你生成一个长度为 n 的只由 A、C、T、G 构成的，不包含病毒串的序列的方案数。

解：对 m 个病毒串，建 AC 自动机，然后，这个AC自动机就类似于一张有向图，可以用邻接矩阵存这张有向图。

　　最多10个病毒串，每个病毒串长度不超过 10，那最多是个 100 * 100 的矩阵，可以接受。

　　最后用矩阵快速幂加速推导。

#include<cstdio>

#include<cstring>

#include<queue>

#define LL long long

#define rep(i, j, k) for(int i = j; i <= k; i++)

#define dep(i, j, k) for(int i = k; i >= j; i--)

#define INF 0x3f3f3f3f

#define inf 0x3f3f3f3f3f3f3f3f

#define mem(i, j) memset(i, j, sizeof(i))

#define pb push_back

using namespace std;

const int N = , mod = ;

struct mat {

    LL a[N][N];

    mat() { mem(a, ); }

};

struct Trie {

    int ch[N][], tot, metch[N], Fail[N];

    void init() {

        mem(ch[], ); tot = ; metch[] = ;

    }

    int get(char Q) {

        if(Q == 'A') return ;

        else if(Q == 'C') return ;

        else if(Q == 'T') return ;

        return ;

    }

    void join(char s[]) {

        int now = ; int len = strlen(s);

        rep(i, , len - ) {

            int id = get(s[i]);

            if(!ch[now][id]) {

                mem(ch[tot], ); metch[tot] = ;

                ch[now][id] = tot++;

            }

            now = ch[now][id];

        }

        metch[now] = ;

    }

    void getFail() {

        queue<int> Q; while(!Q.empty()) Q.pop();

        rep(i, , ) {

            if(ch[][i]) {

                Q.push(ch[][i]); Fail[ch[][i]] = ;

            }

        }

        while(!Q.empty()) {

            int now = Q.front(); Q.pop();

            rep(i, , ) {

                int u = ch[now][i];

                if(u == ) ch[now][i] = ch[Fail[now]][i];

                else {

                    Q.push(u);

                    Fail[u] = ch[Fail[now]][i];

                    metch[u] |= metch[Fail[u]];

                }

            }

        }

    }

    mat getMat() {

        mat A;

        rep(i, , tot - ) {

            if(metch[i]) continue;

            rep(j, , ) {

                if(!metch[ch[i][j]]) A.a[i][ch[i][j]]++;

            }

        }

        return A;

    }

};

Trie AC;

char b[];

mat mul(mat A, mat B, int n) {

    mat C;

    rep(i, , n) {

        rep(j, , n) {

            rep(k, , n) {

                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;

            }

        }

    }

    return C;

}

mat ksm(mat A, int B, int n) {

    mat res; rep(i, , n) res.a[i][i] = ;

    while(B) {

        if(B & ) res = mul(res, A, n);

        A = mul(A, A, n); B >>= ;

    }

    return res;

}

int main() {

    int n, m;

    while(~scanf("%d %d", &m, &n)) {

        AC.init();

        rep(i, , m) {

            scanf("%s", b); AC.join(b);

        }

        AC.getFail();

        mat A; A = AC.getMat();

        mat ans = ksm(A, n, AC.tot - );

        LL res = 0LL;

        rep(i, , AC.tot - ) {

            res = (res + ans.a[][i]) % mod;

        }

        printf("%lld\n", res);

    }

    return ;

}

巴特西

POJ 2778 DNA Sequence (矩阵快速幂 + AC自动鸡)

最新文章

热门文章