問題一覧 > 通常問題

No.1855 Intersected Lines

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 6424 / 自分の提出
問題文最終更新日: 2022-02-26 00:09:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 333 (灘高入試コンテスト2022) (順位表) の他の問題:

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.
Also, the score of a good division is defined as follows.
  • 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 R or B $\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もしくは右上の雲マークをクリックしてアカウントを作成してください。