做的第一道AC自动机非模板题,感觉真的是神了。
一些AC自动机的性质自己完全不知道……

废话不多说,直接上题解。

题意:
给你n种病毒,要你求出长度为 m 的不含这 n 中病毒的数量。

思路:
这道题可以转化成图论解决,当然只能是思路而已
对于AC自动机上的每一个结点,他都可以看成是一个字符串的一部分前缀,也可以认为是一个字符串的一部分后缀。
作为一部分后缀,如果我们在一直不含病毒串的同时,长度达到了要求,我们就可以将其认为是一种可行方案。

解题关键 : 离散数学上的矩阵阶乘定理

构建一个矩阵,矩阵值 Mat\left[ i , j \right] 代表的是 ij 的边数。对其求 k 次幂,所得新矩阵为 Mat\left[ i , j \right] 代表的是 ij 长度为 k 的路径数量。

应用到这题来,其实我们对于AC自动机上的每一个结点,我们只要求出它的邻接矩阵,再通过矩阵快速幂,累加和,就是我们要的答案。

下面是求邻接矩阵的方法与说明

作为一部分前缀,如果这个结点它选择走向了另一个结点从而形成了我们的病毒串,我们认为这是不可行的。
这是很显然的,比如说有病毒串 ATC ,而我 当前结点及其它的所有前结点构成的字符串为 *****AT,如果这时候我们走向了 T 的孩子 C结点 ,这时候就构成了病毒串,我这里暂时称它为病毒结点。

另一个不允许我们跑动的状态是跑 fail 指针的时候。当我们已知我们的fail指针是指向的病毒结点的时候,我们自然不能通过这个fail指针跑向病毒结点。并且我们的当前结点也成为了病毒结点。因为他们的后缀相同。
举个例子就比如 R -> ATC ,T指向了 R -> T ,其中 T 为病毒结点,那么 R -> AT 中的 T 也成为了病毒结点。

初学者 当然包括我啦 有个很自然的困惑就是这样的情况 R -> ATCT , R -> T 病毒结点的时候,R -> ATCT 的第一个 T 能不能有效的被 “感染” 为病毒结点。
答案当然是显然的,因为我们的遍历过程是宽度优先。如果是深度优先,恐怕不行。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef long long ll;
const int max_n = 120;
const int max_c = 4;
const int mod = 1e5;
char buf[max_n];

int getChar(char& ch)
{
    if (ch == 'A')
        return 0;
    else if (ch == 'C')
        return 1;
    else if (ch == 'G')
        return 2;
    return 3;
}

struct Matrix {
    int mat[max_n][max_n], n;
    Matrix(int _n = 1)
    {
        n = _n;
        memset(mat, 0, sizeof mat);
    }
    Matrix operator*(const Matrix& a) const
    {
        Matrix tmp(n);
        for (int i = 1; i < n; ++i)
            for (int j = 1; j < n; ++j)
                if (mat[i][j])
                    for (int k = 1; k < n; ++k)
                        tmp.mat[i][k] = (tmp.mat[i][k] + 1LL * mat[i][j] * a.mat[j][k] % mod) % mod;
        return tmp;
    }
};

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    inline void insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = getChar(str[i]);
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            if (end[fail[now]])
                end[now] = 1;
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    Matrix getMatrix()
    {
        Matrix a(size);
        for (int i = 1; i < size; i++)
            for (int j = 0; j < 4; j++)
                if (!end[next[i][j]])
                    a.mat[i][next[i][j]]++;
        return a;
    }
} aho;

Matrix Pow(Matrix a, ll m)
{
    Matrix ans(a.n);
    for (int i = 1; i < a.n; i++)
        ans.mat[i][i] = 1;
    while (m) {
        if (m & 1)
            ans = ans * a;
        a = a * a;
        m >>= 1;
    }
    return ans;
}

int main()
{
    int n;
    ll m;
    while (scanf("%d %lld", &n, &m) != EOF) {
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        Matrix a = aho.getMatrix();
        a = Pow(a, m);
        int res = 0;
        for (int i = 1; i < a.n; i++)
            res = (res + a.mat[1][i]) % mod;
        printf("%d\n", res);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

AC自动机

HDU 6138 Fleet of the Eternal Throne

昨天多校的AC自动机入门题…… 为什么我还要写AC自动机入门题呢,因为 Read more…

AC自动机

HDU 6096 String

AC自动机好题,恐怕出题人都完全没有想到是AC自动机。 队友在写这题的 Read more…

AC自动机

HDU 2457 DNA repair

好题。但kuangbin说这道题已经是很简单的DP了。 首先kuang Read more…