Submission #21865521

---

Source Code Expand

#include <bits/stdc++.h>
#define i64 long long
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
using namespace std;

const int M = 3;
struct mint {
	int x; mint(int x) : x(x) {}
	friend mint operator + (const mint &a, const mint b)
	 {const int x = a.x + b.x; return mint(x >= M ? x - M : x);}
	friend mint operator - (const mint &a, const mint b)
	 {const int x = a.x - b.x; return mint(x < 0 ? x + M : x);}
	friend mint operator * (const mint &a, const mint b)
	 {return mint(1ll * a.x * b.x % M);}
};
int Pw(int a, int x = M - 2, int res = 1) {
	for (; x; x >>= 1, a = (mint(a) * a).x)
	 {if (x & 1) {res = (mint(res) * a).x;}}
	return res;
}

const int N = 4e5;
int n; string s;
struct par {
	int p, c;
	par(int x) : p(x), c(0) {while (!(p % M)) {p /= M, ++c;}}
};

int main() {
	// freopen("c.in", "r", stdin); //
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> s;
	int res = 0; par f = 1;
	rep(i, 0, n) {
		int x = s[i] == 'B' ? 0 : (s[i] == 'W' ? 1 : 2);
		// cout << f.p << ' ' << f.c << '\n'; //
		if (!f.c) {res = (res + mint(f.p) * x).x;}
		if (i == n - 1) {break;}
		par m = n - 1 - i, d = i + 1;
		f.p = (mint(f.p) * m.p * Pw(d.p)).x;
		f.c = f.c + m.c - d.c;
	}
	if (!(n & 1)) {res = (mint(0) - res).x;}
	cout << (res == 0 ? 'B' : (res == 1 ? 'W' : 'R')) << '\n';
	return 0;
}

/* 📌https://www.cnblogs.com/George1123/p/tips.html */

Submission Info

Judge Result