题目链接：[JSOI2009]密码

我们先看第一问：输出方案数

我们把所有给出来的串丢到AC自动机里面去，然后在建出来的(trie)图上跑dp

由于(nleq 10)我们很自然的就想到了状压

记(dp[i][j][sta])表示原串匹配到了第(i)位，在AC自动机里走到了第(j)个节点，已经出现了(sta)个单词（压缩状态）的方案数

注意到如果有两个串(s_i)和(s_j)满足(s_i)是(s_j)的子串，那么我们所构建的串并不一定必须要有(s_i)，因为如果有了(s_j)那么一定满足了必须有(s_i)

那么我们可以确定最终统计答案时的(sta)，暴力累加即可

接下来就是第二问：输出方案

我么先要考虑一下在什么情况需要做第二问，题目中给的条件是(ansleq 42)

如果此时我们构建的字符串一定有一位“空闲”，即一定有一位可以放置任意字符，而剩下的则必须构成给定的字符串，那么方案数就是(2*26=52>42)（该字符可以放在开头和末尾）

因此此时一定不需要输出答案

所以当要进行第二问的时候，一定是只能用所给定的串进行组合

并且不可能出现的重复的串，因为重复的串是可以变成空闲节点的，这样就和上面一样了

预处理出对于任意两个字符串(s_i,s_j)，(s_i)的后(k)位和(s_j)的前(k)位相等的所有(k)值

然后暴力dfs排序顺序即可

#include<iostream>#include<string.h>#include<string>#include<stdio.h>#include<algorithm>#include<math.h>#include<vector>#include<queue>#include<map>using namespace std;const int maxd=1000000007,N=100000;const double pi=acos(-1.0);typedef long long ll; namespace AC{ struct node{ int ch[27]; int fail,end; node() {memset(ch,0,sizeof(ch));fail=0;end=0;} }point[100100]; int cnt; void init() { cnt=0; point[0].fail=0; } void insert(char *s,int id) { int len=strlen(s),i,now=0; for (i=0;i<len;i++) { if (!point[now].ch[s[i]-'a']) { point[now].ch[s[i]-'a']=(++cnt); point[cnt]=node(); } now=point[now].ch[s[i]-'a']; } point[now].end=(1<<(id-1)); } void get_fail() { queue<int> q; int i; for (i=0;i<26;i++) { if (point[0].ch[i]) { point[point[0].ch[i]].fail=0; q.push(point[0].ch[i]); } } while (!q.empty()) { int u=q.front();q.pop(); for (i=0;i<26;i++) { if (point[u].ch[i]) { point[point[u].ch[i]].fail=point[point[u].fail].ch[i]; q.push(point[u].ch[i]); } else point[u].ch[i]=point[point[u].fail].ch[i]; } } }}using namespace AC;int n,m,len[20],restm,LINK[50][50],ansord[50];ll dp[2][110][1030];char s[20][20];bool del[20]; 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;} int getl(int u,int v){ int maxl,i; for (maxl=min(len[u],len[v]);maxl>0;maxl--) { bool ok=1; for (i=0;i<maxl;i++) { if (s[v][i]!=s[u][len[u]-maxl+i]) {ok=0;break;} } if (ok) return maxl; } return 0;} int ord[50],tot=0;bool vis[50];char ansch[110][110]; void dfs(int dep){ if (dep>restm) { tot++; int i,j,now=0; for (i=1;i<=restm;i++) { for (j=LINK[ord[i-1]][ord[i]];j<len[ord[i]];j++) { ansch[tot][now++]=s[ord[i]][j]; if (now>n) {tot--;return;} } } if (now<n) tot--; return; } int i; for (i=1;i<=m;i++) { if ((del[i]) || (vis[i])) continue; ord[dep]=i;vis[i]=1; dfs(dep+1); vis[i]=0; }} bool cmp(int p,int q){ int i; for (i=0;i<n;i++) if (ansch[p][i]!=ansch[q][i]) return ansch[p][i]<ansch[q][i]; } int main(){ n=read();m=read();restm=m; int i,j,k; for (i=1;i<=m;i++) {scanf("%s",s[i]);len[i]=strlen(s[i]);} for (i=1;i<=m;i++) { for (j=1;j<=m;j++) { if ((del[i]) || (del[j]) || (i==j)) continue; if (len[i]<len[j]) continue; if (strstr(s[i],s[j])) {del[j]=1;restm--;break;} } } init(); for (i=1;i<=m;i++) if (!del[i]) insert(s[i],i); get_fail(); dp[0][0][0]=1; int now=1,pre=0; for (i=1;i<=n;i++) { memset(dp[now],0,sizeof(dp[now])); for (j=0;j<=cnt;j++) { for (k=0;k<(1<<m);k++) { if (dp[pre][j][k]) { int p; for (p=0;p<26;p++) { int v=point[j].ch[p]; dp[now][v][(k|point[v].end)]+=dp[pre][j][k]; } } } } now^=1;pre^=1; } int all=0; for (i=1;i<=m;i++) if (!del[i]) all|=(1<<(i-1)); ll ans=0; for (i=0;i<=cnt;i++) ans+=dp[pre][i][all]; printf("%lldn",ans); if (ans<=42) { for (i=1;i<=m;i++) { for (j=1;j<=m;j++) { if ((del[i]) || (del[j])) continue; LINK[i][j]=getl(i,j); } } memset(vis,0,sizeof(vis)); dfs(1); for (i=1;i<=ans;i++) ansord[i]=i; sort(ansord+1,ansord+1+tot,cmp); for (i=1;i<=tot;i++) { for (j=0;j<n;j++) putchar(ansch[ansord[i]][j]); puts(""); } } return 0;}

bzoj