/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの番号を付けられた N 人の人が、人 1、人 2、\cdots、人 N の順に時計回りに円環状に等間隔に並んでいます。
それぞれの人が向いている方向は L または R のみからなる長さ N の文字列 S で表されます。各 i \, (1 \leq i \leq N) に対し、S_i = L ならば人 i は反時計回りの方向を向いており、S_i = R ならば人 i は時計回りの方向を向いています。
以下の操作を N-1 回繰り返します。
- 残っている人の中から等確率で一人を選び、その人から見て一番手前にいる残っている人を円環から除く。このとき、選んだ人から除かれる人までの距離と同じだけのコストがかかる。
ここで、人 i から人 j (i \neq j) までの距離を以下のように定義します。
- 人 i が時計回りの方向を向いている場合
- i \lt j ならば j-i
- i \gt j ならば j-i+N
- 人 i が反時計回りの方向を向いている場合
- i \lt j ならば i-j+N
- i \gt j ならば i-j
合計コストの期待値を\mod 998244353 で求めてください（注記参照）。
注記
求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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 を出力します。
なお、例えば以下のような操作手順が考えられます。
- 人 2 を選ぶ。人 2 から見て一番手前にいる、円環に残っている人は人 1 であるため、人 1 を円環から除く。
- 人 2 をもう一度選ぶ。人 2 から見て一番手前にいる、円環に残っている人は人 3 であるため、人 3 を円環から除く。
この操作手順における合計コストは 3(=1+2) となります。
入力例 2
10 RRRRRRLLRR
出力例 2
460301586
Score : 600 points
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.
- When Person i is facing in the clockwise direction:
- j-i if i \lt j;
- j-i+N if i \gt j.
- 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
LandR.
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.
- Person 2 is chosen. The nearest person seen from Person 2 remaining in the circle is Person 1, who gets removed from the circle.
- 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