分数: 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) 定义如下。
- 当人 i 面向顺时针方向:
- j-i if i \lt j;
- j-i+N if i \gt j.
- 当人 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 。
以下是一种可能的情况,供您参考。
- 人 选择 2 。从 Person 看到的最近的人 2 圆圈中剩余的是人 1,被从圈子中删除。 再次选择
- 人 选择 2 。从 Person 看到的最近的人 2 圆圈中剩余的是人 3,被从圈子中删除。 再次选择
在这种情况下,产生的总成本是 3(=1+2).
示例输入 2
10 RRRRRRLLRR
示例输出 2
460301586