P4336 [SHOI2016]黑暗前的幻想乡

P4336 [SHOI2016]黑暗前的幻想乡

矩阵树定理（高斯消元+乘法逆元）+容斥

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=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

}

const int mod=1e9+;

inline ll ksm(ll x,int y){

    ll res=;

    for(;y;y>>=){

        if(y&) res=res*x%mod;

        x=x*x%mod;

    }return res;

}

struct edge{int x,y;}a[][];

ll f[][];

int n,b[];

inline ll det(){ //高斯消元

    ll res=; int c=;

    for(int i=;i<n;++i){

        int p=i;

        for(int j=i+;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+;j<n;++j){

            ll div=f[j][i]*ksm(f[i][i],mod-)%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=;

    for(int i=;i<n;++i){

        read(b[i]);

        for(int j=;j<=b[i];++j) read(a[i][j].x),read(a[i][j].y);

    }

    for(int i=;i<=(<<(n-))-;++i){ //i转为二进制数表示方案：0/1 表示是否参加

        memset(f,,sizeof(f)); //清空重建图

        int p=i,cnt=;

        for(int j=;p;++j,p>>=){

            if(!(p&)) continue; //二进制表示下该位为0->没参加该方案

            for(int k=;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]-+mod)%mod; //注意减法要重新取模

                f[Y][X]=(f[Y][X]-+mod)%mod;

            }++cnt;

        }

        ans=(ans+((n--cnt)& ? -det():det())+mod)%mod; //容斥原理决定是加还是减

    }printf("%lld",ans);

    return ;

}