题目链接：[JSOI2009]密码
我们先看第一问：输出方案数
我们把所有给出来的串丢到AC自动机里面去，然后在建出来的\(trie\)图上跑dp
由于\(n\leq 10\)我们很自然的就想到了状压
记\(dp[i][j][sta]\)表示原串匹配到了第\(i\)位，在AC自动机里走到了第\(j\)个节点，已经出现了\(sta\)个单词（压缩状态）的方案数
注意到如果有两个串\(s_i\)和\(s_j\)满足\(s_i\)是\(s_j\)的子串，那么我们所构建的串并不一定必须要有\(s_i\)，因为如果有了\(s_j\)那么一定满足了必须有\(s_i\)
那么我们可以确定最终统计答案时的\(sta\)，暴力累加即可
接下来就是第二问：输出方案
我么先要考虑一下在什么情况需要做第二问，题目中给的条件是\(ans\leq 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("%lld\n",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
bzoj1559 [JSOI2009]密码
原文地址：https://www.cnblogs.com/zhou2003/p/10468634.html