2020-12-08

Codeforces Global Round 12 H1. Multithreading (Easy Version) (R2900)

Codeforces CodeforcesCombined CodeforcesR2900 数え上げ問題入れ子構造変数変換して扱いやすい同型な問題を見出すワイルドカード問題二項係数 DP 解空間:O(N^2)通りの選択肢数珠「選ぶ」と「選ばない」の一対一対応期待値 0と1の問題多項式・FPS(形式的冪級数) カッコ列交差数に関する問題

ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した

drken1215.hatenablog.com

問題へのリンク

問題概要 (意訳)

"B", "W", "?" のみからなる長さ $N$ の文字列が与えられる ( $N$ は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B", "W" の個数がともに偶数となるものを一様ランダムにとってくる。

"B" と "W" がともに偶数個ずつある文字列のスコアを次のように定める。文字列中の連続する 2 文字 (左右両端も連続する 2 文字とみなす) であって同じ文字から成っている箇所を削除する操作を好きな回数だけ行ったとき、最終的に得られる文字列の長さの最小値を 4 で割った値とする。

"?" へ "B", "W" を割り当てる方法であって条件を満たすものを一様ランダムに選んだときの、文字列のスコアの期待値を 998244353 で割ったあまりで求めよ。

制約

$2 \le N \le 2 \times 10^{5}$

考えたこと

期待値の問題だけど実質的には数え上げ問題。まず "?" を埋める方法は、"?" の個数を $K$ とすると、

$2^{K-1}$ 通り

となる。もし B の個数が偶数個という制約がなければ $2^{K}$ 通りになる。「B の個数が偶数個」という場合と「B の個数が奇数個」という場合とは一対一対応が作れることから、これらは同数ずつある。よって全体の方法の個数は $2^{K-1}$ 通りとなる、以上から、条件を満たすすべての文字列に対するスコアの総和を求めて、最後に $2^{K-1}$ で割ればよいことがわかった。

さて、文字列のスコアの決め方は完全に Neither AB nor BA と同じ。とすれば、同じ手法が使えそうだ。

文字列の 0, 2, 4, ... 番目の "B" と "W" とを入れ替えると、操作は「"BW" または "WB" を削除する」となる。そうするとスコアは単に

(max(B の個数, W の個数) - min(B の個数, W の個数)) / 4

となってとても明快になる。 $K$ 個の "?" のうち、 $a$ 個を "B" に割り当てる方法は $C(K, a)$ 通りある。そしてそれらのスコアも簡単に求められる。 $a$ を順に動かしていけば OK。

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};

// Binomial coefficient
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;
BiCoef<mint> bc;

mint solve(int N, string S) {
    bc.init(N+1);
    for (int i = 0; i < N; ++i) {
        if (i % 2 != 0) continue;
        if (S[i] == 'b') S[i] = 'w';
        else if (S[i] == 'w') S[i] = 'b';
    }
    int B = 0, W = 0, K = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'b') ++B;
        else if (S[i] == 'w') ++W;
        else ++K;
    }
    if (K == 0) return (max(B, W) - min(B, W)) / 4;

    mint res = 0;
    for (int k = 0; k <= K; ++k) {
        int bnum = B + k, wnum = W + K - k;
        int score = max(bnum, wnum) - min(bnum, wnum);
        if (score % 4 != 0) continue;
        score /= 4;
        res += bc.com(K, k) * score;
    }
    return res / modpow(mint(2), K-1);
}

int main() {
    int N, M; 
    string S; 
    cin >> N >> M >> S;
    cout << solve(N, S) << endl;
}