题解：AT_jsc2021_g Spanning Tree

· · 题解

水篇题解。本题为矩阵树定理基础练习题，不会的可以移步 模板题。

发现题目中给定的条件很像矩阵树定理的矩阵。但是 kirchkoff 矩阵没有办法很好地表示一条边必须连的限制。

所以我们考虑把原图中的连通块缩成一个点，如果一个连通块内产生了环则无解。容易发现缩点后并不会影响生成树计数，因为无论连哪条边永远满足点数减边数等于一。

所以对新图做矩阵树定理即可，模数为质数所以不需要辗转相除，复杂度没有变化但是更为好写。

#include <bits/stdc++.h>
#define lint __int128
#define int long long
#define fi first
#define se second
#define Il inline
#define vec vector
#define pb push_back
#define IT ::iterator
#define p_q priority_queue

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N=300,mod=1e9+7;
const db eps=1e-9,pi=acos(-1.0);

mt19937 rnd(time(0));
Il int rint(int l,int r){return rnd()%(r-l+1)+l;}

Il int qpow(int x,int y){int t=1;for(;y;y>>=1,x=x*x%mod)if(y&1)t=t*x%mod;return t;}

Il int det(int g[N+5][N+5],int n){
    int t=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=(g[i][j]+mod)%mod;
    for(int i=1;i<=n;i++){
        int p=i;while(p<n&&!g[p][i])p++;
        if(!g[p][i])return 0;
        if(i^p){t=-t;for(int j=i;j<=n;j++)swap(g[p][j],g[i][j]);}
        for(int j=i+1;j<=n;j++){int x=g[j][i]*qpow(g[i][i],mod-2)%mod;for(int k=i;k<=n;k++)g[j][k]=(g[j][k]-x*g[i][k]%mod+mod)%mod;}
    }
    t=(t+mod)%mod;for(int i=1;i<=n;i++)t=t*g[i][i]%mod;
    return t;
}

int n,a[N+5][N+5],fa[N+5],b[N+5][N+5],m,id[N+5];

Il int find(int p){return fa[p]^p?fa[p]=find(fa[p]):p;}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(a[i][j]==1){int fx=find(i),fy=find(j);fa[fx]=fy;if(fx==fy){cout<<0;return 0;}}
    for(int i=1;i<=n;i++)if(fa[i]==i)id[i]=++m;
    for(int i=1;i<=n;i++)for(int j=1;j<i;j++){int fx=id[find(i)],fy=id[find(j)];if((fx^fy)&&a[i][j]<0)b[fx][fy]--,b[fy][fx]--,b[fx][fx]++,b[fy][fy]++;}
    cout<<det(b,m-1);
    return 0;
}