N Cut N Eat

respect:atgt2023ff

正の整数 が与えられます。

枚のピザがあります。このピザは半径 の円とみなすことができます。

このピザに対し、次の操作を 回行います。

• からの一様な乱数として つの実数を生成し、それを とする。ただし、 は生成した順序で区別される。
• から へ、ピザの元々の円周上を通る弧で反時計回りに結ぶ。
• その弧の端点 つとピザの中心をそれぞれ線分で結び、その つの線分と弧で囲まれている部分のピザを食べる。

最終的にピザを全て食べきることができる確率に をかけた値は整数になることが示せます。これを で割った余りを求めてください。ただし、乱数は全て独立であるものとします。

正の整数 が与えられます。

次のような操作を行います。

• まず、集合 を持つ。これは最初空である。
• 次の操作を 回行う。
  • からの一様な乱数として つの実数を生成し、それを とする。ただし、 は生成した順序で区別される。
  • ならば、 に を加算する。
  • を で置き換える。ただし、 は次のように定義される。
    • ならば、
    • ならば、

操作が終了した時点で となっている確率に をかけた値は整数になることが示せます。これを で割った余りを求めてください。ただし、乱数は全て独立であるものとします。

• は整数

N

操作が条件を満たす確率に をかけた値を で割った余りを出力してください。

2

4

最初の操作によってピザが全体を として だけ食べられた時、次の 回でピザを全て食べきる確率は となります。 最初の操作が終了した時点での は の一様な乱数と等しくなるため、問題の確率は となります。これに をかけた を出力してください。

1

0

一度の操作でピザを全て食べきる確率は です。

8

872904659

確率は であり、これに をかけた を で割った余りである を出力してください。

2536

524186647