洛谷 P4336 黑暗前的幻想乡 —— 容斥+矩阵树定理

题目：https://www.luogu.org/problemnew/show/P4336

当作考试题了，然而没想出来，呵呵。

其实不是二分图完美匹配方案数，而是矩阵树定理+容斥...

就是先放上所有的边，求生成树个数，但其中可能有的公司的边没有选上，所以减去至少一个公司没选上的，加上两个...

高斯消元里面可以直接除而不用辗转相除，因为取模可以乘逆元，反倒是辗转相除里不能直接用除法，会减不到0。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define pb push_back

using namespace std;

typedef long long ll;

int const xn=,xm=,mod=1e9+;

int n,m[xn],id[xn][xn],deg[xn][xn],sid[xn][xn],ans,cnt;

ll a[xn][xn];

vector<int>vc[xn];

struct N{int u,v;}ed[xm];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

int gauss()

{

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

    for(int j=;j<=n;j++)a[i][j]=upt(deg[i][j]-sid[i][j]);

  int fl=;

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

    {

      int t=i;

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

    if(a[j][i]>a[t][i])t=j;

      if(t!=i)

    {

      fl=-fl;

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

    }

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

    {

      int tmp=(ll)a[j][i]*pw(a[i][i],mod-)%mod;//a[j][i]/a[i][i]

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

        a[j][k]=upt(a[j][k]-(ll)tmp*a[i][k]%mod);

    }

    }

  ll ret=;

  for(int i=;i<n;i++)ret=(ll)ret*a[i][i]%mod;

  return ret*fl;

}

void dfs(int nw,int s)

{

  if(nw==n)

    {

      int sum=gauss();

      if((s&)==((n-)&))ans+=sum; else ans-=sum;

      ans=upt(ans);

      return;

    }

  dfs(nw+,s); int siz=vc[nw].size();

  for(int i=;i<siz;i++)

    {

      int u=ed[vc[nw][i]].u,v=ed[vc[nw][i]].v;

      deg[u][u]++; deg[v][v]++;

      sid[u][v]++; sid[v][u]++;

    }

  dfs(nw+,s+);

  for(int i=;i<siz;i++)

    {

      int u=ed[vc[nw][i]].u,v=ed[vc[nw][i]].v;

      deg[u][u]--; deg[v][v]--;

      sid[u][v]--; sid[v][u]--;

    }

}

int main()

{

  n=rd();

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

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

      ed[++cnt].u=i,ed[cnt].v=j,id[i][j]=id[j][i]=cnt;

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

    {

      m[i]=rd();

      for(int j=,x,y;j<=m[i];j++)x=rd(),y=rd(),vc[i].pb(id[x][y]);

    }

  dfs(,);

  printf("%d\n",ans);

  return ;

}