← 返回题目列表

AtCoder · arc175_a

A. 勺子拿取问题

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

分数: 400 点

问题陈述

N 人们围坐在圆桌旁,并编号 1 to N 按逆时针顺序。每个人都有一只惯用手:左手或右手。

有 N 勺子编号 1 to N 在圆桌上,每对相邻的人之间放一个勺子。对于每个 1 \leq i \leq N,在人的左侧和右侧 i,有勺子 分别是 i 和 (i+1)。在这里,勺子 (N+1) 指勺子 1.

下图是 N = 4.

给你一个排列 (P_1, \dots, P_N) of (1, \dots, N)。按顺序 i=1,\dots,N, 人 P_i 将执行以下操作:

  • 如果左边或右边还有一把勺子,他们就会拿其中一个。
    • 如果两边都剩下勺子,他们会拿惯用手一侧的勺子。
  • 否则,他们什么也不做。

还给你一个字符串 S 长度 N 组成 L, R,和 ?。其中 2^N 优势手的可能组合,找出有多少满足以下所有条件,取模 998244353:

  • 如果 i- 第一个字符 S is L, 人 i 是左撇子。
  • 如果 i- 第一个字符 S is R, 人 i 是右撇子。
  • 大家演完了,大家都拿了勺子。

约束

  • 所有输入值均为整数。
  • 2 \leq N \leq 2 \times 10^5
  • (P_1, \dots, P_N) 是一个排列 (1, \dots, N).
  • S 是一个长度为 N 组成 L, R,和 ?.

输入

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

N
P_1 \dots P_N
S

输出

在一行中打印答案。


示例输入 1

3
1 2 3
L??

示例输出 1

2

当人 1, 2,和 3 分别为左撇子、左撇子、右撇子,执行的动作如下:

  • 人 1 开始行动。两边都有勺子,所以人 1 拿勺子 1 在左侧,与他们的惯用手相同。
  • 人 2 开始行动。两边都有勺子,所以人 2 拿勺子 2 在左侧,与他们的惯用手相同。
  • 人 3 开始行动。右边没有勺子,但是有勺子 3 留在左侧,所以他们拿了勺子 3。大家演完了,拿勺子。

这种优势牌组合满足条件。此外,当人 1, 2, 3 都是左撇子。


示例输入 2

3
1 3 2
R?L

示例输出 2

0

没有优势手的组合满足条件。


示例输入 3

12
6 2 9 3 1 4 11 5 12 10 7 8
????????????

示例输出 3

160