第二回日本最強プログラマー学生選手権 : G - Spanning Tree

久々にこの定理見た。
https://atcoder.jp/contests/jsc2021/tasks/jsc2021_g

問題

N頂点のグラフを考える。
各頂点対の間に、

• 辺がなければならない
• 辺があってはならない
• 辺があってもなくてもどちらでもよい

のいずれかの関係が与えられる。

この関係を満たすグラフのうち、木となるのは何通りか。

解法

行列木定理で解く。
まず、辺がなければならない辺はつないでしまい、uniono-findを使い連結要素を1つの点に縮約してしまおう。
あとはこの縮約後のグラフに対し、行列木定理を適用する。
縮約後は多重辺がある場合もあるが、それでも行列木定理は問題なく動く。

int N;
int A[303][303];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<303> uf;

const ll mo=1000000007;

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll mat[301][301];
ll det_mo(int N) {
	int x,y,z;
	ll ret=1;
	FOR(y,N) FOR(z,N) mat[y][z]=((mat[y][z]%mo)+mo)%mo;
	FOR(x,N) {
		if(mat[x][x]==0) {
			for(y=x+1;y<N;y++) if(mat[y][x]) break;
			if(y==N) return 0;
			FOR(z,N) swap(mat[x][z],mat[y][z]);
		}
		ret=ret*mat[x][x]%mo;
		ll rev=modpow(mat[x][x],mo-2,mo);
		FOR(z,N) mat[x][z]=rev*mat[x][z]%mo;
		for(y=x+1;y<N;y++) if(mat[y][x]) {
			rev=mat[y][x];
			for(z=x;z<N;z++) mat[y][z]=((mat[y][z]-mat[x][z]*rev)%mo+mo)%mo;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
	}
	FOR(y,N) FOR(x,y) if(A[y][x]==1) {
		if(uf[y]==uf[x]) return _P("0\n");
		uf(y,x);
	}
	map<int,int> to;
	FOR(i,N) {
		if(to.count(uf[i])==0) {
			x=to.size();
			to[uf[i]]=x++;
		}
	}
	FOR(y,N) FOR(x,y) if(A[y][x]==-1) {
		i=to[uf[y]];
		j=to[uf[x]];
		(mat[i][j]+=mo-1)%=mo;
		(mat[j][i]+=mo-1)%=mo;
		mat[i][i]++;
		mat[j][j]++;
	}
	
	cout<<det_mo(to.size()-1)<<endl;
}

まとめ

単なる行列式ではなく、余因子行列を使うっての忘れてた。