kmjp's blog

競技プログラミング参加記です

AtCoder ABC #253 (NOMURA プログラミングコンテスト2022) : Ex - We Love Forest

ARC

よろしくないなぁ。
https://atcoder.jp/contests/abc253/tasks/abc253_h

問題

N頂点のグラフを考える。初期状態で辺は1つもない。
ここに、M通りの辺の候補がある。

以下の手順をK回行う。
M通りの辺の候補を等確率で1つ選び、その辺を張る。
同じ交互が複数回選ばれてもよく、その場合辺は多重辺となる。
K回完了後、グラフが森である確率を求めよ。

上記問題をK=1～(N-1)のそれぞれについて解け。

解法

同じ候補を2回選ぶと、その時点で森にはなりえないので、結局異なるK個の候補を選ぶ問題となる。(この問題では選び順も関係あるが、それは解を出力するときにK!を掛けておけばよい)

f(S) := 点の集合Sに対し、辺の候補を|S|-1個選んだ時に木となる選び方
g(n,S) := 点の集合Sに対し、n個の連結成分を成すような辺の候補の選び方

g(K,(全頂点))が求めたい値である。
f(S)は、行列木定理で求められる。
g(n,S)は以下の要領でO(N*2^N+3^N)で求められる。
g(n+1,S∪S') += g(n-1,S)*f(S’) (S'は、Sに含まれない最小の頂点番号を含む点の集合)

int N,M;
int U[555],V[555];
const ll mo=998244353;

ll T[1<<14];
ll P[15][1<<14];
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


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


ll mat[14][14];
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);
		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;

		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
	}
	
	FOR(i,N) T[1<<i]=1;
	int mask;
	FOR(mask,1<<N) if(__builtin_popcount(mask)>=2) {
		vector<int> cand;
		int rev[14]={};
		x=0;
		FOR(i,N) {
			rev[i]=-1;
			if(mask&(1<<i)) rev[i]=x++;
		}
		ZERO(mat);
		FOR(i,M) {
			if(rev[U[i]]==-1||rev[V[i]]==-1) continue;
			mat[rev[U[i]]][rev[V[i]]]--;
			mat[rev[V[i]]][rev[U[i]]]--;
			mat[rev[U[i]]][rev[U[i]]]++;
			mat[rev[V[i]]][rev[V[i]]]++;
		}
		T[mask]=(det_mo(x-1)%mo+mo)%mo;
	}
	
	P[0][0]=1;
	FOR(i,N) FOR(mask,1<<N) if(P[i][mask]) {
		x=-1;
		FOR(j,N) if((mask&(1<<j))==0) {
			x=j;
			break;
		}
		if(x==-1) continue;
		int cand=((1<<N)-1)^mask^(1<<x);
		for(int sm=cand;sm>=0;sm--) {
			sm&=cand;
			
			int ce=__builtin_popcount(mask)-i;
			int ne=__builtin_popcount(sm);
			
			(P[i+1][mask^(1<<x)^sm]+=P[i][mask]*T[(1<<x)^sm])%=mo;
		}
	}
	
	for(i=1;i<=N-1;i++) {
		ll pat=P[N-i][(1<<N)-1]*fact[i]%mo;
		pat=pat*modpow(modpow(M,i))%mo;
		cout<<pat<<endl;
	}
	
	
	
}

まとめ

久々に行列木定理使った。