← 返回题目列表

AtCoder · agc037_b

B. RGB 球

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

我们有 3N 彩色球,其 ID 来自 1 to 3N。 一个字符串 S 长度 3N 代表球的颜色。球的颜色 i 为红色,如果 S_i is R,如果为绿色 S_i is G,如果 S_i is B。有 N 红球, N 绿球,以及 N 蓝色球。

高桥将分发这些 3N 球到 N 人,以便每人获得一颗红球、一颗蓝球和一颗绿球。 人们想要ID彼此靠近的球,所以他还要满足以下条件:

  • 让 a_j < b_j < c_j 是接收者收到的球的 ID j- 按升序排列的第一个人。
  • 然后, \sum_j (c_j-a_j) 应尽可能小。

求高桥分配球的方式数。由于答案可能很大,因此对它进行模计算 998244353。 当且仅当一个人收到不同组的球时,我们才会考虑两种不同的球分配方式。

约束

  • 1 \leq N \leq 10^5
  • |S|=3N
  • S 包括 R, G,和 B,并且每个字符都出现 N 次 S.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印高桥可以分配球的方式数,模 998244353.


示例输入 1

3
RRRGGGBBB

示例输出 1

216

的最小值 \sum_j (c_j-a_j) is 18 例如,当球分布如下时:

  • 第一个人获得球 1, 5,和 9.
  • 第二个人得到球 2, 4,和 8.
  • 第三人获得球 3, 6,和 7.

示例输入 2

5
BBRGRRGRGGRBBGB

示例输出 2

960