【题意】
给定n个点，和m个公司能建立的边，求由n-1个公司建立n-1条边的生成树的方案数
【分析】
首先，这两个限制条件同时满足比较难考虑，所以我们先考虑枚举由那些公司建立
这样对于一个状态i，二进制每一位表示是否用到了i公司，然后把用到的公司能建立的边加上
跑一边矩阵树定理，计算出方案数
然后我们继续考虑这样算是有重复的，考虑容斥，n-1个公司的方案里包含了n-2个公司的部分，所以要乘上一个$(-1)^{n-公司个数+1}$ 的容斥系数进行计算即可
【代码】
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define lson now<<1 #define rson now<<1|1 typedef long long ll; const int maxs=131100; const int maxn=20; const int mod=1e9+7; int n; int cnt[maxs<<1],lim,pu[maxn][400],pv[maxn][400]; ll d[maxn][maxn]; int tot[maxn]; ll qpow(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll calc() { ll res=1; int trans=0; for(int i=1;i<n;i++) { if(!d[i][i]) { for(int j=i+1;j<n;j++) { if(!d[j][i]) continue; trans^=1; for(int k=1;k<n;k++) swap(d[i][k],d[j][k]); } } for(int j=i;j<n;j++) { if(!d[j][i]) continue; ll inv=qpow(d[j][i],mod-2); res=(res*d[j][i])%mod; for(int k=i;k<n;k++) d[j][k]=d[j][k]*inv%mod; } for(int j=i+1;j<n;j++) { if(!d[j][i]) continue; for(int k=i;k<n;k++) d[j][k]=(d[j][k]-d[i][k]+mod)%mod; } } for(int i=1;i<n;i++) res=res*d[i][i]; return trans?(mod-res)%mod:res; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); int x,y; for(int i=1;i<=n;i++) { scanf("%d",&tot[i]); for(int j=1;j<=tot[i];j++) { scanf("%d%d",&x,&y); pu[i][j]=x; pv[i][j]=y; } } lim=(1<<(n-1))-1; for(int i=1;i<=lim;i++) cnt[i]=cnt[i>>1]+(i&1); ll res=0; for(int i=1;i<=lim;i++) { for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) d[j][k]=0; for(int j=1,p=i;p;p>>=1,j++) { if(p&1) { for(int k=1;k<=tot[j];k++) { x=pu[j][k],y=pv[j][k]; d[y][y]++; d[x][x]++; d[x][y]=(d[x][y]-1+mod)%mod; d[y][x]=(d[y][x]-1+mod)%mod; } } } res=(res+mod+(((n-cnt[i])&1)?calc():-calc()))%mod; } printf("%lld",res); return 0; }
原文：https://www.cnblogs.com/andylnx/p/14816680.html