問題一覧 > 通常問題

No.3551 Regions by Random Points 2

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : ルク / テスター : 👑 loop0919 ぽえ
お気に入りにしたユーザー ProblemId : 13333 / 自分の提出
問題文最終更新日: 2026-04-22 22:23:10
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 500 (順位表) の他の問題:

Problem Statement

Perform the following operation $N$ times: place $2$ points independently and uniformly at random on the circumference of a circle, and connect them with a line segment.
Find the expected value, $\mathrm{mod}$ $998244353$, of the number of regions into which the interior of the circle is divided by these $N$ line segments.

Definition of expected value $\mathrm{mod}$ $998244353$ (click to open)

Under the constraints of this problem, the expected value to be found is always a rational number, and it is guaranteed that it can be expressed as $\frac{y}{x}$ using an integer $x ~ \big(x \not\equiv 0 ~ (\mathrm{mod} ~ 998244353)\big)$ and an integer $y$.

In this case, there exists a unique integer $z$ between $0$ inclusive and $998244353$ exclusive satisfying $xz \equiv y$ $(\mathrm{mod}$ $998244353)$, so output that value.

Constraints

  • $1 \le N \le 10^9$
  • All input values are integers.

Input

The input is given from Standard Input in the following format.

$N$

Output

Output the answer.

Sample

Sample 1
Input
8
Output
332748136
When $N=8$, the answer is $\dfrac{55}{3}$.
Sample 2
Input
1000000000
Output
952678484

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。