题目大意

给定$n$个点的无向图，求它的$Dfs$序方案数

$n\leq 18$

 

题解

状压$Dp+$记忆化搜索。

设$F_{i,now}$表示到达$i$其中$now$集合代表的点集已经遍历过，还需要遍历其余点的方案数。

考虑枚举$i$每一个不在点集内部的出边进行记忆化搜索转移。

这样会有一个问题:无法解决回溯。

考虑设$G_{i,now}$表示已选了点集$now$当前位置在$i$，能遍历到的所有最大状态，即当前情况下$i$的子树的集合与$now$的并集。

$G_{i,now}$也可以用记忆化搜索处理。

这样，对于每一个$F_{x,now}$，枚举每一个$\notin now$的$x$的后继$y$,

$$F_{x,now}=\sum F_{x,G_{y,now|y}}\times F_{y,now|y}$$

复杂度$O(n^2 2^n)$

#include
     
      #define debug(x) cerr<<#x<<" = "<
      
       =mod?x-mod:x)int Trans(int x,int now){	if(G[x][now]>=0) return G[x][now]; G[x][now]=now;	for(int k=1;k<=sz[x];k++){		int to=c[x][k]; if((now>>(to-1))&1) continue;		G[x][now]|=Trans(to,now|(1<<(to-1)));	}return G[x][now];}int Dp(int x,int now){	if(Trans(x,now)==now) return 1;	if(F[x][now]>=0) return F[x][now]; F[x][now]=0;	for(int k=1;k<=sz[x];k++){		int to=c[x][k];		if((now>>(to-1))&1) continue;		int t1=Dp(to,now|(1<<(to-1)));		int t2=Dp(x,now|Trans(to,now|(1<<(to-1))));		int res=(LL)t1*(LL)t2%mod; upd(F[x][now],res);	} return F[x][now];}int main(){	n=read(),m=read(),memset(G,-1,sizeof(G)),memset(F,-1,sizeof(F));	for(int i=1;i<=m;i++){int x=read(),y=read();c[x][++sz[x]]=y,c[y][++sz[y]]=x;}	for(int i=1;i<=n;i++) upd(ans,Dp(i,1<<(i-1))); printf("%d\n",ans); return 0;}