HDU 2825 Wireless Password

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;
}