【状压DP】【字符串】SRM599D1L3 Similar

分析：

每个字符串把它最大的前缀视为父亲，可以建一颗树出来。 显然，如果标号满足$a_i$是$b_i$的前缀，则必须满足：$ai$在树上是$b_i$的祖先。

所以，可以定义 $DP[i][mask]$表示：以i为根的子树中，已经标号的状态为mask的方案数。

暴力转移会挂，所以只能先预处理出每种状态能转移到哪些，使得不会互相矛盾。

因为每个限制条件，在两种状态间只有5种合法状态： $a_i$与$b_i$均不在任何状态中。 $b_i$在X中，$a_i$不在任何状态中。 $b_i$在Y中，$a_i$不在任何状态中。 $a_i$与$b_i$均在X中。 $a_i$与$b_i$均在Y中。 (这只是分析，实际操作的时候可以不这么写)

所以，总共的合法转移方案仅有$5^m$种。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<map> #include<iostream> #define SF scanf #define PF printf #define MAXN 55 #define MAXM 10 #define MAXS 65546 #define MOD 1000000007 using namespace std; typedef long long ll; vector<string> s; vector<int> a[MAXN],b[MAXN],tr[MAXS],son[MAXN]; ll dp[MAXN][MAXS]; map<int,int> mp; int n,m,sz,fa[MAXN]; void dfs(int x){ dp[x][0]=1; for(int i=0;i<int(son[x].size());i++){ int u=son[x][i]; dfs(u); for(int mask=(1<<sz)-1;mask>=0;mask--) for(int j=0;j<int(tr[mask].size());j++){ int k=tr[mask][j]; if(k!=0) dp[x][mask|k]=(dp[x][mask|k]+(dp[x][mask]*dp[u][k])%MOD)%MOD; } } if(x!=0){ for(int mask=(1<<sz)-1;mask>=0;mask--) for(int i=0;i<sz;i++) if(((mask>>i)&1)==0){ bool flag=1; for(int j=0;j<int(a[i].size());j++){ int k=a[i][j]; if(((mask>>k)&1)==0){ flag=0; break; } } if(flag) (dp[x][mask|(1<<i)]+=dp[x][mask])%=MOD; } } } bool used[MAXN]; void dfs(int x,int now,int mask){ if(x==sz){ tr[mask].push_back(now); return ; } if(used[x]==1) dfs(x+1,now|(1<<x),mask); dfs(x+1,now,mask); } bool check(int x,int y){ if(s[x].size()<=s[y].size()) return 0; for(int i=0;i<int(s[y].size());i++) if(s[x][i]!=s[y][i]) return 0; return 1; } int p1[MAXM],p2[MAXM]; int main(){ SF("%d",&n); s.resize(n+1); for(int i=1;i<=n;i++) cin>>s[i]; int u,v; SF("%d",&m); for(int i=0;i<m;i++) SF("%d",&p1[i]); for(int i=0;i<m;i++) SF("%d",&p2[i]); for(int i=1;i<=m;i++){ u=p1[i-1]; v=p2[i-1]; // SF("%d%d",&u,&v); if(mp.count(u)==0) mp[u]=sz++; if(mp.count(v)==0) mp[v]=sz++; b[mp[v]].push_back(mp[u]); a[mp[u]].push_back(mp[v]); } for(int mask=0;mask<(1<<sz);mask++){ for(int j=0;j<sz;j++) used[j]=1; bool flag=0; for(int j=0;j<sz;j++) if((mask>>j)&1){ for(int k=0;k<int(a[j].size());k++) if(((mask>>a[j][k])&1)==0){ flag=1; break; } if(flag) break; used[j]=0; for(int k=0;k<int(b[j].size());k++) used[b[j][k]]=0; } if(flag) continue; dfs(0,0,mask); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(check(i,j)){ if(fa[i]!=0&&s[fa[i]].size()>s[j].size()) continue; fa[i]=j; } for(int i=1;i<=n;i++) son[fa[i]].push_back(i); dfs(0); ll ans=dp[0][(1<<sz)-1]; for(int i=n-sz;i>=1;i--) ans=1ll*ans*i%MOD; PF("%lld\n",ans); }