「SHOI2016」黑暗前的幻想乡

题目链接

戳我

\(Describe\)

\(Solution\)

这道题很明显容斥.答案就是:所有都选的生成树个数\(-\)一个没选的生成树个数\(+\)两个没选的生成树个数\(-...\)

至于生成树个数怎么算,用\(Matrix - Tree\)矩阵树定理做就好了

如果不会:传送门

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

const int mod=1e9+7;

int read(){

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

int a[21][21],len[1001],f[1001][1001],vis[1001][1001],n,ans,bj[10001];

void init(){

	memset(a,0,sizeof(a));

    for(int i=1;i<n;i++)

        if(bj[i])

            for(int j=1;j<=len[i];j++)

                ++a[f[i][j]][f[i][j]],++a[vis[i][j]][vis[i][j]],--a[f[i][j]][vis[i][j]],--a[vis[i][j]][f[i][j]];

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            a[i][j]=(a[i][j]+mod)%mod;

}

int ksm(int a,int b){

	int ans=1;

	while(b){

		if(b&1)

			ans=ans*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ans;

}

int work(){

	init();

	int js=1;

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

		int inv=ksm(a[i][i],mod-2);

        for(int j=i+1;j<=n;j++)

            while(a[j][i]){

                int x=a[j][i]*inv%mod;

                for(int k=i;k<=n;k++)

                    a[j][k]=(a[j][k]-x*a[i][k]%mod+mod)%mod,swap(a[i][k],a[j][k]);

            }

        js=js*a[i][i]%mod;

    }

    return js%mod;

}

void dfs(int x,int opt){

    if(x==n){

		(opt&1)?ans-=work():ans+=work(),ans=(ans+mod)%mod;

        return;

    }

    bj[x]=1;dfs(x+1,opt),bj[x]=0;dfs(x+1,opt+1);

}

main(){

	n=read();

	for(int i=1;i<n;i++){

		len[i]=read();

		for(int j=1;j<=len[i];j++)

			f[i][j]=read(),vis[i][j]=read();

	}

	dfs(1,0);

	printf("%lld",ans);

}