BZOJ 4596: [Shoi2016]黑暗前的幻想乡

时间：2023-03-09 21:32:24
BZOJ 4596: [Shoi2016]黑暗前的幻想乡

Sol

容斥原理+Matrix-Tree定理.容斥跟小星星那道题是一样的,然后...直接Matrix-Tree定理就可以了...

复杂度\(O(2^{n-1}n^3)\)

PS:调了好久啊QAQ 明明知道了Matrix-Tree定理了以后非常简单QAQ n-1写成n 直接真·爆0.

Code

/**************************************************************

    Problem: 4596

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:6040 ms

    Memory:1296 kb

****************************************************************/

#include<cstdio>

#include<cstring>

#include<utility>

#include<vector>

#include<iostream>

using namespace std;

#define mpr(a,b) make_pair(a,b)

#define _0(x) ((x>0?x:-x)>0)

typedef long long LL;

const int N = 18;

const LL p = 1000000007;

int n,cnt,S;LL ans;int pow2[N];

vector<pair<int,int> > g[N];

LL a[N][N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

LL Pow(LL a,LL b,LL res=1){ for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;return res; }

void Build(int S){

    memset(a,0,sizeof(a));cnt=0;

    for(int i=0;i<n-1;i++) if(S&pow2[i]){

        cnt++;

        for(int j=0;j<g[i].size();j++){

            int u=g[i][j].first,v=g[i][j].second;

            a[u][v]--,a[v][u]--,a[u][u]++,a[v][v]++;

        }

    }

    for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i][j]=(a[i][j]+p)%p;

//  for(int i=0;i<n;i++) for(int j=0;j<n;j++) printf("%10I64d%c",a[i][j]," \n"[j==n-1]);

//  cout<<"*******************"<<endl;

}

LL det(int n){

    LL res=1;int swpt=0;

    for(int i=0,j,k;i<n;i++){

        if(!_0(a[i][i])){

            for(j=i+1;j<n;j++) if(_0(a[j][i])) break;

            if(j>=n) return 0;

            for(k=i;k<n;k++) swap(a[i][k],a[j][k]);

            swpt++;

        }

        res=(res*a[i][i]%p+p)%p;

        LL inv=Pow(a[i][i],p-2);

//      for(j=i+1;j<n;j++) a[i][j]/=a[i][i];

//      for(j=i+1;j<n;j++) for(k=i+1;k<n;k++) a[j][k]-=a[j][i]*a[i][k];

        for(j=i+1;j<n;j++) for(k=i+1;k<n;k++) a[j][k]=(a[j][k]-a[j][i]*a[i][k]%p*inv%p+p)%p;

    }if(swpt&1) return -res;return res;

}

int main(){

    n=in();pow2[0]=1;for(int i=1;i<17;i++) pow2[i]=pow2[i-1]<<1;

    for(int i=0;i<n-1;i++){ int x=in();for(int j=1,u,v;j<=x;j++) u=in()-1,v=in()-1,g[i].push_back(mpr(u,v)); }

    for(S=1;S<pow2[n-1];S++){

//      Build(S);

//      cout<<cnt<<" "<<det(n-1)<<endl;

        Build(S);

        if((n-1-cnt)&1) ans=(ans-det(n-1)+p)%p;else ans=(ans+det(n-1))%p;

    }cout<<(ans+p)%p<<endl;return 0;

}

　　

　　

相关文章