Codeforces #758 : D. Dominoes

出来は悪くないけど、最初の1時間足らずしか出番のなかった回。
https://codeforces.com/contest/1608/problem/D

問題

N個のドミノがあり、各ドミノの2マスは白黒で塗られている。
各マスの色は、指定されている場合もあればされない場合もある。

これらのN個を並べ替えたのち、円形に並べたとする。
この時、各ドミノは回転はできない。

ドミノが接している部分は色が異なるように並べられる色の塗り分け方は何通りか。

解法

先に各ドミノ2つ目のマスの色を反転させておく。
そうすると、接する部分の色が一致する問題となる。

黒同士で接するドミノ対の数を総当たりしよう。
そうすると、左右のセルで白黒で塗るべき個数がわかるので、あとは二項係数を使ってそれぞれのパターンを数え上げられる。

int N;
string S;
const ll mo=998244353;
int num[3][3];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int isb=0,isw=0;
	FOR(i,N) {
		cin>>S;
		if(S[1]=='B') S[1]='W';
		else if(S[1]=='W') S[1]='B';
		
		FORR(c,S) {
			if(c=='B') c=0,isb++;
			if(c=='W') c=1,isw++;
			if(c=='?') c=2;
		}
		num[S[0]][S[1]]++;
	}
	ll ret=0;
	// all b
	if(isw==0) ret++;
	// all w
	if(isb==0) ret++;
	
	for(int nb=1;nb<=N-1;nb++) {
		int b1=num[0][0]+num[0][1]+num[0][2];
		int w1=num[1][0]+num[1][1]+num[1][2];
		int b2=num[0][0]+num[1][0]+num[2][0];
		int w2=num[0][1]+num[1][1]+num[2][1];
		
		(ret+=comb(N-b1-w1,nb-b1)*comb(N-b2-w2,nb-b2))%=mo;
		
		// ALL B+ALL C
		if(num[0][1]||num[1][0]) continue;
		int lb=nb-num[0][0]-num[0][2]-num[2][0];
		int lw=N-nb-num[1][1]-num[1][2]-num[2][1];
		(ret+=mo-comb(lb+lw,lb))%=mo;
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

本番Dまでサクサク解けて、後はダメだった。