Mister雑記

競プロやります。

JSC2019予選 - C 「Cell Inversion」 (500)

atcoder.jp

問題

長さ 2NのBとWからなる文字列 Sが与えられる。この文字列に対して、以下の操作を N回行う。

  • まだ選んでいない2つのindexを選ぶ( l, rとする)。
  •  S[l, r]を全て反転させる。

最終的に全部Wになるような操作列の個数を求めよ。

制約

  •  1 \leq N \leq 10^5

考察

 N個のマッチングを決めてしまえば、最終的な文字列は選ぶ順番に依存しない。 そこでマッチングを左から決めていくことを考える。

 S_1に着目すると、これは絶対に一度だけ反転される。よって S_1がWである場合、答えは 0になる。  S_1がBである場合は1とペアになるindexがあるが、これは後で決めることにする。

次に S_2に着目すると、これの反転する回数は以下の2パターンがある。

  • 1のペアを2にする場合は1回。
  • 2と3以降のどれかをペアにする場合は2回。

このうち S_2がWになるのはいずれか一方のみである。

これと同じことが任意のindexで言える。 つまり、 S_iを見ている時点で右端を保留しているペアが K個ある場合、

  • 保留中のペアのうちいずれか1つの右端を iにする場合は K回。
    • どれと iをペアにするかが K通りある。
    •  Kは1減る。
  •  iをペアの左端にする場合は K + 1回。
    •  Kは1増える。

このうち S_iがWになるのはいずれか一方のみである。 ただし K = 0の場合前者は選べない、つまり条件を満たすマッチングはない。

これを先頭から繰り返せばマッチングの数が求まる。 ただし最終的に K \neq 0になったときは、これはinvalidなマッチングなので答えは0になることに注意。

最後にマッチングをどの順に適用するか、つまり N!を掛ければ答えとなる。

実装例

atcoder.jp

using namespace std;
using mint = ModInt<1000000007>;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int K = 0;
    mint ans = 1;
    for (auto c : S) {
        if ((c == 'W') == (K % 2 == 0)) {
            // 保留中のどれかの右端にする
            ans *= K;
            if ((--K) < 0) break;
        } else {
            // iを左端にする 右端は保留
            ++K;
        }
    }

    if (K != 0) {
        // invalidなマッチング
        cout << 0 << endl;
        return 0;
    }

    // N!を掛けて出力
    for (int i = 1; i <= N; ++i) ans *= i;
    cout << ans << endl;
    return 0;
}