300iq Contest 2 C Counting Cactus

这个数据范围显然是要状压的。

考虑一个子集 \(S\)，钦定他的根是 \(u\) 该如何转移（设为 \(f(u,S)\)）：

\(u\) 会在若干个环中，还会有若个用一条边分割的子仙人掌。

也就是若干子仙人掌拼起来。自然需要再设一个 \(g(u,S)\) 表示 \(u\) 为根，且 \(u\) 只包含在一个环或一条边中的方案数。

\(g\) 向 \(f\) 的转移是一个枚举子集，需要保证两边集合的大小关系避免算重。

为了求 \(g\)，再设一个 \(h(u,v,S)\)：环的起始点为 \(u\)，现在加入了 \(v\)。

转移有 \(h(u,v,S\cup T)\leftarrow h(u,d,S)f(v,T)[(v,d)\in E]\)。

显然 \(u\) 处是不能算上 \(f(u,T)\) 的。

注意到一个环会被算两边，但长为 \(2\) 的不会（一条边），所以 \(h\) 向 \(g\) 的转移需要特殊处理一下。

丑陋的代码：

#include <bits/stdc++.h>
#define o(_s,_i) ((_s)>>_i&1)
using namespace std;
const int N=13,M=1<<N,mod=998244353;
int n,m,b[N][N],f[N][M],g[N][M],h[N][N][M];
inline void fix(int&x) {if(x>=mod) x-=mod;}
int main(){
	cin>>n>>m;
	for(int u,v;m--;) cin>>u>>v,u--,v--,b[u][v]=b[v][u]=1;
	for(int i=0;i<n;i++) h[i][i][1<<i]=g[i][1<<i]=1;
	for(int s=1;s<1<<n;s++){
		for(int u=0;u<n;u++) for(int v=0;v<n;v++) if(o(s,u)&&o(s,v))
			for(int t=s;t;t=(t-1)&s) if(o(t,u)&&o(t,v)&&h[u][v][t])
				for(int d=0;d<n;d++) if(o(t^s,d)&&b[v][d]) fix(h[u][d][s]+=1ll*h[u][v][t]*f[d][t^s]%mod);
		for(int u=0;u<n;u++) for(int v=0;v<n;v++) if(o(s,u)&&o(s,v)&&b[u][v])
			fix(g[u][s]+=(mod+1ll)/2*h[u][v][s]%mod);
		for(int u=0;u<n;u++) for(int v=0;v<n;v++) if(u!=v&&o(s,u)&&o(s,v)&&b[u][v])
			fix(g[u][s]+=(mod+1ll)/2*f[v][s^(1<<u)]%mod);
		for(int i=0;i<n;i++) if(o(s,i)){
			f[i][s]=g[i][s];
			for(int t=(s-1)&s;t;t=(t-1)&s) if(o(t,i)&&t!=(1<<i)){
				int p=s^t^(1<<i);
				if(t<p) fix(f[i][s]+=1ll*f[i][t]*g[i][p]%mod);
			}
		}
	}
	cout<<f[0][(1<<n)-1];
	return 0;
}