AC自动机+状压DP的入门题
虽然不是很好意思,但我的确是先看了kuangbin的代码再敲的。
从AC自动机构建矩阵开始起的出现的那个结点状态,在之后做题中越來越显著。
因为AC自动机本身也没多少地方可以改了,这是一个成熟的算法。而考研我们的运用就只能在理解熟悉它的状态,并运用它的状态。
关于状态应用最明显的就是DP了。

这题之后尽量不看题解……

说了一堆废话,下面放题解。

题意:
有一个长度为 n 的密码,给你一个 m 个字符串的集合。告诉你这个密码必定会包含这集合中的 k 个。
问密码的种数。

思路:
这道题应该是给出一个状态就很好理解了。
开一个三维数组,记 dp\left[ i \right] \left[ j \right] \left[ k \right] 为长度为 i ,在第j 个结点,含有字符串数量的状态为 k 的可构字符串数量。
每次在AC自动机上跑的时候更新一下状态,最后再将包含字符串数量大于等于 k 的状态数量累加即可。

相信我,真的是入门级的……

AC Code

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

using namespace std;

typedef unsigned long long ull;

const int mod = 20090717;
const int max_n = 110;
const int max_c = 26;
char buf[max_n];

int n, m, k;

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] = -1;
        end[size++] = 0;
        return size - 1;
    }

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

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

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

    int dp[max_c + 2][max_n][1 << 10];

    int solve()
    {
        int ans = 0, ni, nj, ns;
        memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < size; j++)
                for (int state = 0; state < (1 << m); state++)
                    if (dp[i][j][state]) {
                        for (int x = 0; x < max_c; x++) {
                            ni = i + 1, nj = next[j][x], ns = state | end[nj];
                            dp[ni][nj][ns] = (dp[ni][nj][ns] + dp[i][j][state]) % mod;
                        }
                    }
        for (int state = 0; state < (1 << m); state++) {
            if (__builtin_popcount(state) < k)
                continue;
            for (int i = 0; i < size; i++)
                ans = (ans + dp[n][i][state]) % mod;
        }
        return ans;
    }
} aho;

int main()
{
    while (scanf("%d %d %d", &n, &m, &k) != EOF) {
        if (n == 0 && m == 0 && k == 0)
            break;
        aho.init();
        for (int i = 0; i < m; i++) {
            scanf("%s", buf);
            aho.insert(buf, i);
        }
        aho.build();
        printf("%d\n", aho.solve());
    }
    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…