题目传送门

看到题目要求求出方案数，所以要么用 dp 要么用组合数学，这里本蒟蒻用的是 dp 求解。

首先我们来考虑这道题的算法。结合字符串和题目要求，我们发现这道题跟 AC 自动机有关我才不会告诉你我是从标签里看到的。

其次来推导 dp 方程。观察数据范围得出，这道题可以使用状压来解决，那么这道题的方程就显而易见了。用 $dp_{i,j,k}$ 来表示构造出 $i$ 位后，当前在 AC 自动机的第 $j$ 个节点，子串集为 $k$ 的方案数，则转移方程为 $dp_{i,j,k}→dp_{i+1,tr_{j,l},k|state_{tr_{j,l}}}$ 。那么最终答案为 $\sum\limits_{i=0}^{temp} dp_{len,i,2^n-1}$ 。

最后来考虑怎样输出答案。我们可以用一个 bool 数组 $f_{i,j,k}$ 来表示构造出 $i$ 位后，当前在 AC 自动机的第 $j$ 个节点，子串集为 $k$ 时是否可以继续构造下去使得最终可以构造出一个满足题目条件的字符串。而这个 bool 数组可以用 dfs 来解决。最终我们在结合着 $f$ 数组输出就可以了。

提醒

1. 一定要开 long long 。

2. dfs 时一定要加记忆化。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,l,tr[110][30],cnt[110],fail[110],tot=0;
long long dp[30][110][(1<<10)];
bool f[30][110][(1<<10)],vis[30][110][(1<<10)];
void addtrie(string s,int x) //创建trie树
{
	int rt=0;
	for(int i=0;i<s.size();i++)
	{
		if(!tr[rt][s[i]-'a']) tr[rt][s[i]-'a']=++tot;
		rt=tr[rt][s[i]-'a'];
	}
	cnt[rt]|=(1<<(x-1));
}

void qfail() //通过BFS算出失配指针
{
	queue<int> q;
	for(int i=0;i<26;i++) 
	{
		if(tr[0][i])
		{
			fail[tr[0][i]]=0;
			q.push(tr[0][i]);
		}
	 } 
	while(!q.empty())
	{
		int nw=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(tr[nw][i])
			{
				fail[tr[nw][i]]=tr[fail[nw]][i];
				cnt[tr[nw][i]]|=cnt[tr[fail[nw]][i]];
				q.push(tr[nw][i]);
			}
			else tr[nw][i]=tr[fail[nw]][i];
		}
	}
}

bool dfs1(int x,int y,int z) //求取f数组
{
	if(vis[x][y][z]) return f[x][y][z];
	vis[x][y][z]=true;
	if(x==l)
	{
		if(z==(1<<n)-1) f[x][y][z]=true;
		return f[x][y][z];
	}
	for(int i=0;i<26;i++)
	{
		f[x][y][z]|=dfs1(x+1,tr[y][i],z|cnt[tr[y][i]]);
	}
	return f[x][y][z];
}

char c[30];

void dfs2(int x,int y,int z) //输出最终答案
{
	if(x==l)
	{
		for(int i=1;i<=l;i++) cout<<(char)(c[i]+'a');
		cout<<endl;
		return;
	}
	for(int i=0;i<26;i++)
	{
		if(f[x+1][tr[y][i]][z|cnt[tr[y][i]]])
		{
			c[x+1]=i;
			dfs2(x+1,tr[y][i],z|cnt[tr[y][i]]);
		}
	}
}

int main()
{
	string s;
	cin>>l>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		addtrie(s,i);
	}
	qfail(); //构建AC自动机
	dp[0][0][0]=1;
	for(int i=0;i<l;i++)
	{
		for(int j=0;j<=tot;j++)
		{
			for(int k=0;k<(1<<n);k++)
			{
				for(int o=0;o<26;o++)
				{
					dp[i+1][tr[j][o]][k|(cnt[tr[j][o]])]+=dp[i][j][k];  //dp求解每种状态能以多少种方案完成
				}
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=tot;i++) ans+=dp[l][i][(1<<n)-1]; //统计方案数
	cout<<ans<<endl;
	if(ans<=42)
	{
		dfs1(0,0,0);
		dfs2(0,0,0);
	}
	return 0;
}