← 返回题目列表

AtCoder · abc238_h

Ex. 移除人员

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

分数: 600 点

问题陈述

N 人数 1 to N 站成一圈,按照人物的顺时针顺序 1, 人 2, \cdots, 人 N。 每个人面对的方向由字符串给出 S 长度 N。对于每个 i (1 \leq i \leq N), 人 i 面向逆时针方向,如果 S_i = L,并且顺时针方向如果 S_i = R.

将重复以下操作 N-1 次。

  • 以等概率选择剩余的人中的一个,并从圆圈中删除与所选人最近的人。 这会产生等于从所选人员到被移除人员的距离的成本。

这里是与Person的距离 i 至人 j (i \neq j) 定义如下。

  1. 当人 i 面向顺时针方向:
    • j-i if i \lt j;
    • j-i+N if i \gt j.
  2. 当人 i 面向逆时针方向:
    • i-j+N if i \lt j;
    • i-j if i \gt j.

求所发生的总成本的预期值,以模数为模 998244353 (见注释)。

注释

可以证明,求的期望值始终是有理数。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,有一个唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.

约束

  • 2 \leq N \leq 300
  • N 是一个整数。
  • S 是一个长度为的字符串 N 组成 L 和 R.

输入

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

N
S

输出

打印答案。


示例输入 1

3
LLR

示例输出 1

831870297

寻求的期望值为 \frac{17}{6}。我们有 831870297 \times 6 \equiv 17\pmod{998244353},所以 831870297 。

以下是一种可能的情况,供您参考。

  1. 人 选择 2 。从 Person 看到的最近的人 2 圆圈中剩余的是人 1,被从圈子中删除。 再次选择
  2. 人 选择 2 。从 Person 看到的最近的人 2 圆圈中剩余的是人 3,被从圈子中删除。 再次选择

在这种情况下,产生的总成本是 3(=1+2).


示例输入 2

10
RRRRRRLLRR

示例输出 2

460301586