bzoj1559: [JSOI2009]密码

题解

构造长度为n包含所有模式串的的串，求方案数
构造AC自动机的trie图
对于模式串可以装压dp
设dp[i][j][s]表示位于字符串第i位,位于trie图上的第j个节点，状态为s方案数
转移边为trie图
考虑ans<=42的情况，若字符串的某一个位不属于n个字符串中的任何一个
则至少存在52（2 * 26）种方案。那么答案就是可行串组合直接拼，爆搜
卡内存能信？

代码

/*
构造长度为n包含所有模式串的的串，求方案数 
构造AC自动机的trie图 
对于模式串可以装压dp 
设dp[i][j][s]表示位于字符串第i位,位于trie图上的第j个节点，状态为s方案数 
转移边为trie图  
考虑ans<=42的情况，若字符串的某一个位不属于n个字符串中的任何一个
则至少存在52（2 * 26）种方案。那么答案就是可行  
*/
#include<queue> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#define LL long long
inline int read() { 
    int x = 0,f = 1;char c = getchar(); 
    while(c < '0'||c > '9')c = getchar(); 
    while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 
#define LL long long 
const int maxn = 57; 
const int maxNode = 137; 
char a[maxn][maxn],A[maxn][maxn]; 
int len[maxn];  
int l,m,n;
LL dp[maxn][maxNode][1100 + 7];int sz,bor[maxn][maxn]; 
int ch[maxNode][31],Snum[maxNode],fail[maxNode]; 
int border(int x,int y) { //维护一串前与一串后的相同部分，方便搜索 
    for(int i = std::min(len[x],len[y]);i >= 0;-- i) { 
        bool flag = false; 
        for(int j = 1;j <= i;++ j) 
            if(a[x][len[x] - i + j] != a[y][j]) { 
                flag = true;break;  
            }  
        if(!flag) return i;  
    } 
}  
void insert(int x) { 
    int now = 0; 
    for(int i = 1;i <= len[x]; ++ i) { 
        int s = a[x][i] - 'a'; 
        if(!ch[now][s]) ch[now][s] = ++ sz; 
        now = ch[now][s]; 
    } 
    Snum[now] = (1 << (x - 1)); 
} 
std::queue<int>que; 
void getfail() { 
    for(int i = 0;i <= 25;++ i) if(ch[0][i])que.push(ch[0][i]); 
    while(!que.empty()) {
        int now = que.front();que.pop();  
        for(int i = 0;i <= 25;++ i) { 
            if(ch[now][i]) fail[ch[now][i]] = ch[fail[now]][i],que.push(ch[now][i]);
            else ch[now][i] = ch[fail[now]][i]; // 
        } 
    }
} 
int del[maxn]; 
bool check(int x,int y) { 
    for(int i = 0;i < len[y] - len[x] + 1;++ i) { 
        int j = 1; 
        for(;j <= len[x];j ++ )if(a[x][j] != a[y][i + j]) break; 
        if(j == len[x] + 1) return true; 
    } 
    return false; 
} 
void unique() { 
    for(int i = 1;i <= n;++ i) for(int j = 1;j <= n;++ j) 	
        if(len[j] > len[i] && !del[j] && !del[i] &&check(i,j)) del[i] = 1,m --;
    for(int i = 1;i <= n;++ i) 
        for(int j = 1;j <= n;++ j) 
            bor[i][j] = border(i,j); 
} 
int Atot = 0,Gtot = 0,g[maxn]; 
bool vis[maxn]; 
void dfs(int x) { 
    if(x > m) { 
        Atot ++; int t = 0; 
        for(int i = 1;i <= Gtot;++ i) 
            for(int j = bor[g[i - 1]][g[i]] + 1;j <= len[g[i]];++ j) 
                A[Atot][++ t] = a[g[i]][j]; 
        if(t != l) Atot --;
        return; 
    } 
    for(int i = 1;i <= n;i ++) {  
        if(!del[i] && !vis[i]) { 
            vis[i] = 1; g[++ Gtot] = i;  
            dfs(x + 1);  
            vis[i] = 0;Gtot --; 
        }
    } 
} 
bool cmp(int x,int y) { 
    for(int i = 1;i <= l;++ i) if(A[x][i] != A[y][i]) return A[x][i] < A[y][i]; return false;
} 
int rk[maxn]; 
void solve() { 
    dp[0][0][0] = 1; 
    for(int i = 1;i <= l;++ i) { 
        for(int j = 0;j <= sz;++ j)  
            for(int s = 0;s <= (1 << n) - 1;++ s) 
                if(dp[i - 1][j][s])  
                    for(int x,ss,l = 0;l <= 25;++ l) { 
                        x = ch[j][l]; ss = s;
                        if(Snum[x])ss |= Snum[x];  
                        dp[i][x][ss] += dp[i - 1][j][s]; 
                    } 
    } 
    LL ans = 0,s = 0; 
    for(int i = 1;i <= n;++ i) if(!del[i])s += 1 << (i - 1); 
    for(int i = 0;i <= sz;++ i)ans += dp[l][i][s]; 
    printf("%lld
",ans); 
    if(ans <= 42) {
        dfs(1); for(int i = 1;i <= Atot; ++ i)rk[i] = i; 
        std::sort(rk + 1,rk + Atot + 1,cmp); 
        for(int i = 1;i <= Atot;++ i) { 
            for(int j = 1;j <= l;++ j)printf("%c",A[rk[i]][j]); 
            puts(""); 
        }
    } 
} 

int main() { 
    l = read(),m = read(),n = m; 
    for(int i = 1;i <= m;++ i) 
        scanf("%s",a[i] + 1) , len[i] = strlen(a[i] + 1);  	
    unique(); 
    for(int i = 1;i <= n;++ i) if(!del[i]) insert(i); 
    getfail(); 	
    solve(); 
    return 0;
}