No.3578 隣接転倒数
p-adic問題文
入力に $2$ 個の正整数 $N, B$ が与えられます。
ここでは $N$ 以下の正整数からなる長さ $N$ の順列を単にサイズ $N$ の順列と呼びます。
サイズ $N$ の順列 $p$ に対し、$f(p)$ で $p_i > p_{i+1}$ を満たす $N$ 未満の正整数 $i$ の個数を表します。
ただしサイズ $N$ の順列 $p$ と $N$ 以下の各正整数 $i$ に対し、$p_i$ で $p$ の $i$ 個目の成分を表します。
サイズ $N$ の順列 $p$ をランダムに（どれが選ばれるかが等確率になるように）選ぶ時の $f(p)$ の期待値の法 $B$ での値が存在するか否かを判定し、存在する場合はその値を求めてください。
ただし有理数 $x$ の法 $B$ での値とは、以下の条件を満たす一意な整数 $r$ を表します。
- $0 \leq r < B$ である。
- $x$ の既約分数表示を $\frac{n}{d}$（$d$ は正整数、$n$ は $d$ と互いに素な整数）と表した時、$n \equiv dr \pmod{B}$ である。
なおこのような $r$ が存在する必要十分条件は、$d$ と $B$ が互いに素である（双方を割り切る素数が存在しない）ことです。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
$N$ $B$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^9$ を満たす整数である。
出力
$f(p)$ の期待値の法 $B$ での値が存在するならば、それを $1$ 行に出力してください。
存在しないならば、NaNと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1
出力
0
サイズ $N = 1$ の順列 $p$ は $(1)$ のみです。$f((1)) = 0$ であるので、$f(p)$ の期待値は $\frac{0}{1} = 0$ です。$0$ の法 $B = 1$ での値 $0$ を出力してください。
サンプル2
入力
2 2
出力
NaN
サイズ $N = 2$ の順列 $p$ は $(1,2)$ と $(2,1)$ があります。$f((1,2)) = 0$ かつ $f((2,1)) = 1$ であるので、$f(p)$ の期待値は $\frac{0+1}{2} = \frac{1}{2}$ です。$\frac{1}{2}$ の法 $B = 2$ での値は存在しないのでNaNと出力してください。
サンプル3
入力
3 5
出力
1
サイズ $N = 3$ の順列 $p$ は $(1,2,3)$ と $(1,3,2)$ と $(2,1,3)$ と $(2,3,1)$ と $(3,1,2)$ と $(3,2,1)$ があります。$f((1,2,3)) = 0$ かつ $f((1,3,2)) = 1$ かつ $f((2,1,3)) = 1$ かつ $f((2,3,1)) = 1$ かつ $f((3,1,2)) = 1$ かつ $f((3,2,1)) = 2$ であるので、$f(p)$ の期待値は $\frac{0+1+1+1+1+2}{6} = 1$ です。$1$ の法 $B = 5$ での値 $1$ を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。