The solution of「CF1608D Dominoes」

· · 题解

\textup{CF603B Moodular Arithmetic}

\textup{Luogu} | \textup{CF} | \textup{Cnblogs} | \textup{Tag}：计数。

自己没做出来所以思路借鉴的这篇，但它似乎不算特别严谨，所以算是一个 rewrite。

\textup{Description}

对于 n 个格子对染色，并且格子也许有黑或白的初始色。

求有多少种方式给没上过色的格子上色，使得 i 的右格和 i \bmod n + 1 的左格的颜色不同。

感性理解的话，也就是连起来（首位相接）的时候不同对的格子颜色不能相同。

\textup{Solution}

我们约定给格子对染色分四种，BB,WW,BW,WB。

观察几个性质然后证明。

第一个，BB 和 WW 在合法染色下数量相等。

:::info[\textup{Prove.1}]

因为非黑即白，那么在当前格是 B 的情况下，下一个只能是 W。

而又因为是首尾相接，所以每一个右 B 都能对应一个左 W。

右边为 B 的有 BB 和 WB，而左边为 W 的有 WW 和 WB，且这两种对的总数相等，故得证。

:::

第二个，存在至少 BW 和 WB 各一个的情况下，BB 和 WW 也至少各有一个。

:::info[\textup{Prove.2}]

BW 只能连 BB 或 WW，而 WB 只能连 WW 或 WB。

假设没有 WW 和 BB，那么就会形成只由 BW 或 WB 组成的环，故与两者均存在的情况矛盾，得证。

:::

接下来考虑统计答案。

设当前有 i 个右侧为白色和左侧为黑色的格子对，相等的原因我们上面推过了，自然有 n - i 个左侧为白色和右侧为黑色的格子对。

枚举 i，令从 Q_1 个左 ? 中选 i - B_1 个填 B，从 Q_2 个右 ? 中选 n-i-B_2 个填 B。

得到方案数：

\sum_{i = 0}^{n} C_{Q_1}^{i - B_1} \times C_{Q_2}^{n - i - B_2}

但是这并不正确。

我们在推论 2 中发现，若 BB 和 WW 个数均为 0 时，BW 和 WB 将一定不能同时出现，于是我们多计算了一些方案。

考虑这些方案的个数，在初始状态下没有固定的 BB 或 WW，所以形如 ?? 出现的格子对情况要减掉。

那么我们需要统计 ?? 出现的个数 tot，然后减去 2 ^ {tot}。

但这样也并不正确。

因为当全部填 BW 或 WB 的时候这种情况是满足的，所以还要加回 2。

\textup{Code}

\textup{Rec.}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const int MAXN = 1e5 + 5;
int N;
int lft, rgt, all, B1, B2, W1, W2;
int fac[MAXN], inv[MAXN];

int ksm( int a, int b ){
    int res = 1;
    while( b ){
        if( b & 1 ) ( res *= a ) %= MOD;
        ( a *= a ) %= MOD;
        b >>= 1;
    }
    return res;
}

void pre(){
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for( int i = 2; i < MAXN; i ++ ){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = ( MOD - MOD / i ) * inv[MOD % i] % MOD;
    }
    for( int i = 1; i < MAXN; i ++ ) inv[i] = inv[i] * inv[i - 1] % MOD;
}

int C( int a, int b ){
    if( b < 0 || b > a ) return 0;
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}

void slove(){
    cin >> N;
    pre();
    bool BB = 0, WW = 0;
    for( int i = 1; i <= N; i ++ ){
        char ch1, ch2;
        cin >> ch1 >> ch2;
        if( ch1 == 'B' && ch2 == 'B' ) BB = true;
        if( ch1 == 'W' && ch2 == 'W' ) WW = true;
        if( ch1 == '?' ){
            if( ch2 == '?' ) all ++, lft ++, rgt ++;
            else lft ++;
        } else if( ch2 == '?' ) rgt ++;
        if( ch1 == 'B' ) B1 ++;
        if( ch2 == 'B' ) B2 ++;
        if( ch1 == 'W' ) W1 ++;
        if( ch2 == 'W' ) W2 ++;
    }
    int ans = 0;
    for( int i = 0; i <= N; i ++ ){
        ans += C( lft, i - B1 ) * C( rgt, N - i - B2 ) % MOD;
        ans %= MOD;
        // cerr << ans << endl;
    }
    if( ! BB && ! WW ) ans -= ksm( 2, all ) % MOD;
    ans = ( ans + MOD ) % MOD;
    if( !W1 && ! B2 ) ans ++;
    if( !B1 && ! W2 ) ans ++;
    cout << ans % MOD;
}
signed main(){
    // freopen( "fraud.in", "r", stdin );
    // freopen( "fraud.out", "w", stdout );
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );
    int T = 1;
    // cin >> T;
    while( T -- )
        slove();
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~