問題一覧 > 通常問題

No.3479 Regions by Random Points

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

Problem Statement

$N$ points are placed independently and uniformly at random inside a square.
When all pairs of these $N$ points are connected by line segments, find the expected value, $\mathrm{mod}$ $998244353$, of the number of regions into which the interior of the square is divided by those segments.

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

Under the constraints of this problem, it is guaranteed that the expected value to be found is always a rational number and 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$ and less than $998244353$ satisfying $xz \equiv y$ $(\mathrm{mod}$ $998244353)$, so report that value as your answer.

Constraints

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

Input

The input is given from standard input in the following format.

$N$

Output

Output the answer.

Sample

Sample 1
Input
4
Output
526851191

When $N=4$, the answer is $\dfrac{169}{36}$.

Sample 2
Input
1000000000
Output
751221712

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