CF1608D Dominoes 题解

题目链接：Dominoes

题意：

有 \(n(1 \le n \le 10^5)\) 个多米诺骨牌，每个骨牌由左右两个方格组成。有的方格已经被涂上了白色（W）或者黑色（B），剩下的方格（?）还没有被涂色。你需要给所有未涂色的方格涂上黑色或者白色。

一种涂色方案被认为是合法的，当且仅当存在一种排列骨牌方案使得任意一块牌的右面不同于下一块的左面。特殊地，最后一个骨牌的下一块是第一个骨牌。值得注意的是不能旋转它们，也就是不能交换左右方格的颜色。

两种涂色方案被认为是不同的，当且仅当存在一个方格在一个方案中被涂白在另一个方案中被涂黑。形如 BW WB 和 WB BW 的两个方案被认为是不同的方案。（同时他们都是非法的）。

求方案数对 \(998244353\) 取模的结果。

输入：\(n\) 行字符串。输出：答案

搬一张图

一般情况：

至少「一个 \(\mathtt{BB}\) 和一个 \(\mathtt{WW}\) 」，剩下的保证「 \(\mathtt{W}\) 个数等于 \(\mathtt{B}\) 个数」即可。

设有 \(a\) 个 \(\tt B\) 和 \(b\) 个 \(\tt W\) ，则答案为 \[ \binom{2n-a-b}{n-a} \]
没有 \(\tt{BB}\) 或者没有 \(\tt{WW}\) ，需要考虑特例：全染 \(\mathtt{WB}\) 和全染 \(\mathtt{BW}\) ，设这部分贡献为 \(V=0,1,2\)

设有 \(a\) 个 \(\tt B\) 和 \(b\) 个 \(\tt W\) ，则答案为 \(\binom{2n-a-b}{n-a}\) 减去不合法的情况。

不合法的情况就是一个 \(\tt{WW}\) 或者一个 \(\tt{BB}\) 都没有染出来的情况

设共有 \(x\) 个「 \(\tt{W?}\) 和 \(\tt{?B}\) 」，\(y\) 个「 \(\tt{?W}\) 和 \(\tt{B?}\) 」，这些在不合法的情况下是固定的

而剩下的 \(n-x-y\) 个字符串都只能染成 \(\tt{WB}\) 或者 \(\tt{BW}\) ，则答案为 \[ \begin{aligned} \mathrm{Ans} &= \binom{2n-a-b}{n-a} - 2^{n-x-y}+V \\[6pt] &= \binom{2n-a-b}{n-a} - 2^{n-x-y}+[x=0]+[y=0] \end{aligned} \]

于是这道题就做完了。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

char s[N][5];
int fac[N], inv[N];
int qpow(int a, int b)
{
    int r = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
int C(int n, int m)
{
    if(n < m || m < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; fac[0] = 1; int _ = 2 * n;
    for(int i = 1; i <= _; i++) fac[i] = fac[i - 1] * i % mod;
    inv[_] = qpow(fac[_], mod - 2);
    for(int i = _; i; i--) inv[i - 1] = inv[i] * i % mod;
    int s1 = 0, s2 = 0, cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s1 += (s[i][0] == 'W') + (s[i][1] == 'W'); // number of white blocks
        s2 += (s[i][0] == 'B') + (s[i][1] == 'B'); // number of black blocks
        if(s[i][0] == 'W' && s[i][1] == 'W') ++cnt1; // WW
        if(s[i][0] == 'B' && s[i][1] == 'B') ++cnt2; // BB
    }
    if(cnt1 || cnt2) cout << C(2 * n - s1 - s2, n - s1) << '\n';
    else {
        int res = C(2 * n - s1 - s2, n - s1);
        cnt1 = 0, cnt2 = 0;
        for(int i = 1; i <= n; i++)
        {
            if(s[i][0] == 'W' || s[i][1] == 'B') ++cnt1; // W? ?B
            if(s[i][1] == 'W' || s[i][0] == 'B') ++cnt2; // ?W ?B
        }
        if(!cnt1) ++res; if(!cnt2) ++res;
        res = (res + mod - qpow(2, n - cnt1 - cnt2)) % mod;
        cout << res << '\n';
    }
    return 0;
}