G - GCD Must Appear
問題文
正の整数 $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行ずつ出力してください。
3
3
10
400000
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}$ です。
この入力例は部分点の条件を満たします。
3
500001
1000000
100000000
749613433
339968887
529960284
この入力例は部分点の条件を満たしません。