n 人站成一个圆圈,按顺时针方向依次为 1,2,⋯,n。
每个人面对的方向由长度为 n 的字符串 S 给出。对于第 i 个人,如果 Si=L,则 i 面向逆时针方向。如果是 Si=R,则面向顺时针方向。
重复 n−1 次以下操作。
- 以相等的概率从剩余的人中选择一个,并从圆中移除离被选中的人最近的人。这样做的代价等于被选中的人到被移除的人的距离。
定义从 i 到 j(i=j)的距离为:
- 当 i 朝向顺时针方向时:
- 如果 i<j,则为 j−i;
- 如果 i>j,则为 j−i+n。
- 当 i 朝向逆时针方向时:
- 如果 i<j,则为 i−j+n ;
- 如果 i>j,则为 i−j 。
求 n−1 次操作后代价之和的期望值,对 998244353 取模。
$n$ 人站成一个圆圈,按顺时针方向依次为 $1, 2, \cdots, n$。
每个人面对的方向由长度为 $n$ 的字符串 $S$ 给出。对于第 $i$ 个人,如果 $S_i = \texttt{L}$,则 $i$ 面向逆时针方向。如果是 $S_i = \texttt{R}$,则面向顺时针方向。
重复 $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$ 。
求 $n-1$ 次操作后代价之和的期望值,对 $998244353$ 取模。