题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1559
分析：
这个题意真的是很**啊！！！直接说每一个字符串至少出现一次不就好了吗......一开始理解错了ORZ
观察发现这个东西是字符串相关，并且有多个模板串，所有串的长度短并且串的数量不多，最多10个，因此大概可以想到一个AC自动机上面的状压。
首先把被包含的单词去掉，它们对决策不影响，这样在写方程的时候就可以不考虑last了。
令f(i,l,s)表示当位于AC自动机的状态i时，已经生成了l个字符，所有单词的出现情况为s的方案数。
f(i,l,s) = sum{ f(j,l-1,s) | j->i } + sum{ f(j,l-1,s-{i}) | j->i },s包含单词i。刷表实现即可。
ans=sum{ f(i,L,all) | 0<=i<=np }
当答案小于等于42的时候直接在状态转移图上面倒着搜就可以了，看那些状态对当前状态有贡献，一路搜下去，最后把所有串排个序即可。
时间复杂度O(L*N*len*2^N)，最后的方案搜索因为方案很少几乎不要时间。
get套路之：字符串算法构造状态辅助字符串有关dp！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
typedef long long LL; int L,N,cnt,len;
char S[][],path[];
LL f[][][];
bool vis[];
struct mstring{
static const int maxn=;
char str[maxn];
mstring(){ memset(str,,sizeof(str)); }
friend bool operator < (mstring a,mstring b){
int n=min(strlen(a.str),strlen(b.str));
for(int i=;i<n;i++)
if(a.str[i]!=b.str[i]) return a.str[i]<b.str[i];
return strlen(a.str)<strlen(b.str);
}
}ss[];
struct Aho_Corasick_Automaton{
static const int maxn=;
int np,to[maxn][],val[maxn],fail[maxn],id[maxn];
Aho_Corasick_Automaton(){
np=; memset(to[],,sizeof(to[]));
}
void ins(char *s,int ii){
int p=,n=strlen(s);
for(int i=;i<n;i++){
int w=s[i]-'a';
if(!to[p][w]){
to[p][w]=++np,val[np]=id[np]=fail[np]=;
memset(to[np],,sizeof(to[np]));
}
p=to[p][w];
}
val[p]=,id[p]=ii;
}
void getfail(){
queue<int>q;
fail[]=;
for(int w=;w<;w++)
if(to[][w]) fail[to[][w]]=,q.push(to[][w]);
while(!q.empty()){
int p=q.front(); q.pop();
for(int w=;w<;w++){
int j=to[p][w];
if(!j){ to[p][w]=to[fail[p]][w]; continue; }
q.push(j);
fail[j]=to[fail[p]][w];
}
}
}
}ac; void data_in()
{
scanf("%d%d",&L,&N);
for(int i=;i<N;i++) scanf("%s",S[i]);
for(int i=;i<N;i++) if(!vis[i]){
int n=strlen(S[i]);
for(int j=;j<N;j++) if(i!=j){
int m=strlen(S[j]);
if(m>n) continue;
bool ok;
for(int k=;k<=n-m;k++){
ok=;
for(int l=;l<m;l++)
if(S[i][k+l]!=S[j][l]){ ok=; break; }
if(ok) break;
}
if(ok) vis[j]=;
}
}
int tmp=;
for(int i=;i<N;i++) if(!vis[i])
memcpy(S[tmp++],S[i],sizeof(S[i]));
N=tmp;
}
void run(int i,int l,int s)
{
if(i==&&l==&&s==){
cnt++;
for(int j=len-;j>=;j--)
ss[cnt].str[len--j]=path[j];
ss[cnt].str[len]='\0';
return;
}
for(int j=;j<=ac.np;j++) if(f[j][l-][s])
for(int w=;w<;w++) if(ac.to[j][w]==i){
path[len++]=w+'a'; run(j,l-,s);
len--; break;
}
if(ac.val[i]){
s^=<<ac.id[i];
for(int j=;j<=ac.np;j++) if(f[j][l-][s])
for(int w=;w<;w++) if(ac.to[j][w]==i){
path[len++]=w+'a'; run(j,l-,s);
len--; break;
}
}
}
void work()
{
for(int i=;i<N;i++) ac.ins(S[i],i);
ac.getfail();
f[][][]=;
int all=(<<N)-;
for(int l=;l<L;l++)
for(int i=;i<=ac.np;i++){
int ori=ac.val[i]?<<ac.id[i]:;
for(int s=ori;s<=all;s=(s+)|ori){
if(!f[i][l][s]) continue;
for(int w=;w<;w++){
int j=ac.to[i][w];
if(ac.val[j]) f[j][l+][s|(<<ac.id[j])]+=f[i][l][s];
else f[j][l+][s]+=f[i][l][s];
}
}
}
LL ans=;
for(int i=;i<=ac.np;i++) ans+=f[i][L][all];
cout<<ans<<'\n';
if(ans<=){
for(int i=;i<=ac.np;i++)
if(f[i][L][all]) run(i,L,all);
sort(ss+,ss+ans+);
for(int i=;i<=ans;i++) puts(ss[i].str);
}
}
int main()
{
data_in();
work();
return ;
}