HDU 2825 Wireless Password-AC自动机+DP

给m个单词，由这m个单词组成的一个新单词（两个单词可以重叠包含）长度为n，且新单词中包含的基本单词数目不少于k个。问这样的新单词共有多少个？

m很小，用二进制表示新单词中包含基本单词的情况。

用m个单词建立AC自动机，可以求出所有单词之间相互包含的情况，AC自动机的后缀特性（每个结点的失配边指向新结点，新节点到trie树根的字符串是当前节点字符串的后缀）。

动态规划：

f(i, j, k)：长度为i的单词，在trie树中第j个结点处，包含基本单词的情况为k（二进制），的总方案数。

转移方程：

在当前字符串后边再加上一个字母

f(i+1, u, k|val[u]) += f(i, j, k)

u是j结点的子结点（或者是失配边指向的结点），k|val[u]表示加上一个新字母后包含基本单词的情况。

#include 
#include 
#include 
#include 
using namespace std;
struct AC_Automata {
    #define N 102
    #define M 26
    int ch[N][M], val[N], last[N], f[N], sz;
    void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }
    int idx(char c) { return c-'a'; }

    void insert(char s[], int v) {
        int u = 0;
        for (int i=0; s[i]; i++) {
            int c = idx(s[i]);
            if (!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = 1< q;
        f[0] = 0;
        for (int c=0; c= p) ans = (ans + f[n][i][j]) % Mod;
    printf("%d\n", ans);
}
int main() {
    int n, m, k;
    char s[12];
    init();

    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        if (n == 0 && m == 0 && k == 0) break;
        ac.clear();

        for (int i=0; i