bzoj 1559 [JSOI2009]密码

内容

Description

Input

Output

Sample Input

10 2

hello

world

Sample Output

helloworld

worldhello

HINT

题解

输出方案太恶心了。

发现n很小，考虑状压。

首先对于所有串建个ac自动机。f[i][j][k]表示长度为i，ac自动机的j节点，当前串的状态为k（二进制），按照往儿子走的顺序转移下、

最后结果是f[len][1..sz][(1<< n)-1]求和

发现空间不够，第一维滚动一下。。

发现输出方案的答案是42。可以观察一下，对于所有s1+a..z+s2的这种组合，方案数肯定是大于42的（a..z可以换位置，还是合法的）

那么一开始就去掉所有串包含串的情况（子串），那么最后就是这些串的紧密全排列。（还要考虑一个串的后缀是另一个串的前缀的情况。。）

反正这个暴力非常难写。。hdu有个不输出方案的，实在懒得写就去搞那个吧。

（hdu2825，要求有至少k个串是子串，就是最后统计答案的时候判下二进制位数是不是多于k就好了。。这题我常数写崩了，被卡常，但是对拍没问题，就不往上放了。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 110
using namespace std;
long long n,m,sz,tot,root,ans,ch[N][26],is_end[N],fail[N],f[2][N][1<<12],len[N];
char s[25][N],a[45][27],c[27];
void insert(char s[],int t)
{
    int len=strlen(s),now=root;
    for (int i=0;i<len;now=ch[now][s[i]-'a'],i++)
        if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++sz;
    is_end[now]=1<<t-1;
}
void make_fail()
{
    queue<int>que;
    for (int i=0;i<26;i++)
        if (ch[root][i]) que.push(ch[root][i]);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        for (int i=0;i<26;i++)
            if (ch[now][i])
                is_end[ch[now][i]]|=is_end[ch[fail[now]][i]],
                fail[ch[now][i]]=ch[fail[now]][i],que.push(ch[now][i]);
            else
                ch[now][i]=ch[fail[now]][i];
    }
}
int rk[47],l,o; bool vis[11],del[11];
void dfs(int x,int u)
{
    if(x>o)
    {
        if(u!=l)
            return;
        ++tot;
        memcpy(a[tot],c,sizeof a[tot]);
        return;
    }
    for(int i=1;i<=n;++i)
        if(!vis[i] && !del[i])
        {
            vis[i]=1;
            int L=len[i],k;
            for(int j=max(u-L,0);j<u;++j)
            {
                for(k=0;k<L && k+j<u;++k)
                    if(s[i][k]!=c[j+k])
                        break;
                int temp=u;
                if(k==L || k+j==u)
                {
                    for(;k<L && temp<l;++k)
                        c[temp++]=s[i][k];
                    if(k==L)
                        dfs(x+1,temp);
                }
            }
            if(u+L<=l)
            {
                for(k=0;k<L;++k)
                    c[u+k]=s[i][k];
                dfs(x+1,u+L);
            }
            vis[i]=0;
        }
}
int comp(int x,int y)
{
    for(int i=0;i<l;++i)
        if(a[x][i]<a[y][i])
            return 1;
        else if(a[x][i]>a[y][i])
            return 0;
    return 0;
}
int find(int x,int y)
{
    for(int i=min(len[x],len[y]);~i;i--)
    {
        bool flag=0;
        for(int j=0;j<i;j++)
            if(s[x][len[x]-i+j]!=s[y][j])
            {
                flag=1;
                break;
            }
        if(!flag) return i;
    }
}
main()
{
    scanf("%d%d",&l,&n);
    for (int i=1;i<=n;i++)
        scanf("%s",s[i]),len[i]=strlen(s[i]);
    for (int i=1;i<=n;i++)
        if (!del[i])
            for (int j=1;j<=n;j++)
                if (i!=j)
                    if (find(i,j)==len[j])
                        del[j]=1;
    for (int i=1;i<=n;i++)
        if (!del[i])
            insert(s[i],i);
    make_fail();
    f[0][root][0]=1;
    int all=1<<n;
    for (int i=0;i<l;memset(f[i&1],0,sizeof f[i&1]),i++)
        for (int j=0;j<=sz;j++)
            for (int k=0;k<all;k++)
                if (f[i&1][j][k])
                    for (int l=0;l<26;l++)
                        f[i+1&1][ch[j][l]][k|is_end[ch[j][l]]]+=f[i&1][j][k];
    int te=0;
    for (int i=1;i<=n;i++)
        if (!del[i])
            te+=(1<<i-1),o++;
    for (int i=0;i<=sz;i++)
        ans+=f[l&1][i][te];
    printf("%lld\n",ans);
    if (ans<=42)
    {
        dfs(1,0);
        for (int i=1;i<=tot;i++)
            rk[i]=i;
        sort(rk+1,rk+1+tot,comp);
        for(int i=1;i<=tot;++i)
            printf("%s\n",a[rk[i]]);
    }
}