yukicoder : No.2435 Order All Company

これはすんなり。
https://yukicoder.me/problems/no/2435

問題

N点M辺の無向グラフが与えられる。
各辺はK色のいずれかを持つ。

この辺から(N-1)辺を選んで全域木を作るとき、K色の辺が最低1本ずつ含まれるのは何通りか。

解法

包除原理で解く。
f(bitmask) := 使ってよい辺の色がbitmaskの範囲内であるときの全域木の数
とすると、bitmaskのうちビットが立っている数の偶奇に応じてf(bitmask)を足し引きすればよい。
全域木の数は行列木定理で計算できる。

int N,K;
vector<pair<int,int>> E[5];
const ll mo=998244353;
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[101][101];
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>>K;
	FOR(i,K) {
		cin>>x;
		FOR(j,x) {
			cin>>y>>k;
			E[i].push_back({y-1,k-1});
		}
	}
	int mask;
	ll ret=0;
	FOR(mask,1<<K) if(mask) {
		ZERO(mat);
		FOR(i,K) if(mask&(1<<i)) {
			FORR2(a,b,E[i]) {
				mat[a][a]++;
				mat[b][b]++;
				(mat[a][b]+=mo-1)%=mo;
				(mat[b][a]+=mo-1)%=mo;
			}
		}
		ll a=det_mo(N-1);
		if(K%2==__builtin_popcount(mask)%2) {
			ret+=a;
		}
		else {
			ret+=mo-a;
		}
	}
	cout<<ret%mo<<endl;
	
}

まとめ

久々の行列木定理。