题解 P4045 【[JSOI2009]密码】
皎月半洒花
2020-02-19 13:42:38
这里说一种跟另外两篇题解不一样的剪枝。
同时……这题大概也就是蓝~紫左右，这个黑实在太虚了。
观察题意，由 `good+day=gooday` 可知应该放在 $\rm AC$ 自动机上做，观察范围可知是状压。记 $f_{i,j,s}$ 表示匹配到串的第 $i$ 位，走到了自动机上的第 $j$ 个节点，当前已经拼完了集合 $s$ 中的模式串的方案数。那么转移自然很简单。值得提一句的的是，由于本身 $\rm AC$ 自动机存在路径压缩，所以是 `认子不认父` 的结构，只能刷表。
之后考虑输出方案。考虑一种无脑的输出方式。由于很容易 $dfs$ 出每个状态 $(i,j,k)$ 是否可以转移到终点，所以不需要考虑 $42$ 的限制，剪完枝直接输出即可。
同时，只要在 $\rm AC$ 自动机上保证每次走最小的字母，就一定是字典序最优的方案。
```cpp
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 ;
}
```