【题解】bzoj1559 [JSOI2009]密码

给定长度为 $L$ 的 $m$ 个子串,要求拼出一个长度为 $L$ 的长串使之包含所有的子串。

如果方案数 $\leq42$ 则输出全部方案,否则只输出方案数。

$L\leq 25,m\leq 10$。

…这题大概也就是蓝~紫左右,这个黑实在太虚了。

但这不影响我还是不太会233

观察题意,由 good+day=gooday 可知应该放在 $\rm AC$ 自动机上做,因为存在重合。观察范围可知是状压。于是考虑在 $\rm$ AC 自动机上 $dp$。

记 $f_{i,j,s}$ 表示匹配到串的第 $i$ 位,走到了自动机上的第 $j$ 个节点,当前已经拼完了集合 $s$ 中的模式串的方案数。转移的话就考虑直接枚举当前状态的所有子状态,暴力转移即可(用来计数的状压 $dp$ 还能怎么转移啊喂)。值得提一句的的是,由于本身 $\rm AC$ 自动机存在路径压缩,所以是 认子不认父 的结构,只能刷表而不能填表。

之后考虑输出方案。发现如果直接搜 $\rm AC$ 自动机上的每个方案十分暴力,于是考虑加一个可行性剪枝。即由于很容易 $dfs$ 出每个状态 $(i,j,s)$ 是否可以转移到终点,所以不需要考虑 $42$ 的限制,预处理一个 $g_{i,j,s}$是否可以拼出最终状态,剪完枝直接输出即可。

同时,只要在 $\rm AC$ 自动机上保证每次走最小的字母,就一定是字典序最优的方案。

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
int o ;
LL ans ;
int n, m ;
int t[N] ;
char s[N] ;
LL f[N][W][Z] ;
bool g[N][W][Z] ;
bool v[N][W][Z] ;

struct ACAM{
int size ;
int _ed[W] ;
int fail[W] ;
queue <int> q ;
int trans[W][26] ;
void Ins(char *t, int num){
int rt = 0, len ;
len = strlen(t + 1) ;
for (int x, i = 1 ; i <= len ; ++ i){
x = t[i] - 'a' ;
if (!trans[rt][x])
trans[rt][x] = ++ size ;
rt = trans[rt][x] ;
}
_ed[rt] |= (1 << num) ;
}
void build(){
for (int i = 0 ; i < 26 ; ++ i)
if (trans[0][i]) q.push(trans[0][i]) ;
while (!q.empty()){
int x = q.front() ;
q.pop() ; _ed[x] |= _ed[fail[x]] ;
for (int i = 0 ; i < 26 ; ++ i){
if (!trans[x][i]) trans[x][i] = trans[fail[x]][i] ;
else fail[trans[x][i]] = trans[fail[x]][i], q.push(trans[x][i]) ;
}
}
}
}S ;
bool search(int x, int y, int z){
if (x == n){
v[x][y][z] = 1 ;
return g[x][y][z] = (bool)(z == o) ;
}
bool p = 0 ;
if (v[x][y][z])
return g[x][y][z] ;
else v[x][y][z] = 1 ;
for (int i = 0 ; i < 26 ; ++ i)
p |= search(x + 1, S.trans[y][i], z | S._ed[S.trans[y][i]]) ;
return g[x][y][z] = p ;
}
void output(int x, int y, int z){
if (!g[x][y][z]) return ;
if (x == n){
for (int i = 1 ; i <= n ; ++ i)
printf("%c", t[i] + 'a') ;
return puts(""), void() ;
}
for (int i = 0 ; i < 26 ; ++ i)
t[x + 1] = i, output(x + 1, S.trans[y][i], z | S._ed[S.trans[y][i]]) ;
}
int main(){
cin >> n >> m ; S.size = 0 ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%s", s + 1), S.Ins(s, i - 1) ;
S.build() ; f[0][0][0] = 1 ; o = (1 << m) - 1 ;
for (int i = 0 ; i < n ; ++ i)
for (int j = 0 ; j <= S.size ; ++ j)
for (int k = 0 ; k <= o ; ++ k)
if (f[i][j][k])
for (int l = 0 ; l < 26 ; ++ l)
f[i + 1][S.trans[j][l]][k | S._ed[S.trans[j][l]]] += f[i][j][k] ;
for (int i = 0 ; i <= S.size ; ++ i) ans += f[n][i][o] ;
if (ans > 42) return printf("%lld\n", ans), 0 ;
else return cout << ans << '\n', search(0, 0, 0), output(0, 0, 0), 0 ;
}