「SHOI2016」黑暗前的幻想乡

发表于
字数统计: 1,339字 | 阅读时长 ≈ 6min

「SHOI2016」黑暗前的幻想乡

题目描述

四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡目前面临的种种大问题却给不出合理的解决方案。

风见幽香是幻想乡里少有的意识到了问题严重性的大妖怪。她这次勇敢地站了出来参加幻想乡大选，提出包括在幻想乡边境建墙（并让人类出钱），大力开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺利地当上了幻想乡的大统领。

幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡一共有 $n$ 个城市，之前原来没有任何路。幽香向选民承诺要减税，所以她打算只修 $n - 1$ 条公路将这些城市连接起来。但是幻想乡有正好 $n - 1$ 个建筑公司，每个建筑公司都想在修路地过程中获得一些好处。虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。

每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算 $n - 1$ 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修建一条边。

幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。

输入格式

第一行包含一个整数 $n$，表示城市个数。
接下来 $n - 1$ 行，第 $i$ 行表示 第 $i$ 个建筑公司可以修建的路的列表：以一个非负数 $m_i$ 开头，表示其可以修建 $m_i$ 条路；接下来有 $m_i$ 对数，每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

输出格式

输出一行一个整数，表示所有可能的方案数对 $10^9 + 7$ 取模的结果。

数据范围与提示
Case $n$
1, 2 $\leq 5$
3 ~ 5 $\leq 8$
6 $\leq 10$
7 ~ 10 $\leq 17$

如果不管题目限制，添加所有边直接跑矩阵树定理会怎样？显然会算多有些公司没有负责边的情况。结合$n$的范围，容易想到容斥。答案就是至少0个公司没有负责边的情况-至少1个公司没有负责边的情况+至少2个公司没有负责边的情况……枚举哪些公司的边一定不选即可，时间复杂度$O(2^{n-1}(n-1)^3)$，事实上这是可以过的，高斯消元复杂度并不是满的$O(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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define pr pair
#define fi first
#define se second
#define mp make_pair
#define ll long long
using namespace std;
const ll mod=1e9+7;

int N,sel[20];
ll Ans,Mat[20][20];
vector<pr<int,int> >E[20];

ll ksm(ll a,ll b){
	ll ans=1;a%=mod;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}

void build(int used){
	memset(Mat,0,sizeof(Mat));
	int i,j,x,y;
	for(i=1;i<=used;i++){
		for(j=0;j<E[sel[i]].size();j++){
			x=E[sel[i]][j].fi;y=E[sel[i]][j].se;
			Mat[x][x]++;Mat[y][y]++;
			Mat[x][y]--;Mat[y][x]--;
		}
	}
	for(i=1;i<N;i++)
	for(j=1;j<N;j++)Mat[i][j]=(Mat[i][j]%mod+mod)%mod;
}

ll Gauss(){
	int i,j,id,x,y,sign=0;ll inv,t,ret=1;
	for(x=y=1;x<N&&y<N;x++,y++){
		for(i=x,id=-1;i<N;i++)if(Mat[i][y]){id=i;break;}
		if(id==-1)return 0;
		if(id!=x){
			sign^=1;
			for(i=y;i<N;i++)swap(Mat[id][i],Mat[x][i]);
		}
		inv=ksm(Mat[x][y],mod-2);
		for(i=x+1;i<N;i++){
			t=inv*Mat[i][y]%mod;
			for(j=y;j<N;j++)Mat[i][j]-=Mat[x][j]*t%mod,Mat[i][j]+=Mat[i][j]<0?mod:0;
		}
	}
	for(i=1;i<N;i++)ret=ret*Mat[i][i]%mod;
	if(sign)ret=mod-ret;
	return (ret%mod+mod)%mod;
}

void dfs(int cur,int used){
	if(cur==N){
		build(used);
		if(N-used&1)Ans+=Gauss();
		else Ans-=Gauss();
		Ans=(Ans%mod+mod)%mod;
		return;
	}
	sel[used+1]=cur;
	dfs(cur+1,used+1);
	sel[used+1]=0;
	dfs(cur+1,used);
}

int main(){
	int i,j,k,x,y;
	scanf("%d",&N);
	for(i=1;i<N;i++){
		scanf("%d",&k);
		for(j=1;j<=k;j++){
			scanf("%d%d",&x,&y);
			E[i].push_back(mp(x,y));
		}
	}
	dfs(1,0);
	printf("%lld\n",Ans);
}