No.1855 Intersected Lines
Problem Statement
There are $2N$ points equally spaced on a circle, numbered $1,2, \cdots ,2N$ in clockwise order.
Point $i$ is painted red if the $i$-th character of the string $S$ is R, and blue if it is B.
Here, a way of dividing the $2N$ points on the circle into $N$ pairs is called a good division if it satisfies the following.
- For each of the $N$ pairs, the $2$ points in the pair have the same color.
- For each of the $2N$ points, exactly $1$ pair contains that point.
- For every pair, draw the line segment connecting the $2$ points of the pair. The score is the number of ways to choose $2$ line segments from the resulting $N$ line segments such that the chosen $2$ segments intersect.
Find the expected value of the score over good divisions. It is guaranteed that a good division exists for the given input.
Here, it can be proved that the answer can be expressed as $\frac{P}{Q}$ using $2$ coprime integers $P,Q$ that are at least $0$, and that an integer $R$ satisfying $R \times Q \equiv P (\mathrm{mod}\ 998244353)$ and $0 \leq R < 998244353$ is uniquely determined. Print this $R$.
In this problem, $S$ is given as follows.
- A positive integer $X$, characters $C_1,C_2, \cdots , C_X$, and numbers $V_1,V_2, \cdots ,V_X$ are given. Let $S_i$ be the string consisting of $C_i$ repeated $V_i$ times. Then $S$ is the concatenation of $S_1,S_2 , \cdots ,S_X$ in this order.
Input
$N\ \ X$
$C_1\ \ V_1$
$C_2\ \ V_2$
$\vdots$
$C_X\ \ V_X$
- $1 \leq N \leq 499122176 = \frac{998244353-1}{2}$
- $1 \leq X \leq 4 \times 10^5$
- $C_i$ is
RorB$\left( 1 \leq i \leq X \right)$ - $1 \leq V_i \leq 2N$ $\left( 1 \leq i \leq X \right)$
- $V_1 + V_2 + \cdots + V_X = 2N$
- $N,X,V_i$ are integers
- A good division exists
Output
Print $R$ as determined in the problem statement, followed by a newline.
Sample
Sample 1
Input
2 4
R 1
B 1
R 1
B 1
Output
1
$S$ is RBRB. There is $1$ good division: $\{1,3 \}, \{2,4 \}$.
The score of this good division is $1$ as shown in the figure above, so the answer is $1$. (The topmost point is point $1$.)
Sample 2
Input
4 5
B 4
R 1
B 1
B 1
R 1
Output
798595485
$S$ is BBBBRBBR. For example, the good division $\{1,6 \}, \{2,4 \} , \{3,7 \} , \{5,8 \}$ has a score of $4$ as shown in the figure above. The answer is $\frac{13}{5}$.
Sample 3
Input
24 19
B 3
R 1
B 2
R 1
B 1
R 3
B 2
R 1
B 4
R 1
B 1
R 2
B 1
R 7
B 7
R 2
B 6
R 2
B 1
Output
865923553
$S$ is BBBRBBRBRRRBBRBBBBRBRRBRRRRRRRBBBBBBBRRBBBBBBRRB.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂