respect:atgt2023ff
問題文(ストーリーあり)
正の整数 N が与えられます。
1 枚のピザがあります。このピザは半径 1 の円とみなすことができます。
このピザに対し、次の操作を N 回行います。
- [0,2π) からの一様な乱数として 2 つの実数を生成し、それを x,y とする。ただし、x,y は生成した順序で区別される。
- (sinx,cosx) から (siny,cosy) へ、ピザの元々の円周上を通る弧で反時計回りに結ぶ。
- その弧の端点 2 つとピザの中心をそれぞれ線分で結び、その 2 つの線分と弧で囲まれている部分のピザを食べる。
最終的にピザを全て食べきることができる確率に (2N)! をかけた値は整数になることが示せます。これを 998244353 で割った余りを求めてください。ただし、乱数は全て独立であるものとします。
厳密な問題文
正の整数 N が与えられます。
次のような操作を行います。
- まず、集合 S を持つ。これは最初空である。
- 次の操作を N 回行う。
- [0,2π) からの一様な乱数として 2 つの実数を生成し、それを x,y とする。ただし、x,y は生成した順序で区別される。
- x>y ならば、y に 2π を加算する。
- S を S∪{f(θ)∣x≤θ≤y} で置き換える。ただし、f(θ) は次のように定義される。
- θ<2π ならば、f(θ)=θ
- 2π≤θ ならば、f(θ)=θ−2π
操作が終了した時点で S={θ∣0≤θ<2π} となっている確率に (2N)! をかけた値は整数になることが示せます。これを 998244353 で割った余りを求めてください。ただし、乱数は全て独立であるものとします。
制約
- N は整数
- 1≤N≤3000
入力
出力
操作が条件を満たす確率に (2N)! をかけた値を 998244353 で割った余りを出力してください。
サンプル
最初の操作によってピザが全体を 1 として p だけ食べられた時、次の 1 回でピザを全て食べきる確率は 2p2 となります。
最初の操作が終了した時点での p は [0,1) の一様な乱数と等しくなるため、問題の確率は ∫012p2dp=61 となります。これに (2N)!=24 をかけた 4 を出力してください。
一度の操作でピザを全て食べきる確率は 0 です。
確率は 259459200244583167 であり、これに 16! をかけた 19723186586880 を 998244353 で割った余りである 872904659 を出力してください。