Description

Input

Output

Sample Input
10 2
hello
world

Sample Output
2
helloworld
worldhello

HINT

一看\(n\)这么小就要状压……我们设\(f[i][j][s]\)表示长度为\(i\)，AC自动机上节点为\(j\)，出现的字符串的状态为\(s\)的方案数，然后直接枚举转移即可

然后难点就在于如何输出方案

首先42这数字非常妙(生命、宇宙以及任何事情的终极答案)

如果存在一个字符可以任意选的情况，那么答案至少也要为2*26=52，所以这种情况是不存在的

所以就直接爆搜，\(O(n!)\)搜索，然后中间疯狂剪枝就好

/*program from Wolfycz*/#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){ int x=0,f=1;char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}inline int read(){ int x=0,f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0');}const int N=1e2;struct S1{ int trie[N+10][26],fail[N+10],End[N+10]; int root,tot; void insert(char *s,int ID){ int len=strlen(s),p=root; for (int i=0;i<len;i++){ if (!trie[p][s[i]-'a']) trie[p][s[i]-'a']=++tot; p=trie[p][s[i]-'a']; } End[p]=1<<ID; } void make_fail(){ static int h[N+10]; int head=1,tail=0; for (int i=0;i<26;i++) if (trie[root][i]) h[++tail]=trie[root][i]; for (;head<=tail;head++){ int Now=h[head]; End[Now]|=End[fail[Now]]; for (int i=0;i<26;i++){ if (trie[Now][i]){ int son=trie[Now][i]; fail[son]=trie[fail[Now]][i]; h[++tail]=son; }else trie[Now][i]=trie[fail[Now]][i]; } } }}AC;//Aho-Corasick automatonint work(char *s,char *t){ int lens=strlen(s),lent=strlen(t),Ans=0; for (int i=0;i<lens;i++){ int res=0,x=i,y=0; while (x<lens&&y<lent){ if (s[x]!=t[y]) break; res++,x++,y++; } if (x!=lens) continue; Ans=max(Ans,res); } return Ans;}ll f[30][N+10][(1<<10)+10];int pos[15],Len[15],g[15][15],L,n,cnt;bool vis[15];char s[15][15];struct S2{char s[N+10];}A[50];bool operator <(const S2 &x,const S2 &y){ int lenx=strlen(x.s),leny=strlen(y.s); if (lenx!=leny) return lenx<leny; for (int i=0;i<lenx;i++) if (x.s[i]!=y.s[i]) return x.s[i]<y.s[i]; return 0;}void dfs(int x,int len){ if (len>L) return; if (x==n){ static char T[N+10]; for (int i=0;i<Len[pos[0]];i++) T[i]=s[pos[0]][i]; int L=Len[pos[0]]; for (int i=1;i<n;i++){ for (int j=0;j<Len[pos[i]];j++) T[j+L-g[pos[i-1]][pos[i]]]=s[pos[i]][j]; L+=Len[pos[i]]-g[pos[i-1]][pos[i]]; } memcpy(A[cnt++].s,T,sizeof(T)); return; } for (int i=0,tmp;i<n;i++){ if (!vis[i]){ pos[x]=i,vis[i]=1; tmp=len+Len[i]-(x?g[pos[x-1]][i]:0); dfs(x+1,tmp); pos[x]=0,vis[i]=0; } }}int main(){ L=read(),n=read(); for (int i=0;i<n;i++){ scanf("%s",s[i]); Len[i]=strlen(s[i]); AC.insert(s[i],i); } AC.make_fail(); f[0][0][0]=1; for (int i=0;i<L;i++){ for (int j=0;j<=AC.tot;j++){ for (int s=0;s<1<<n;s++){ if (!f[i][j][s]) continue; for (int k=0;k<26;k++){ int son=AC.trie[j][k]; f[i+1][son][s|AC.End[son]]+=f[i][j][s]; } } } } ll Ans=0; for (int i=0;i<=AC.tot;i++) Ans+=f[L][i][(1<<n)-1]; printf("%lld\n",Ans); if (Ans>42) return 0; for (int i=0;i<n;i++) for (int j=0;j<n;j++) g[i][j]=work(s[i],s[j]); dfs(0,0); sort(A,A+cnt); for (int i=0;i<cnt;i++) printf("%s\n",A[i].s); return 0;}