bzoj 4596 黑暗前的幻想乡

Posted on | Views:

矩阵树定理 + 容斥原理.

  • 如果把所有出现的边都加上,直接算生成树个数,可能会包括了有某些公司没有用边的情况.
  • 于是减去 $1$ 个公司不修路,其他公司随便修的方案数.再加上 $2$ 个公司不修路的方案数…
  • 二进制大力枚举每个公司的边考不考虑,用矩阵树定理算方案数,乘上容斥系数即可.
  • 时间复杂度 $O(2^n\cdot n^3)$ .

二进制表示状态的题,下标从 $0$ 开始会方便一些.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
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;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
inline int count(int x)
{
	int s=0;
	while(x)
		s+=x&1,x>>=1;
	return s;
}
const int MAXN=20;
typedef pair<int,int> pii;
#define mp make_pair
int n,ans=0;
vector<pii> E[MAXN];
int A[MAXN][MAXN];
int sgn;
void SwapRow(int x,int y,int k)
{
	for(int i=k;i<n;++i)
		swap(A[x][i],A[y][i]);
}
void GCD(int x,int y)
{
	if(!A[y][x])
		return;
	int t=A[x][x]/A[y][x];
	for(int i=x;i<n;++i)
		A[x][i]=add(A[x][i],P-mul(t,A[y][i]));
	SwapRow(x,y,x);
	sgn*=-1;
	GCD(x,y);
}
void Gauss(int x)
{
	if(x==n-1)
		return;
	if(!A[x][x])
	{
		for(int i=x+1;i<n;++i)
			if(A[i][x])
			{
				SwapRow(x,i,x);
				sgn*=-1;
				break;
			}
	}
	if(!A[x][x])
		return;
	for(int i=x+1;i<n;++i)
		if(A[i][x])
			GCD(x,i);
	Gauss(x+1);
}
int det()
{
	int res=1;
	sgn=1;
	Gauss(1);
	for(int i=1;i<n;++i)
		res=mul(res,A[i][i]);
	return add(P,sgn*res);
}
int main()
{
	n=read();
	for(int i=0;i<n-1;++i)
	{
		int m=read();
		for(int j=1;j<=m;++j)
		{
			int u=read(),v=read();
			E[i].push_back(mp(u-1,v-1));
		}
	}
	int mx=1<<(n-1);
	for(int st=0;st<mx;++st)
	{
		memset(A,0,sizeof A);
		int tot=count(st);
		for(int i=0;i<n-1;++i)
		{
			if((st>>i)&1)
				continue;
			int siz=E[i].size();
			for(int j=0;j<siz;++j)
			{
				int u=E[i][j].first;
				int v=E[i][j].second;
				++A[u][u],++A[v][v];
				A[u][v]=add(A[u][v],P-1);
				A[v][u]=add(A[v][u],P-1);
			}
		}
		if(tot&1)
			ans=add(ans,P-det());
		else
			ans=add(ans,det());
	}
	cout<<add(ans%P,P)<<endl;
	return 0;
}