← 返回题目列表

AtCoder · arc196_c

C. 强关联

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

分数: 900 点

问题陈述

有一个有向图 2N 顶点和 2N-1 边缘。 顶点已编号 1, 2, \ldots, 2N,以及 i-th 边是从顶点开始的有向边 i 到顶点 i+1.

给你一个长度-2N 字符串 S = S_1 S_2 \ldots S_{2N} 组成 N W和 N Bs。 顶点 i 的颜色为白色,如果 S_i is W,如果 S_i is B.

您将执行以下一系列操作:

  • 分区 2N 顶点变成 N 对,每对由一个白色顶点和一个黑色顶点组成。
  • 对于每一对,添加一条从白色顶点到黑色顶点的有向边。

打印数字,模数 998244353,将顶点划分为 N 配对,使得最终图是强连接的。

关于强连通性的注释

有向图是 强连接 当且仅当可以通过跟随边从任何顶点移动到任何顶点。

约束

  • 1 \le N \le 2\times 10^5
  • S 是长度 2N 字符串组成 N W和 N Bs。
  • N 是一个整数。

输入

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

N
S

输出

打印数字,模数 998244353,将顶点划分为 N 配对,以便最终图是强连接的。


示例输入 1

2
BWBW

示例输出 1

1

顶点 2,4 是白色的,并且顶点 1,3 是黑色的。

让 (u,v) 表示从顶点开始的边 u 到顶点 v.

如果我们将顶点配对为 (2,1), (4,3),最终的图有边 (1,2), (2,3), (3,4), (2,1), (4,3)。例如,在这种情况下,不可能从顶点出发 3 到顶点 1 通过跟随边,因此该图不是强连通的。

如果我们将顶点配对为 (2,3), (4,1),最终的图有边 (1,2), (2,3), (3,4), (2,3), (4,1)。该图是强连通的。

因此,正好有 1 配对满足条件的顶点的方法。


示例输入 2

4
BWWBWBWB

示例输出 2

0

无论如何配对顶点,都无法满足条件。


示例输入 3

9
BWWBWBBBWWBWBBWWBW

示例输出 3

240792