[yukicoder] No.984 Inversion

概要
解法
コメント

概要

問題文 → ■
公式解説 → ■

想定解よりは平易な発想で解けたと思うので、シェアします。

解法

$S = {(i, j) ∣ 0 < i < j < P}$ とします。次の対応を考えます。

$f : S ⟶ S; (i, j) ⟼ (P - j, P - i) .$

$f \circ f = {id}_{S}$ となるので、 $f$ は、 $f$ の不動点を除き、 $S$ の元 $2$ 個ずつペアにしています。 $P = 5$ なら

${(1, 4)}, {(2, 3)}, {(1, 2), (3, 4)}, {(1, 3), (2, 4)}$

といった要領ですね。 $i + j = P$ となるペアが $f$ の不動点です。

$(i, j)$ が不動点でないとします。 $A_{i} < A_{j} ⟺ P - A_{P - i} < P - A_{P - j} ⟺ A_{P - j} < A_{P - i}$ が成り立ちます。転倒数の偶奇にのみ興味がある状況なので、 $(i, j)$ の寄与と $(P - j, P - i)$ の寄与が相殺します。

したがって、次を解くことに帰着されました。
以下、 $P$ が奇素数であることを仮定して、 $P = 2 K + 1$ としておきます。

【問題】 $A_{i} > K$ となる $1 ≦ i ≦ K$ の個数を $n_{i}$ とするとき、 $n_{i}$ の偶奇を決定せよ。

さらに、 $(- 1)^{n_{i}} \equiv N^{K} (\mod P)$ が証明できます。

$(\mod P)$ で、任意の数が $\pm 1, \pm 2, \dots, \pm K$ のどれかに合同で、擬似的に「符号」が考えられます。例えば、 $P = 7, N = 3$ としましょう。

$\begin{aligned} 1 \cdot N & \equiv 3 (\mod P), \\ 2 \cdot N & \equiv - 1 (\mod P), \\ 3 \cdot N & \equiv 2 (\mod P) \end{aligned}$

のような感じで、 $i \cdot N \equiv e_{i} a_{i} (\mod P)$ （ $e_{i} \in {\pm 1}, 1 ≦ a_{i} ≦ K$ ）と表します。

このとき、 $a_{i}$ は重複しないことが示せます：

$a_{i} = a_{j} ⟹ i \cdot N \equiv \pm j \cdot N (\mod P) ⟹ i \equiv \pm j (\mod P) ⟹ i = j .$

よって、 $\prod_{i} a_{i} \equiv K! (\mod P)$ が成り立ちます。 $K$ 個の式を全部かけあわせると、 $K! \cdot N^{K} \equiv \prod e_{i} \cdot \prod a_{i} \equiv (- 1)^{n_{i}} K! (\mod P)$ で、 $K!$ は $P$ と互いに素なので、 $N^{K} \equiv (- 1)^{n_{i}} (\mod P)$ が示されました。

後半パートは、有名な（？）証明です。平方剰余の第１補充則、第２補充則などはこの方法を使って $- i$ や $2 i$ が「負の数」になる回数を数えると証明されます。もう少し頑張ると、平方剰余の相互法則の証明になります。

概要

解法

コメント