「BJOI2017」魔法咒语

发表于

题目大意

给定n个基本词汇和m个禁忌词汇，求用这n个串组成长度l的串的方案数

数据范围

data

算法讨论

AC自动机DP

$状态:f[i][j]表示已经组成了长度为i的串，停留在自动机上第j个点的方案数$

$转移:f[i + len[k]][run(j,len[k])] += f[i][j]$

这样可以过前6组数据，注意AC自动机上每个点的$flag$会影响$fail$子树的$flag$

对于后面四组数据，DP就不行了，可以考虑矩阵乘法

对于词汇长度为1的，直接按照自动机的转移建矩阵，对于长度为2的，就扩大矩阵，记录一下前一次的状态就好了

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 105;
typedef long long ll;
const ll mod = 1e9 + 7;

char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline int _R() {
	int d; char t;
	while (t = GC, t < '0' || t > '9') ;
	d = t - '0';
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return d;
}
inline int _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
	return t - c;
}

int n, m, l, len[55];
char str[51][N];

int root, tot, Son[N][26], fail[N], flag[N];
void insert(char *c) {
	int t, p = root;
	for (char *it = c; *it; it ++) {
		t = (*it) - 'a';
		if (!Son[p][t]) Son[p][t] = ++ tot;
		p = Son[p][t];
	}
	flag[p] = 1;
}
void Build() {
	queue<int> q;
	for (int i = 0; i < 26; i ++)
		if (Son[root][i]) fail[Son[root][i]] = root, q.push(Son[root][i]);
		else Son[root][i] = root;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = 0; i < 26; i ++){
			int u = Son[x][i];
			if (u) {
				fail[u] = Son[fail[x]][i];
				flag[u] |= flag[fail[u]];
				q.push(u);
			}
			else Son[x][i] = Son[fail[x]][i];
		}
	}
}
int nxt_node(int p, char *c) {
	for (; *c; c ++) {
		int t = (*c) - 'a';
		while (p && !Son[p][t]) p = fail[p];
		p = Son[p][t];
		if (!p) p = root;
		if (flag[p]) return 0;
	}
	return p;
}

namespace deep_dark {
	ll f[N][N];
	void fantasy() {
		int i, j, k, u;
		f[0][1] = 1;
		for (i = 0; i < l; i ++)
			for (j = 1; j <= n; j ++) if (i + len[j] <= l)
				for (k = 1; k <= tot; k ++) if (!flag[k]) {
					u = nxt_node(k, str[j]);
					if (u) f[i + len[j]][u] = (f[i + len[j]][u] + f[i][k]) % mod;
				}
		ll ans = 0;
		for (i = 1; i <= tot; i ++) ans = (ans + f[l][i]) % mod;
		printf("%lld\n", ans);
	}
}

namespace boy {
	typedef long long Matrix[N << 1][N << 1];

	int T;
	Matrix src;
	void MMul(Matrix a, Matrix b) {
		int i, j, k;
		for (i = 1; i <= T; i ++)
			for (j = 1; j <= T; j ++) src[i][j] = 0;
		for (i = 1; i <= T; i ++)
			for (j = 1; j <= T; j ++)
				for (k = 1; k <= T; k ++)
					src[i][j] = (src[i][j] + a[i][k] * b[k][j] % mod) % mod;
		for (i = 1; i <= T; i ++)
			for (j = 1; j <= T; j ++)
				a[i][j] = src[i][j];
	}
	Matrix tr, st, ans;
	void KSM() {
		for (int i = 1; i <= T; i ++) ans[i][i] = 1;
		for (; l; l >>= 1, MMul(tr, tr))
			if (l & 1) MMul(ans, tr);
	}
	void next_door() {
		int i, j, k, flagt = 1;
		T = tot << 1;
		for (i = 1; i <= tot; i ++) if (!flag[i])
			for (j = 1; j <= n; j ++) {
				k = nxt_node(i, str[j]);
				if (!k) continue;
				if (len[j] == 1) tr[i][k] ++;
				else tr[i + tot][k] ++, flagt = 0;
			}
		for (i = 1; i <= tot; i ++)
			tr[i][i + tot] = 1;
		if (flagt) T >>= 1;
		st[1][1] = 1;
		KSM();
		MMul(st, ans);
		ll answ = 0;
		for (i = 1; i <= tot; i ++) answ = (answ + st[1][i]) % mod;
		printf("%lld\n", answ);
	}
}
int main () {
	int i, j, k;
	n = _R(), m = _R(), l = _R();
	root = tot = 1;
	for (i = 1; i <= n; i ++) len[i] = _S(str[i]);
	for (i = 1; i <= m; i ++) {
		_S(str[0]);
		insert(str[0]);
	}
	Build();
	if (l <= 100) deep_dark :: fantasy();
	else boy :: next_door();
}