又忘了计数题算补集这回事了

感觉trie的好处就是一个节点代表一个串啊?

又及: wdnmd真都一个错误犯三次啊

懵逼的 题目

BZOJ

扯淡的 题解

一开始想着是在trie上遍历然后算贡献云云 然后发现这个容斥似乎有点反人类

然后抄题解第一句就是取补集

Emmmmm…

f[i][j]代表当前生成第i位, 匹配到了自动机的第j个点上 没有出现过已知单词的方案数

然后随便写写就好了

沙茶的 代码

我构建fail的时候又㕛叒叕忘了把下一层push进去了

这是有多大仇…

/**************************************************************
    Problem: 1030
    User: Cansult
    Language: C++
    Result: Accepted
    Time:184 ms
    Memory:4460 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (6000 + 5)
#define MAXM (100 + 5)
#define MAXC (26)
#define Aufun (10007)
using namespace std;
struct node {
    int son[MAXC], fail;
    vector<int> bh;
} b[MAXN];
int n, m, f[MAXM][MAXN], cntb, ans;
char s[MAXM];
void init() {
    queue<int> q;
    for (int i = 0; i < MAXC; i++) if (b[0].son[i]) q.push(b[0].son[i]);
    while (!q.empty()) {
        int dq = q.front();
        q.pop();
        for (int i = 0; i < MAXC; i++) 
            if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
            else b[dq].son[i] = b[b[dq].fail].son[i];
    }
}
int mpow(int a, int b) {
    int re = 1;
    for (int i = 1; i <= b; i++) 
        re *= a, re %= Aufun;
    return re;
}
bool pd(int dq) {
    for (int i = dq; i; i = b[i].fail)
        if (b[i].bh.size())
            return false;
    return true;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int dqn = strlen(s), dq = 0;
        for (int j = 0; j < dqn; j++) {
            if (!b[dq].son[s[j] - 'A']) b[dq].son[s[j] - 'A'] = ++cntb;
            dq = b[dq].son[s[j] - 'A'];
        }
        b[dq].bh.push_back(i);
    }
    init();
    f[0][0] = 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= cntb; j++)
            if (f[i][j])
                for (int k = 0; k < MAXC; k++)
                    if (pd(b[j].son[k]))
                        f[i + 1][b[j].son[k]] += f[i][j], f[i + 1][b[j].son[k]] %= Aufun;
    for (int i = 0; i <= cntb; i++) ans += f[m][i], ans %= Aufun;
    printf("%d", ((mpow(26, m) - ans) % Aufun + Aufun) % Aufun);
    return 0;
}

By 准备退役旅游的 Cansult