BZOJ4596: [Shoi2016]黑暗前的幻想乡

Description

四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖

怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）

博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡

目前面临的种种大问题却给不出合适的解决方案。

风间幽香是幻想乡里少有的意识到了问题的严重性的大妖怪。她这次勇敢的

站了出来参加幻想乡大选。提出包括在幻想乡边境建墙（并让人类出钱），大力

开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺

利的当上了幻想乡的大统领。

幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市，

之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将

这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，每个建筑公司都想

在修路的过程中获得一些好处。

虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，

因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。

每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所

以幽香打算选择 N-1 条能够连接幻想乡所有城市的边，然后每条边都交给一

个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修一条边。

幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它

们要么修的边的集合不同，要么边的分配方式不同。

Input

第一行包含一个正整数 N(N<=17)，表示城市个数。

接下来 N-1 行，其中第 i行表示第 i个建筑公司可以修建的路的列表：

以一个非负数mi 开头，表示其可以修建 mi 条路，接下来有mi 对数，

每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

Output

仅一行一个整数，表示所有可能的方案数对 10^9 + 7 取模的结果。

Sample Input

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

Sample Output

和ZJOI小星星很像啊。

考虑容斥原理，设A(x)表示x公司参与修建的方案集合，那么答案等价于求|A(1)∩A(2)∩……∩A(n)|，容斥转化成并集形式，然后用MatrixTree定理计算即可。

实际复杂度为O(N^3*2^N)。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,1,BufferSize,stdin);

        tail=(head=buffer)+l;

    }

    return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

typedef long long ll;

const int maxn=20;

const int mod=1000000007;

typedef ll Matrix[maxn][maxn];

void gcd(ll a,ll b,ll& x,ll& y) {

    if(!b) x=1,y=0;

    else gcd(b,a%b,y,x),y-=x*(a/b);

}

ll getinv(ll a) {

    ll b=mod,x,y;gcd(a,b,x,y);

    return (x+mod)%mod;

}

Matrix B;

ll gauss(Matrix A,int n) {

    ll ans=1;

    rep(i,0,n-1) {

        int r=i;

        rep(j,i+1,n-1) if(abs(A[r][i])<abs(A[j][i])) r=j;

        if(r!=i) ans*=-1,swap(A[r],A[i]);

        ll inv=getinv(A[i][i]);

        rep(k,0,n-1) if(i!=k)

           dwn(j,n-1,i) A[k][j]=(A[k][j]-A[k][i]*A[i][j]%mod*inv%mod+mod)%mod;

    }

    rep(i,0,n-1) (ans*=A[i][i])%=mod;

    return (ans+mod)%mod;

}

struct Company {

    int m,u[maxn*maxn],v[maxn*maxn];

}A[maxn];

int main() {

    int n=read();

    rep(i,0,n-2) dwn(j,A[i].m=read(),1) A[i].u[j]=read(),A[i].v[j]=read();

    ll ans=0;

    rep(S,0,(1<<n-1)-1) {

        int cnt=0;

        rep(i,0,n-1) rep(j,0,n-1) B[i][j]=0;

        rep(i,0,n-2) if(S>>i&1) {

            cnt++;

            rep(j,1,A[i].m) {

                int u=A[i].u[j]-1,v=A[i].v[j]-1;

                B[u][u]++;B[v][v]++;B[u][v]--;B[v][u]--;

            }

        }

        rep(i,0,n-1) rep(j,0,n-1) (B[i][j]+=mod)%=mod;

        if(n-1-cnt&1) (ans-=gauss(B,n-1))%=mod;

        else (ans+=gauss(B,n-1))%=mod;

    }

    printf("%lld\n",(ans+mod)%mod);

    return 0;

}

秒客网