区間反転操作問題シリーズ！！！
それにしてもいろんな見方ができる問題な気がする。

問題概要

長さ $2N$ の 'B', 'W' からなる文字列 $S$ があたえられる。今この文字列に $N$ 回の操作を行う。

まだ選んでいない 2 マス $l \lt r$ を選んで区間 [ $l, r$ ] の 'B' と 'W' とを入れ替える

最終結果が 'W' 一色になるような操作が何通りあるかを 1000000007 で割ったあまりで求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

本質的には $N$ 組の組分けを数える問題なので、順序は気にしてくて OK。順序については最後に $N!$ をかけることにする。

さて各マスについて、それがいずれかの区間反転操作において区間の左端になるか右端になるか、のいずれかになるが、

たとえば $N = 3$ で L, L, R, L, R, R という具合に各マスについて区間操作の左端になるか右端になるかを決めると
最終結果にいたるまでの各マスの反転回数は 1, 2, 2, 2, 2, 1 と一意に決まる

ということがわかる。そして逆になんと、

各マスの反転回数の偶奇に着目すると、その反転回数を実現する L, R の決め方も一意に決まる

ということもわかる。具体的には

L が来たら +1
R が来たら、そのマスについては変化なしで、次のマスに入るときに -1 する

という感じ。そして反対に、各マスの反転回数を決めると、各マスの L, R の決め方も存在するならば一意になる。さらにいうと反転回数の偶奇を決めるだけでも、各マスの L, R の決め方が一意に決まる。具体的には

前回が L のとき
- 前回と反転回数のパリティが等しかったら、R
- 前回と反転回数のパリティが異なっていたら、L
前回が R のとき
- 前回と反転回数のパリティが等しかったら、L
- 前回と反転回数のパリティが異なっていたら、R

となる。なお、もっと天才的で明快な方法がりんごさんの解説にある。

www.youtube.com

L, R に帰着したら

残りの問題は

L, L, R, L, R, R

といった LR 列について L を左側、R を右側として組分けする方法を数え上げる問題になる。これは、カッコ列の整合性判定問題とよく似ている。カッコの対応の交差を許したときの、対応方法の個数を数える問題といえる。

「num := まだ R とペアになっていない L の個数」として、
左から順に見ていったときに R が登場した時点で、num を掛け算して、num を減らす

というふうにしていけば OK。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int MOD = 1000000007;

long long solve(int N, const string &S) {
    if (S[0] == 'W') return 0;

    char prev = 'L';
    int num = 1;
    long long res = 1;
    for (int i = 1; i < N*2; ++i) {
        if (prev == 'L') {
            if (S[i-1] == S[i]) prev = 'R', res *= num--, res %= MOD;
            else prev = 'L', ++num;
        }
        else {
            if (S[i-1] == S[i]) prev = 'L', ++num;
            else prev = 'R', res *= num--, res %= MOD;
        }
    }
    if (num != 0) return 0;

    for (long long i = 1; i <= N; ++i) res = (res * i) % MOD;
    return res;
}

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