已知有n-1家公司，以及每家公司可以修建的边的集合，现求这个图的生成树个数，并满足n-1家公司都参与了边的修建。

链接

BZOJ 4596

LOJ 2027

题解

使用容斥原理，首先计算出无限制下的方案总数，减去只有两家公司参与修建的方案数，再加上三家公司参与修建的方案数……考虑到n的范围很小，所以容斥的过程直接暴力即可，并利用基尔霍夫矩阵求方案数。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 10010
#define MOD 1000000007
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,k,cnt,sum;
LL ans=0,Ans=0;
int a[25][25],beg[25],en[25];

struct Edge{
    int s,t;
}e[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Swap(int x,int y){
    int i=0,t=0;
    for (i=1;i<n;i++){
        t=a[x][i];  a[x][i]=a[y][i];    a[y][i]=t;
    }
}

inline void Gauss(){
    int i=0,j=0,k=0;
    LL t=0;
    ans=1;
    for (i=1;i<n;i++)
        for (j=i+1;j<n;j++){
            while (a[j][i]){
                t=a[i][i]/a[j][i];
                for (k=1;k<n;k++)   a[i][k]=(a[i][k]-t*a[j][k])%MOD;
                Swap(i,j);  ans*=-1;
            }
        }
    for (i=1;i<n;i++)   ans=(ans*a[i][i]+MOD)%MOD;
    while (ans<0)   ans+=MOD;
}

int main(){
    scanf("%d",&n); cnt=1;
    for (i=1;i<=n-1;i++){
        scanf("%d",&m); beg[i]=cnt;
        for (j=1;j<=m;j++){
            scanf("%d%d",&e[cnt].s,&e[cnt].t);
            cnt++;
        }
        en[i]=cnt-1;
    }
    for (i=0;i<(1<<(n-1));i++){
        sum=0;  memset(a,0,sizeof(a));
        for (j=0;j<=n-2;j++)
            if ((1<<j)&i)   {
                sum++;
                for (k=beg[j+1];k<=en[j+1];k++){
                    a[e[k].s][e[k].s]++;    a[e[k].t][e[k].t]++;
                    a[e[k].s][e[k].t]--;    a[e[k].t][e[k].s]--;
                }
            }
        Gauss();
        Ans=((n-sum)&1)?(Ans+ans)%MOD:(Ans-ans+MOD)%MOD;
    }
    while (Ans<0)   Ans+=MOD;
    cout<<Ans%MOD<<endl;
    return 0;
}