Luogu

BZOJ

分析

求出来的$n-1$条边要满足两个限制:

  • 构成一颗生成树
  • 恰好$n-1$种颜色

考虑容斥,用至多$n-1$种颜色的,减去至多$n-2$种的,加上至多$n-3$种的,......

至于生成树个数怎么求,用$\texttt{Matrix_Tree}$定理就行了。

然后就可以直接枚举子集容斥去算了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=17+10;
const int MOD=1e9+7;

int n;
int m[N],cnt[1<<17];
struct Edge { int u,v; } G[N][N*N];
int a[N][N];

inline void build(int S) {
    memset(a,0,sizeof(a));
    for (re int i=1;i<n;++i) {
        if ((S&(1<<i-1))==0) continue;
        for (re int j=1;j<=m[i];++j) {
            int u=G[i][j].u,v=G[i][j].v;
            ++a[u][u],++a[v][v],--a[u][v],--a[v][u];
        }
    }
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            a[i][j]=(a[i][j]+MOD)%MOD;
}

inline int calc(int S) {
    build(S); int ans=1;
    for (re int i=2;i<=n;++i) {
        for (re int j=i+1;j<=n;++j)
            while (a[j][i]) {
                int t=a[i][i]/a[j][i];
                for (re int k=i;k<=n;++k) {
                    a[i][k]=(a[i][k]-1ll*a[j][k]*t%MOD+MOD)%MOD;
                    swap(a[i][k],a[j][k]);
                }
                ans=MOD-ans;
            }
        ans=1ll*ans*a[i][i]%MOD;
    }
    return ans;
}

int main() {
    n=read(); int ans=0;
    for (re int i=1;i<n;++i) {
        m[i]=read();
        for (re int j=1;j<=m[i];++j)
            G[i][j].u=read(),G[i][j].v=read();
    }
    for (re int S=0;S<(1<<n-1);++S) cnt[S]=cnt[S>>1]+(S&1);
    for (re int S=0;S<(1<<n-1);++S) {
        int x=calc(S);
        if ((n-cnt[S]-1)&1) x=MOD-x;
        ans=(ans+x)%MOD;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 14 PM