题解 P4045 【[JSOI2009]密码】

· · 题解

这里说一种跟另外两篇题解不一样的剪枝。

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

观察题意，由 good+day=gooday 可知应该放在 \rm AC 自动机上做，观察范围可知是状压。记 f_{i,j,s} 表示匹配到串的第 i 位，走到了自动机上的第 j 个节点，当前已经拼完了集合 s 中的模式串的方案数。那么转移自然很简单。值得提一句的的是，由于本身 \rm AC 自动机存在路径压缩，所以是 认子不认父 的结构，只能刷表。

之后考虑输出方案。考虑一种无脑的输出方式。由于很容易 dfs 出每个状态 (i,j,k) 是否可以转移到终点，所以不需要考虑 42 的限制，剪完枝直接输出即可。

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

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 ;
}