图[FJWC2020Day3]

发表于 分类于 ，

题意

有一张 $n$ 个点，$m$ 条边的无向图，你想选出一个非空点集，使得仅保留这个点集中的点和两个端点都在这个点集里的边后得到的图是连通的。你想知道有多少种可能的选点集的方案。

对 $2$ 取模。

$n\leq 50$，对于所有的边 $(x,y)$，均有 $|x-y|\leq 12$。

题解

这种毒瘤题谁想得到啊qwq。

看到 $|x-y|\leq 12$，能想到状压，也就是 $f_{i,s}$ 表示前 $i$ 位，$[i-11,i]$ 状态为 $s$ 的答案是什么。

导出子图连通，也就是连通块个数为 $1$，否则大于 $1$。

又看到答案对 $2$ 取模。如果用 $cnt$ 表示连通块个数，那么计算 $\sum 2^{cnt}\mod 4$ 就可以了。（这谁想得到啊qwq）

因为当连通块个数大于 $1$ 时，$2^{cnt}\equiv 0\pmod 4$。

而我们知道，连通块个数是非常难统计的。我们转换一下，对于一个导出子图，变成求将点分成两个部分，不同部分的点之间没有连边的方案数。

那么就可以状压了，一个点有三个状态，分别是不在导出子图里，在第一部分，在第二部分。

转移很简单。

最后记得将空集去掉。

时间复杂度 $O(n\times 12\times 3^{12})$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=55;
const int M=531442;
int n,m;
bool bo[N][N];
int pw[13],f[N][M];
inline int bit(int x,int y)
{
	return x/pw[y]%3;
}
int main()
{
	FO(graph);
	n=read(); m=read();
	int x,y;
	fo(i,1,m)
	{
		x=read(),y=read();
		bo[x][y]=bo[y][x]=1;
	}
	pw[0]=1;
	fo(i,1,12) pw[i]=pw[i-1]*3;
	f[0][0]=1;
	int w,t,b[4];
	fo(i,1,n)
		ff(s,0,pw[12])
			if(w=f[i-1][s])
			{
				t=s/3;
				(f[i][t]+=w)&=3;
				b[1]=b[2]=1;
				ff(j,max(13-i,0),12)
					if(bo[i][i-12+j])
						b[3-bit(s,j)]=0;
				if(b[1]) (f[i][t+pw[11]]+=w)&=3;
				if(b[2]) (f[i][t+2*pw[11]]+=w)&=3;
			}
	int ans=3;
	ff(s,0,pw[12]) (ans+=f[n][s])&=3;
	ans>>=1;
	printf("%d",ans);
	return 0;
}