Codeforces Round #758 Dominoes 题解 (Java/C++)

题解

首先，我们需要注意到的是，多米诺牌涂色后其实就只有4种状态：BW，WB，WW，BB。

于是我们自然的开始考虑如何构造一个有效的涂色方法。不难发现，最终的构造方案一定形如：BB, WB, WB, ..., WB, WW, BW, BW, ..., BW, BB, WW, BB, WW。
也就是说：1. 只要存在BB和WW，那么WB和BW其实对构造没啥影响。2. BB的数目一定和WW的数目一致。
当然一个例外就是没有BB和WW的情况，这种情况下，要么全是WB，要么全是BW。

于是，显然的，字母B的数目和字母W的数目一定一样。（因为BB和WW数目相等，而WB和BW并不影响B和W的数目）
而这个结论反过来也几乎一样：当字母B和字母W的数目一样时，这个涂色一定有效。因为数目一样时，排除掉WB和BW，剩下的字母B的数目依然和字母W的数目一样，因此剩下的BB和WW的数目一定一样。
于是涂色的方法数为：$C_{2n-\text{count('W')}-\text{count('B')}}^{n - \text{count('W')}}$。

但有一个例外，如果全部都是WB和BW时，因为没有BB和WW，那么既有WB又有BW的涂法是无效的。
显然对于"W?"或者"?B"只可能涂成WB。"?W"或者"B?"只能涂成BW。而"??"两种都可以。
记invalid为无效的涂法数目，则有$invalid=2^{\text{count('??')}}$。
但这里又有例外，如果可以全部涂成WB，则invalid-=1。同理如果可以涂成BW，则invalid-=1。

最终的结果为：$C_{2n-\text{count('W')}-\text{count('B')}}^{n - \text{count('W')}} - \text{invalid}$。

代码

Java

C++