前言

仔细想了想，考试的时候其实对正解有些思路，但自己认为正确性有问题，所以没这么写，大寄，考了倒2，呜呜呜┭┮﹏┭┮

T1 弹珠游戏

下面的匹配的含义： \(R\) 的匹配指 \(G,B\)，其中 \(R\) 为被匹配字母，\(G,B\)为匹配字母；\(G\) 的匹配指 \(R,B\) 以此类推。

我们用把每个人现在手里的牌用十进制来表示。有 \(R\) 的用 \(100\) 表示，有 \(G\) 的用 \(010\) 表示，有 \(B\) 的用 \(001\) 表示。考虑贪心，我们从前往后枚举，先确定一个点，在后面我们若枚举到与之匹配的两个点，那我们直接拿走被匹配的字母和匹配字母，用乘法原理乘上，不再管它这一组。具体请看代码实现。

正确性证明：若我们的 \(R\) 在位置 \(1,3\)， \(G\) 在位置 \(2,4\)，\(B\) 在位置 \(5,6\)。此时若我们固定两个 \(R\)，则找到位置 \(5\) 时发现第一个匹配，我们这时可以将找到的匹配给两个位置 \(1,3\) 的 \(R\)，那我们这时该给谁呢？两个都行，因为我们 \(R\) 的所有匹配的位置是一定确定的，我们可以将题目的所有人的不满意之和列出式子

化简：

其中 \(posr\) 表示匹配的右边字母的位置，\(posl\) 表示被匹配的左边字母的位置。

如果我们都能选的话，按先前的说法为什么将匹配给先出现的被匹配字母？？这就涉及到了代码实现。我们有如下代码

		if (num[i] == 100) {
			if (cnt[011]) {
				ans = (ans * cnt[011]) % mod;
				cnt[111] ++;
				cnt[011] --;
			}
			else if (cnt[010]) {
				//这里面不会出现cnt[010]和cnt[001]都存在值得情况
				//因为存在cnt[001]或cnt[010]的一定会并到cnt[010]或cnt[001]里面成为cnt[011] 
=				ans = (ans * cnt[010]) % mod;
				cnt[110] ++;
				cnt[010] --;
			}
			else if (cnt[001]) {
				ans = (ans * cnt[001]) % mod;
				cnt[101] ++;
				cnt[001] --;
			}
			if (cnt[000]) {
				ans = (ans * cnt[000]) % mod;
				cnt[100] ++;
				cnt[000] --;
			}
		}

其中 \(i\) 表示枚举到了第 \(i\) 位。我们为什么要先加匹配字母是两个的？？

首先，由于我们推导了上面的式子，所以我们可以发现拿最后一个匹配的时候先拿哪个 \(posr\) 所代表的匹配并不会影响我们的不满意度之和，但我们如果将现在的珠子给只存在一个匹配的人，我们此时最后一个拿的珠子的位置就不再是我们原先 \(posl\) 里面对应的 \(posr\) 了。如：若我们拿的顺序是 \(R,G,B\)，如果在拿完 \(R\) 后拿 \(B\) 肯定是不对的。

所以就能得到代码蜡

#include <iostream>
#include <cstdio> 
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
typedef long long ll;
const ll mod = 998244353;

int n;
char ch[1100000];
ll cnt[3000], ans = 1, num[1100000];

int main() {
	scanf("%d", &n);
    ch[1] = getchar();
    while (ch[1] != 'R' && ch[1] != 'B' && ch[1] != 'G') {
        ch[1] = getchar();
    }
    for (int i = 2; i <= n * 3; ++ i) {
        ch[i] = getchar();
    }
    for (int i = 1; i <= n * 3; ++ i) {
    	if (ch[i] == 'R') num[i] = 100;
    	if (ch[i] == 'G') num[i] = 10;
    	if (ch[i] == 'B') num[i] = 1;
	}
	cnt[0] = n;
	for (int i = 1; i <= n * 3; ++ i) {
		if (num[i] == 100) {
			if (cnt[011]) {
				ans = (ans * cnt[011]) % mod;
				cnt[111] ++;
				cnt[011] --;
			}
			else if (cnt[010]) {
				//这里面不会出现cnt[010]和cnt[001]都存在值得情况
				//因为存在cnt[001]或cnt[010]的一定会并到cnt[010]或cnt[001]里面成为cnt[011] 
				ans = (ans * cnt[010]) % mod;
				cnt[110] ++;
				cnt[010] --;
			}
			else if (cnt[001]) {
				ans = (ans * cnt[001]) % mod;
				cnt[101] ++;
				cnt[001] --;
			}
			if (cnt[000]) {
				ans = (ans * cnt[000]) % mod;
				cnt[100] ++;
				cnt[000] --;
			}
		}
		else if (num[i] == 10) {
			if (cnt[101]) {
				ans = (ans * cnt[101]) % mod;
				cnt[111] ++;
				cnt[101] --;
			}
			else if (cnt[100]) {
				ans = (ans * cnt[100]) % mod;
				cnt[110] ++;
				cnt[100] --;
			}
			else if (cnt[001]) {
				ans = (ans * cnt[001]) % mod;
				cnt[011] ++;
				cnt[001] --;
			}
			else {
				ans = (ans * cnt[000]) % mod;
				cnt[010] ++;
				cnt[000] --;
			}
		}
		else if (num[i] == 1) {
			if (cnt[110]) {
				ans = (ans * cnt[110]) % mod;
				cnt[111] ++;
				cnt[110] --;
			}
			else if (cnt[010]) {
				ans = (ans * cnt[010]) % mod;
				cnt[011] ++;
				cnt[010] --;
			}
			else if (cnt[100]) {
				ans = (ans * cnt[100]) % mod;
				cnt[101] ++;
				cnt[100] --;
			}
			else {
				ans = (ans * cnt[000]) % mod;
				cnt[001] ++;
				cnt[000] --;
			}
		}
	}
	cout << ans << endl;
	return 0;
}