题解 P4045 【[JSOI2009]密码】

· · 题解

解题思路：

这道题目...有点诡...

首先显然是AC自动机+状压DP，我们设f[i][j][S]表示长度为i，当前在Trie树上的j号节点，观察到的字符串的使用情况为S的方案树，然后转移就好了。

现在主要的问题就是怎么输出方案。

我们注意到这些被观察到的字符串可能会存在一个字符串的后缀是另一个字符串的前缀的情况，这就可能会给我们的方案构造加大难度。

但是我们仔细思考一下，如果存在一个字符是可以任意选取的话，那么它给方案数的最小的贡献就是2 \times 26=52，就超出了我们需要给出具体方案的范围，因此，我们可以直接暴搜来得到方案。

然后还需要注意一点，那就是我们需要预处理出来一个字符串是另一个字符串的子串的情况，然后在搜索的过程中判一下。

代码不是很好看了...

Code：

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxl=26;
const int maxn=110;
bool vis[maxn],del[maxn];
char s[20][21],ans[50][maxn];ll f[maxl][maxn][(1<<10)+1];
int L,n,m,tot,cnt,now,pos[maxn],len[maxn],ed[maxn],fail[maxn],trie[maxn][maxl],nxt[maxl][maxl];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
struct AC_automaton{
    void insert(char *s,int num){
        int p=0,len=strlen(s);
        for(int i=0;i<len;i++){yixia
            int ch=s[i]-'a';
            if(!trie[p][ch])trie[p][ch]=++tot;
            p=trie[p][ch];
        }ed[p]=1<<num;
    }
    void make_fail(){
        queue<int >q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++)if(trie[0][i])q.push(trie[0][i]);
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(trie[x][i]){
                    fail[trie[x][i]]=trie[fail[x]][i];
                    q.push(trie[x][i]);
                }else trie[x][i]=trie[fail[x]][i];
            }ed[x]|=ed[fail[x]];
        }
    }
}AC;
bool cmp(int x,int y){for(int i=0;i<L;i++)if(ans[x][i]!=ans[y][i])return ans[x][i]<ans[y][i];return 0;}
int get_nxt(int x,int y){
    int ans=0;
    for(int i=1;i<=min(len[x],len[y]);i++){
        int flag=1,k=0;
        for(int j=len[x]-i;j<len[x]&&k<i;j++,k++)if(s[x][j]!=s[y][k])flag=0;
        if(flag)ans=i;
    }return ans;
}yixia
bool check(int x,int y){
    int flag=0;
    for(int i=0,k;i+len[x]<=len[y];i++,k=1){
        for(int j=0;j<len[x];++j)if(s[x][j]!=s[y][i+j])k=0;
        flag|=k;
    }return flag;
}
char tmp[maxn];
int d;
void dfs(int l,int pst){
    if(l<L){
        for(int i=0,k=0;i<n;i++){
            if(~pst)k=nxt[pst][i];
            for(int j=k+1;j<=len[i];j++)if(!vis[i]&&!del[i])tmp[l+j-k]=s[i][j-1];
            if(!del[i]&&!vis[i])vis[i]=1,d++,dfs(l+len[i]-k,i),vis[i]=0,d--;k=0;
        }return ;
    }if(l==L&&d==m){cnt++;for(int i=1;i<=L;++i)ans[cnt][i]=tmp[i];}
}
int main(){
    L=read();m=n=read();f[0][0][0]=1;ll ret=0;
    for(int i=0;i<n;i++)scanf("%s",s[i]),len[i]=strlen(s[i]),AC.insert(s[i],i);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j)nxt[i][j]=get_nxt(i,j);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j)del[i]=(check(i,j)?:del[i]);
    for(int i=0;i<n;i++)if(del[i])m--;
    AC.make_fail();
    for(int i=1;i<=L;i++)
        for(int j=0;j<=tot;j++)
            for(int l=0;l<(1<<n);l++)
                if(f[i-1][j][l])
                    for(int ch=0;ch<26;ch++)
                        f[i][trie[j][ch]][l|ed[trie[j][ch]]]+=f[i-1][j][l];
    for(int i=0;i<=tot;i++)ret+=f[L][i][(1<<n)-1];write(ret);
    if(ret<=42){
        dfs(0,-1);
        for(int i=1;i<=cnt;i++)pos[i]=i;
        sort(pos+1,pos+cnt+1,cmp);
        for(int i=1;i<=cnt;i++)printf("%s\n",ans[pos[i]]+1);
    }
    return 0;
}