問題概要

長さ $N$ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を $N-1$ 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。

それぞれの隣り合う 2 文字に対して
- それらが同じ文字ならば、その文字を対応させる
- それらが異なる文字ならば、残りの文字を対応させる

f:id:drken1215:20210611222958p:plain

制約

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

考えたこと

この手の問題は、まずは

"B" → 0
"W" → 1
"R" → 2

という風に変換して考えたくなる。そしてきっと操作の前後で、「なんらかの量」を考えると、それが不変になってるんだろうな...という想像を働かせていくのが良さそう。

さて、0, 1, 2 で考えると、

(0, 0) → 0
(1, 1) → 1
(2, 2) → 2
(0, 1), (1, 0) → 2
(1, 2), (2, 1) → 0
(2, 0), (0, 2) → 1

となっている。mod. 3 で考えると良さそうだとあたりをつけると、

$(a, b)$ → $- (a + b)$

となっていることに気づく。たとえば

(1, 1) → -2 ≡ 1 (mod. 3)
(1, 2) → -3 ≡ 0 (mod. 3)

という感じ。

二項係数の重複度

$N = 5$ くらいで具体的に書き出してみると、

$(a, b, c, d, e)$
→ $(-a-b, -b-c, -c-d, -d-e)$
→ $(a+2b+c, b+2c+d, c+2d+e)$
→ $(-a-3b-3c-d, -b-3c-3d-e)$
→ $(a+4b+6c+4d+e)$

という風になっていく。一般に、パスカルの三角形と同じ原理で、 $c_{0}, c_{1}, \dots, c_{N-1}$ に対して、 ${}_{N-1}{\rm C}_{0}, {}_{N-1}{\rm C}_{1}, \dots, {}_{N-1}{\rm C}_{N-1}$ を係数にかけて総和をとった値になるのだ。ただし、 $N$ が偶数のときは $-1$ 倍になる。

まとめ

以上から、

${}_{N-1}{\rm C}_{r}$ (mod. 3)

が計算できればよいことがわかった。これは任意 mod nCr のライブラリを使った。

全体として計算量は、 $O(N)$ になる。

github.com

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

// mod function
long long mod(long long a, long long mod) {
    return (a % mod + mod) % mod;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    long long 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);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

// binomial coefficient
struct BiCoef {
    // max size of n of nCr
    int n_;
    
    // pm = p^k, p is prime
    // mod pm
    long long p_, pm_;
    
    // i! = p^ord[i] * fact[i] (mod. m)
    vector<long long> ord_, fact_;

    // constructor
    BiCoef(int n) : n_(n), ord_(n), fact_(n) {}
    BiCoef(long long p, long long pm, int n) :
        n_(n), p_(p), pm_(pm), ord_(n), fact_(n) {
        init(p, pm);
    }
    void init(int n) {
        ord_.resize(n);
        fact_.resize(n);
    }
    void init(long long p, long long pm) {
        p_ = p, pm_ = pm;
        ord_[0] = ord_[1] = 0;
        fact_[0] = fact_[1] = 1;
        for (int i = 2; i < n_; i++) {
            long long add = 0;
            long long ni = i;
            while (ni % p == 0) ++add, ni /= p;
            ord_[i] = ord_[i-1] + add;
            fact_[i] = fact_[ni-1] * ni % pm;
        }
    }
    void init(long long p, long long pm, int n) {
        init(n);
        init(p, pm);
    }

    // nCr mod. pm
    long long com(long long n, long long r) {
        if (n < 0 || r < 0 || n < r) return 0;
        long long e = ord_[n] - ord_[r] - ord_[n-r];
        long long res = fact_[n] * modinv(fact_[r] * fact_[n-r] % pm_, pm_) % pm_;
        res = res * modpow(p_, e, pm_) % pm_;
        return res;
    }
};

string check = "BWR";
int main() {
    int N;
    string S;
    cin >> N >> S;

    BiCoef bf(3, 3, N);
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        int val = 0;
        if (S[i] == 'W') val = 1;
        else if (S[i] == 'R') val = 2;
        res += bf.com(N - 1, i) * val % 3;
    }
    res %= 3;
    if (N % 2 == 0) res = (3 - res) % 3;
    cout << check[res] << endl;
}