【2024NOI模拟赛07】爆搜 做题记录

给定一张 $n$ 个点 $m$ 条边的简单无向图和一个正整数 $c$，对于这个无向图的所有匹配 $S$，求 $c^{|S|}$ 的和 $\text{mod }10^9+7$ 的结果。

一个可空边集 $S$ 被称为匹配当且仅当 $S$ 中任意两条边没有公共点。

$1\le n\le 36$，$0\le m\le \frac{n(n-1)}{2}$，$1\le c\le 10^9+6$。

先将点转化为 0-index。

有个很神奇的转化：对于每个 $i$，在 $2i$ 和 $2i+1$ 之间连一条虚边，那么每个匹配都会形成虚实边交错的若干环和链。

不难发现转化后 $2i$ 和 $2i+1$ 必定是相邻的，那么不妨把它们缩成一个大点，这样就只剩下 $\frac{n}{2}$ 个点了。统计这些大点组成环和链的方案数再组合起来即可，时间复杂度 $O(2^\frac{n}{2}n^2)$（子集 exp）或 $O(3^\frac{n}{2})$（暴力枚举子集）。

具体的，把每个大点内的两个点看作两个插头。对于链的情况，设 $f_{s,x}$ 表示使用了集合 $s$ 中的大点，暴露在外的插头为 $x$ 的方案数，初始 $f_{\{i\},2i}=f_{\{i\},2i+1}=1$；对于环的情况，先把环从编号最小的大点 $u$ 的插头 $2u$ 处断开，设 $g_{s,x}$ 表示使用了集合 $s$ 中的大点，暴露在外的插头为 $x$ 的方案数，初始 $g_{\{i\},2i+1}=1$，最后再把环接起来。

注意链的方案数要除以二。

$O(3^\frac{n}2)$ 代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=36;
const int p=1000000007,inv2=(p+1)/2;

int n,m,c;
bool a[S][S];
int f[1<<(S/2)][S],g[1<<(S/2)][S]; // f:link g:circle
int h[1<<(S/2)],re[1<<S/2];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int mlog(int x)
{
	int res=0;
	while(x>1) res++,x>>=1;
	return res;
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--,y--;
		a[x][y]=a[y][x]=true;
	}
	n=(n+1)/2;
	for(int i=0;i<n;i++) f[1<<i][i*2]=f[1<<i][i*2+1]=1,g[1<<i][i*2+1]=1;
	for(int i=0;i<(1<<n);i++)
	{
		for(int u=0;u<n*2;u++)
		{
			if(f[i][u]==0&&g[i][u]==0) continue;
			for(int j=0;j<n;j++)
			{
				if(i>>j&1) continue;
				for(int k=0;k<=1;k++)
				{
					int v=j*2+k;
					if(!a[u][v]) continue;
					add(f[i|(1<<j)][j*2+(k^1)],1ll*f[i][u]*c%p);
				}
				if((1<<j)<(i&-i)) continue;
				for(int k=0;k<=1;k++)
				{
					int v=j*2+k;
					if(!a[u][v]) continue;
					add(g[i|(1<<j)][j*2+(k^1)],1ll*g[i][u]*c%p);
				}
			}
		}
	}
	for(int i=1;i<(1<<n);i++)
	{
		for(int v=0;v<n*2;v++) add(h[i],1ll*f[i][v]*inv2%p);
		int u=mlog(i&-i)*2;
		for(int v=0;v<n*2;v++)
		{
			if(!a[u][v]) continue;
			add(h[i],1ll*g[i][v]*c%p);
		}
	}
	re[0]=1;
	for(int i=1;i<(1<<n);i++)
	{
		int st=i&-i;
		for(int j=(i^st);;j=(j-1)&(i^st))
		{
			add(re[i],1ll*re[i^j^st]*h[j^st]%p);
			if(j==0) break;
		}
	}
	printf("%d\n",re[(1<<n)-1]);
	return 0;
}