ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

G - GCD Must Appear

Flavor
4
s
1024
MB
700
点

問題文

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

$1,2,\ldots,N$ を並べ替えた順列を、$N!$ 通りの中から等確率で1つ選び、$P=(P_1,P_2,\ldots,P_N)$ とします。
各整数 $k$($1\leq k\leq N$)について、

$G_k=\gcd(P_1,P_2,\ldots,P_k)$

と定めます。ここで、$\gcd$ は最大公約数を表します。

すべての整数 $k$($1\leq k\leq N$)に対して、$P_1,P_2,\ldots,P_k$ の中に $G_k$ と等しい要素が存在するとき、$P$ を良い順列と呼びます。

選ばれた順列 $P$ が良い順列である確率を、$998244353$ を法として求めてください。

確率を$998244353$ を法として求めるとは

この問題で求める確率は必ず有理数になることが証明できます。この問題の制約下では、求める確率を既約分数 $\frac ab$ で表したとき、$b$ が $998244353$ で割り切れないことが保証されます。このとき $bx\equiv a\pmod{998244353}$ を満たす $0\le x<998244353$ なる整数 $x$ が一意に定まるので、その $x$ を求めてください。

テストケースは $T$ 個与えられます。各テストケースについて答えを求めてください。

制約

  • $1\leq T\leq5$
  • $1\leq N$
  • 全テストケースにおける $N$ の総和は $998244353$ 未満である。
  • 入力はすべて整数である。

部分点

この問題には部分点が設定されています。

  • 全テストケースにおける $N$ の総和が $5\times10^5$ 以下であるデータセットに正解すると、部分点として500点が与えられます。

入力

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

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられます。

$N$

出力

各テストケースについて、選ばれた順列が良い順列である確率を、問題文で指定した形式で、入力された順に1行ずつ出力してください。

入力例 1
3 3 10 400000
出力例 1
665496236 941439496 903198672

1番目のテストケースでは、良い順列は $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(3,1,2)$ の4個です。
順列は全部で $3!=6$ 個あるため、求める確率は $\frac46=\frac23$ です。
$3\times665496236\equiv2\pmod{998244353}$ なので、$665496236$ を出力します。

例えば、$(2,3,1)$ では $G_2=\gcd(2,3)=1$ ですが、最初の2要素に $1$ が含まれないため、良い順列ではありません。

2番目のテストケースでは、良い順列は $835488$ 個あり、求める確率は $\frac{835488}{10!}=\frac{967}{4200}$ です。

この入力例は部分点の条件を満たします。

入力例 2
3 500001 1000000 100000000
出力例 2
749613433 339968887 529960284

この入力例は部分点の条件を満たしません。

提出
C++23 (g++ 12.2.0)