bzoj 5006 随机二分图

Posted on | Views:

状压 $dp$ .

考虑如果只有单独的边,可以用状压 $dp$ 来做.

设 $f(S,T)$ 表示左边已经匹配的集合为 $S$ ,右边已经匹配的集合为 $T$ 的期望方案数.

为了避免重复计数,规定加入边的顺序为按照左边点的编号从小到大排序.

现在有边组,考虑仍然把它们看成独立的两条边.

可以发现边组二少算了 $\frac 1 4$ 的贡献,边组三多算了 $\frac 1 4$ 的贡献,把边强行绑在一起形成新边,把这些贡献调整过来.

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
75
76
77
78
79
80
81
82
83
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7,inv2=(P+1)>>1,inv4=(P+1)>>2;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int N=15,M=N*N*3;
int n,k,m,U;
struct Edge
{
	int l,r,w;
	Edge(int l=0,int r=0,int w=0):l(l),r(r),w(w) {}
}E[M];
int lowbit(int x)
{
	return x&(-x);
}
bool intersect(int S,int T)
{
	return S&T;
}
map<pair<int,int>,int> f;
int dfs(int S,int T)
{
	if(S==U && T==U)
		return 1;
	pair<int,int> tmp=make_pair(S,T);
	if(f.count(tmp))
		return f[tmp];
	int ans=0;
	for(int i=0;i<m;++i)
	{
		int l=E[i].l,r=E[i].r,w=E[i].w;
		if(!intersect(S,l) && !intersect(T,r) && intersect(l,lowbit(U-S)))
			inc(ans,mul(dfs(S^l,T^r),w));
	}
	return f[tmp]=ans;
}
int main()
{
	n=read(),k=read();
	for(int i=0;i<k;++i)
	{
		int tp=read(),a=read()-1,b=read()-1;
		E[m++]=Edge(1<<a,1<<b,inv2);
		if(tp)
		{
			int c=read()-1,d=read()-1;
			E[m++]=Edge(1<<c,1<<d,inv2);
			if(a==c || b==d)
				continue;
			E[m++]=Edge((1<<a)+(1<<c),(1<<b)+(1<<d),tp==1?inv4:P-inv4);
		}
	}
	U=(1<<n)-1;
	int ans=mul(1<<n,dfs(0,0));
	cout<<ans<<endl;
	return 0;
}