bzoj4596 [Shoi2016]黑暗前的幻想鄉 矩陣樹定理+容斥

Description

四年一度的幻想鄉大選開始了，最近幻想鄉最大的問題是很多來曆不明的妖怪湧入了幻想鄉，擾亂了幻想鄉昔日的秩序。但是幻想鄉的建制派妖怪（人類）博麗靈夢和八雲紫等人整日高談所有妖怪平等，幻想鄉多元化等等，對于幻想鄉目前面臨的種種大問題卻給不出合理的解決方案。

風見幽香是幻想鄉裡少有的意識到了問題嚴重性的大妖怪。她這次勇敢地站了出來參加幻想鄉大選，提出包括在幻想鄉邊境建牆（并讓人類出錢），大力開展基礎設施建設挽回失業率等一系列方案，成為了大選年出人意料的黑馬并順利地當上了幻想鄉的大統領。

幽香上台以後，第一項措施就是要修建幻想鄉的公路。幻想鄉一共有 nnn 個城市，之前原來沒有任何路。幽香向選民承諾要減稅，是以她打算隻修 n−1n-1n−1條公路将這些城市連接配接起來。但是幻想鄉有正好 n−1n-1n−1 個建築公司，每個建築公司都想在修路地過程中獲得一些好處。雖然這些建築公司在選舉前沒有給幽香錢，幽香還是打算和他們搞好關系，因為她還指望他們幫她建牆。是以她打算讓每個建築公司都負責一條路來修。

每個建築公司都告訴了幽香自己有能力負責修建的路是哪些城市之間的。是以幽香打算 n−1n - 1n−1條能夠連接配接幻想鄉所有城市的邊，然後每條邊都交給一個能夠負責該邊的建築公司修建，并且每個建築公司都恰好修建一條邊。

幽香現在想要知道一共有多少種可能的方案呢？兩個方案不同當且僅當它們要麼修的邊的集合不同，要麼邊的配置設定方式不同。

Solution

好長的題目啊

容斥簡單題。答案就是至多n家-至多n-1家+至多n-2家…這樣，我們2n枚舉然後跑矩陣樹定理就可以了，容斥系數剛好就是(-1)^i

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fi first
#define se second

typedef std:: pair <int,int> pair;
typedef long long LL;
const int MOD=1000000007;
const int N=25;

LL a[N][N],b[N][N],ans;

std:: vector <pair> c[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

LL det(int n) {
	rep(i,1,n) rep(j,1,n) a[i][j]=(b[i][j]%MOD+MOD)%MOD;
	LL ret=1;
	rep(i,1,n) {
		rep(j,i+1,n) {
			while (a[j][i]) {
				LL tmp=a[i][i]/a[j][i];
				rep(k,i,n) a[i][k]=(a[i][k]-a[j][k]*tmp%MOD+MOD)%MOD;
				std:: swap(a[i],a[j]);
				ret=-ret;
			}
		}
		if (!a[i][i]) return 0;
		ret=ret*a[i][i]%MOD;
	}
	return (ret%MOD+MOD)%MOD;
}

void dfs(int dep,int xs,int n) {
	if (dep==n) {
		ans=ans+xs*det(n-1);
		ans=(ans%MOD+MOD)%MOD;
		return ;
	}
	for (int i=0;i<c[dep].size();++i) {
		pair tmp=c[dep][i];
		b[tmp.fi][tmp.fi]--;
		b[tmp.se][tmp.se]--;
		b[tmp.fi][tmp.se]++;
		b[tmp.se][tmp.fi]++;
	}
	dfs(dep+1,-xs,n);
	for (int i=0;i<c[dep].size();++i) {
		pair tmp=c[dep][i];
		b[tmp.fi][tmp.fi]++;
		b[tmp.se][tmp.se]++;
		b[tmp.fi][tmp.se]--;
		b[tmp.se][tmp.fi]--;
	}
	dfs(dep+1,xs,n);
}

int main(void) {
	int n=read();
	rep(i,1,n-1) {
		for (int s=read();s--;) {
			int x=read(),y=read();
			c[i].push_back(pair(x,y));
			b[x][y]--; b[y][x]--;
			b[x][x]++; b[y][y]++;
		}
	}
	dfs(1,1,n);
	printf("%lld\n", (ans%MOD+MOD)%MOD);
	return 0;
}