UVALive
给你m个字符串，让你构造一个字符串，包含所有的m个子串，问有多少种构造方法。如果答案不超过42，则按字典序输出所有可行解。
由于m很小，所以可以考虑状压。
首先对全部m个子串构造出AC自动机，每个节点有一个附加属性val[u]代表结点u包含的子串集合。
设dp[l][S][u]为长度为l，包含子串集合为S，当前在结点u时，接下来能构造出的合法字符串总数，则dp[l][S][u]=∑dp[l+1][S|val[v]][v],v=go[u][i],0<=i<26;
两遍dfs，一遍dp，一遍输出答案即可。
注意一个结点可能是多个字符串的结尾，因此在建AC自动机的时候，每个结点的val值还要加上其pre结点的val值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=25+5; 5 int n,m,ka; 6 char s[N]; 7 8 struct AC { 9 static const int N=100+10,M=26; 10 int go[N][M],pre[N],tot,val[N]; 11 ll d[27][(1<<10)+10][N],ans; 12 int idx(char ch) {return ch-'a';} 13 void init() {tot=0; newnode();} 14 int newnode() { 15 int u=tot++; 16 memset(go[u],0,sizeof go[u]); 17 val[u]=pre[u]=0; 18 return u; 19 } 20 void ins(char* s,int x) { 21 int u=0,n=strlen(s); 22 for(int i=0; i<n; u=go[u][idx(s[i])],++i) 23 if(!go[u][idx(s[i])])go[u][idx(s[i])]=newnode(); 24 val[u]|=1<<x; 25 } 26 void build() { 27 queue<int> q; 28 for(int i=0; i<M; ++i)if(go[0][i])q.push(go[0][i]); 29 while(!q.empty()) { 30 int u=q.front(); 31 q.pop(); 32 val[u]|=val[pre[u]]; 33 for(int i=0; i<M; ++i) { 34 if(go[u][i]) { 35 pre[go[u][i]]=go[pre[u]][i]; 36 q.push(go[u][i]); 37 } else go[u][i]=go[pre[u]][i]; 38 } 39 } 40 } 41 ll dp(int l,int S,int u) { 42 if(l==n)return S==(1<<m)-1?1:0; 43 ll& ret=d[l][S][u]; 44 if(~ret)return ret; 45 ret=0; 46 for(int i=0; i<M; ++i) { 47 int v=go[u][i]; 48 ret+=dp(l+1,S|val[v],v); 49 } 50 return ret; 51 } 52 void dfs(int l,int S,int u) { 53 if(l==n) { 54 if(S==(1<<m)-1)s[l]='