[luogu3244 SHOI2016] 黑暗前的幻想乡(容斥原理+矩阵树定理)

Description

给出 n 个点和 n−1 种颜色，每种颜色有若干条边。求这张图多少棵每种颜色的边都出现过的生成树，答案对 109+7 取模。

Input

第一行包含一个正整数 N(N<=17)，表示城市个数。

接下来 N-1 行，其中第 i行表示第 i个建筑公司可以修建的路的列表：

以一个非负数mi 开头，表示其可以修建 mi 条路，接下来有mi 对数，

每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

Output

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

Sample Input

4

2 3 2 4 2

5 2 1 3 1 3 2 4 1 4 3

4 2 1 3 2 4 1 4 2

Sample Output

Solution

随意选的-一个颜色不选+两个颜色不选。。。

暴力枚举所有情况求出生成树个数统计到答案中即可

Code

//By Menteur_Hxy

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

typedef long long LL;

int read() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int MOD=1000000007;

bool vis[20];

int n,m[20];

int vx[20][400],vy[20][400];

LL ans,ma[20][20];

LL qpow(LL a,LL b) {

	LL t=1;

	while(b) {

		if(b&1) t=t*a%MOD;

		a=a*a%MOD; b>>=1;

	}

	return t;

}

void dfs(int x,int flag) {

	if(x==n) {

		memset(ma,0,sizeof(ma));

		LL now=1,ret;

		F(i,1,n-1) if(vis[i])

			F(j,1,m[i]) ma[vx[i][j]][vx[i][j]]++,ma[vy[i][j]][vy[i][j]]++,

				ma[vx[i][j]][vy[i][j]]--,ma[vy[i][j]][vx[i][j]]--;

		int i,j,k;

		for(i=2;i<=n;i++) {

			for(j=i;j<=n;j++) if(ma[j][i]) break;

			if(j>n) break;

			if(j!=i) {

				flag=-flag;

				F(k,i,n) swap(ma[i][k],ma[j][k]);

			}

			now=now*ma[i][i]%MOD; ret=qpow(ma[i][i],MOD-2);

			for(j=i;j<=n;j++) ma[i][j]=ma[i][j]*ret%MOD;

			for(j=i+1;j<=n;j++) for(ret=ma[j][i],k=i;k<=n;k++)

				ma[j][k]=(ma[j][k]-ret*ma[i][k]%MOD+MOD)%MOD;

		}

		if(i>n) ans=(ans+flag*now+MOD)%MOD;

		return ;

	}

	vis[x]=1; dfs(x+1,flag);

	vis[x]=0; dfs(x+1,-flag);

}

int main() {

	n=read();

	F(i,1,n-1) {

		m[i]=read();

		F(j,1,m[i]) vx[i][j]=read(),vy[i][j]=read();

	}

	dfs(1,1);

	printf("%lld",ans);

	return 0;

}

巴特西