102387: [AtCoder]ABC238 Ex - Removing People

Problem Statement

$N$ people numbered $1$ to $N$ are standing in a circle, in the clockwise order of Person $1$, Person $2$, $\cdots$, Person $N$. The direction each person faces is given by a string $S$ of length $N$. For each $i$ $(1 \leq i \leq N)$, Person $i$ is facing in the counter-clockwise direction if $S_i = $ L, and clockwise direction if $S_i = $ R.

The following operation will be repeated $N-1$ times.

• Choose one of the remaining people with equal probability, and remove from the circle the nearest person seen from the chosen person. This incurs a cost equal to the distance from the chosen person to the removed person.

Here, the distance from Person $i$ to Person $j$ $(i \neq j)$ is defined as follows.

1. When Person $i$ is facing in the clockwise direction:
   • $j-i$ if $i \lt j$;
   • $j-i+N$ if $i \gt j$.
2. When Person $i$ is facing in the counter-clockwise direction:
   • $i-j+N$ if $i \lt j$;
   • $i-j$ if $i \gt j$.

Find the expected value of the total cost incurred, modulo $998244353$ (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is expressed as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $2 \leq N \leq 300$
• $N$ is an integer.
• $S$ is a string of length $N$ consisting of L and R.

Input

Input is given from Standard Input in the following format:

$N$
$S$

Output

Print the answer.

Sample Input 1

3
LLR

Sample Output 1

831870297

The sought expected value is $\frac{17}{6}$. We have $831870297 \times 6 \equiv 17\pmod{998244353}$, so $831870297$ should be printed.

For your reference, here is one possible scenario.

1. Person $2$ is chosen. The nearest person seen from Person $2$ remaining in the circle is Person $1$, who gets removed from the circle.
2. Person $2$ is chosen again. The nearest person seen from Person $2$ remaining in the circle is Person $3$, who gets removed from the circle.

In this case, the total cost incurred is $3(=1+2)$.

Sample Input 2

10
RRRRRRLLRR

Sample Output 2

460301586

问题描述

编号为1到N的N个人站成一个圆形，按顺时针方向为第1个人，第2个人，…，第N个人。每个人面向的方向由一个长度为N的字符串S给出。对于每个i $(1 \leq i \leq N)$，如果$S_i = $ L，那么第i个人面向逆时针方向；如果$S_i = $ R，那么第i个人面向顺时针方向。

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

• 以相等的概率选择剩下的一个人，并从圈中移除被选中的人所看到的最近的人。这将产生等于从被选中的人到被移除的人的距离的成本。

这里，从第i个人到第j个人 $(i \neq j)$ 的距离定义如下。

1. 当第i个人面向顺时针方向时：
   • 如果$i \lt j$，则为$j-i$；
   • 如果$i \gt j$，则为$j-i+N$。
2. 当第i个人面向逆时针方向时：
   • 如果$i \lt j$，则为$i-j+N$；
   • 如果$i \gt j$，则为$i-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是一个由L和R组成的长度为N的字符串。

输入

输入从标准输入以以下格式给出：

$N$
$S$

输出

打印答案。

样例输入1

3
LLR

样例输出1

831870297

所求的期望值为$\frac{17}{6}$。我们有$831870297 \times 6 \equiv 17\pmod{998244353}$，因此应该打印831870297。

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

1. 选择第2个人。在圈中剩下的从第2个人所看到的最近的人是第1个人，他从圈中被移除。
2. 再次选择第2个人。在圈中剩下的从第2个人所看到的最近的人是第3个人，他从圈中被移除。

在这种情况下，产生的总成本为$3(=1+2)$。

样例输入2

10
RRRRRRLLRR

样例输出2

460301586