AT_abc238_h [ABC238Ex] Removing People

题目描述

有 $N$ 个人，编号从 $1$ 到 $N$，他们按 $1,2,\cdots,N$ 的顺序顺时针等间隔地围成一个环。每个人面朝的方向由一个长度为 $N$ 的仅包含 L 和 R 的字符串 $S$ 给出。对于每个 $i\ (1 \leq i \leq N)$，若 $S_i = \texttt{L}$，则第 $i$ 个人面朝逆时针方向；若 $S_i = \texttt{R}$，则第 $i$ 个人面朝顺时针方向。

以下操作重复 $N-1$ 次：

• 从剩下的人中等概率随机选择一人，从该人出发，移除其面朝方向上最近的剩余一人。移除时，花费的代价等于从选中人到被移除人的距离。

其中，从第 $i$ 个人到第 $j$ 个人（$i \neq j$）的距离定义如下：

1. 若第 $i$ 个人面朝顺时针方向：
   • 若 $i < j$，距离为 $j-i$
   • 若 $i > j$，距离为 $j-i+N$
2. 若第 $i$ 个人面朝逆时针方向：
   • 若 $i < j$，距离为 $i-j+N$
   • 若 $i > j$，距离为 $i-j$

请计算总花费的期望值，并对 $998244353$ 取模输出（见注释）。

输入格式

输入以如下格式从标准输入读入：

$N$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
LLR

输出 #1

831870297

输入输出样例 #2

输入 #2

10
RRRRRRLLRR

输出 #2

460301586

说明/提示

注释

可以证明，所求的期望值一定是有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示为 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

约束条件

• $2 \leq N \leq 300$
• $N$ 为整数
• $S$ 为仅包含 L 和 R 的长度为 $N$ 的字符串

样例解释 1

所求期望值为 $\frac{17}{6}$。由于 $831870297 \times 6 \equiv 17 \pmod{998244353}$，所以输出 $831870297$。例如，以下是一种操作顺序：

1. 选择第 $2$ 个人。第 $2$ 个人面前最近的剩余人为第 $1$ 个人，将其移除。
2. 再次选择第 $2$ 个人。此时第 $2$ 个人面前最近的剩余人为第 $3$ 个人，将其移除。

该操作顺序下的总代价为 $3(=1+2)$。

由 ChatGPT 4.1 翻译