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

Submission #139402852 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #139403670 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论