前言
仔细想了想，考试的时候其实对正解有些思路，但自己认为正确性有问题，所以没这么写，大寄，考了倒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\) 的所有匹配的位置是一定确定的，我们可以将题目的所有人的不满意之和列出式子
\[\sum (posr-posl) \]化简：
\[\sum posr - \sum posl \]其中 \(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;
}