問題一覧 > 通常問題

No.3479 Regions by Random Points

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : ぽえ / テスター : ルク 👑 loop0919 hiro1729
ProblemId : 13210 / yukicoder contest 494 オムニバス (順位表) / 自分の提出
問題文最終更新日: 2026-04-22 21:54:03
yukicoder contest 494 オムニバスの他の問題:

問題文

正方形の内部に、独立かつ一様ランダムに $N$ 個の点を打つ。
これらの $N$ 個の点どうしをすべて線分で結ぶとき、それらの線分によって正方形の内部が分割されてできる領域の個数の期待値 $\mathrm{mod}$ $998244353$ を求めよ。

期待値 $\mathrm{mod}$ $998244353$ の定義（クリックで開く）

この問題の制約下で求める期待値は必ず有理数になり、整数 $x ~ \big(x \not\equiv 0 ~ (\mathrm{mod} ~ 998244353)\big)$ と整数 $y$ を用いて $\frac{y}{x}$ で表せることが保証される。

このとき $xz \equiv y$ $(\mathrm{mod}$ $998244353)$ を満たす $0$ 以上 $998244353$ 未満の整数 $z$ が一意に存在するので、その値を解答すること。

制約

  • 入力はすべて整数である。
  • $1 \le N \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えを出力せよ。

サンプル

サンプル 1
入力
4
出力
526851191

$N=4$ のとき、答えは $\dfrac{169}{36}$ である。

サンプル 2
入力
1000000000
出力
751221712

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