又忘了计数题算补集这回事了
感觉trie的好处就是一个节点代表一个串啊?
又及: wdnmd真都一个错误犯三次啊
懵逼的 题目
BZOJ
扯淡的 题解
一开始想着是在trie上遍历然后算贡献云云
然后发现这个容斥似乎有点反人类
然后抄题解第一句就是取补集
Emmmmm...
f[i][j]代表当前生成第i位,
匹配到了自动机的第j个点上 没有出现过已知单词的方案数
然后随便写写就好了
沙茶的 代码
我构建fail的时候又㕛叒叕忘了把下一层push进去了
这是有多大仇...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#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