矩阵树定理（高斯消元+乘法逆元）+容斥
ans=总方案数 -（公司1未参加方案数 ∪ 公司2未参加方案数 ∪ 公司3未参加方案数 ∪ ...... ∪ 公司n未参加方案数）
方案数=生成树方案数 所以用矩阵树定理瞎搞
显然后面的部分可以用容斥原理求解
枚举的时候用一个数转成二进制来表示哪些公司参加/不参加
mod=1e9+7是质数所以可以在高斯消元的时候用逆元搞
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> using namespace std; typedef long long ll; template <typename T> inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); } const int mod=1e9+7; inline ll ksm(ll x,int y){ ll res=1; for(;y;y>>=1){ if(y&1) res=res*x%mod; x=x*x%mod; }return res; } struct edge{int x,y;}a[19][402]; ll f[19][19]; int n,b[19]; inline ll det(){ //高斯消元 ll res=1; int c=1; for(int i=1;i<n;++i){ int p=i; for(int j=i+1;j<n;++j) if(f[j][i]>f[p][i]) p=j; if(p!=i) swap(f[i],f[p]),c=-c; //注意行列式每次交换行符号都会改变 for(int j=i+1;j<n;++j){ ll div=f[j][i]*ksm(f[i][i],mod-2)%mod; //除法转成乘逆元 for(int k=i;k<n;++k) f[j][k]=(f[j][k]-f[i][k]*div%mod+mod)%mod; } res=res*f[i][i]%mod; }return (res*c+mod)%mod; } int main(){ read(n); ll ans=0; for(int i=1;i<n;++i){ read(b[i]); for(int j=1;j<=b[i];++j) read(a[i][j].x),read(a[i][j].y); } for(int i=1;i<=(1<<(n-1))-1;++i){ //i转为二进制数表示方案：0/1 表示是否参加 memset(f,0,sizeof(f)); //清空重建图 int p=i,cnt=0; for(int j=1;p;++j,p>>=1){ if(!(p&1)) continue; //二进制表示下该位为0->没参加该方案 for(int k=1;k<=b[j];++k){ //kirchhoff矩阵=度数矩阵-邻接矩阵 int X=a[j][k].x,Y=a[j][k].y; ++f[X][X]; ++f[Y][Y]; f[X][Y]=(f[X][Y]-1+mod)%mod; //注意减法要重新取模 f[Y][X]=(f[Y][X]-1+mod)%mod; }++cnt; } ans=(ans+((n-1-cnt)&1 ? -det():det())+mod)%mod; //容斥原理决定是加还是减 }printf("%lld",ans); return 0; }