概要
想定解よりは平易な発想で解けたと思うので、シェアします。
解法
$S = \{(i,j)\mid 0 < i < j < P\}$ とします。次の対応を考えます。
\[f\colon S\longrightarrow S; (i,j) \longmapsto (P-j,P-i).\]
$f\circ f = \id_S$ となるので、$f$ は、$f$ の不動点を除き、 $S$ の元 $2$ 個ずつペアにしています。$P=5$ なら
\[ \{(1,4)\}, \quad \{(2,3)\}, \quad \{(1,2),(3,4)\},\quad \{(1,3),(2,4)\}\]
といった要領ですね。$i+j=P$ となるペアが $f$ の不動点です。
$(i,j)$ が不動点でないとします。\[ A_i < A_j\iff P – A_{P-i} < P – A_{P-j}\iff A_{P-j} < A_{P-i} \] が成り立ちます。転倒数の偶奇にのみ興味がある状況なので、$(i,j)$ の寄与と $(P-j,P-i)$ の寄与が相殺します。
したがって、次を解くことに帰着されました。
以下、$P$ が奇素数であることを仮定して、$P = 2K+1$ としておきます。
【問題】$A_i > K$ となる $1 \leqq i \leq K$ の個数を $n_i$ とするとき、$n_i$ の偶奇を決定せよ。
さらに、$(-1)^{n_i} \equiv N^{K}\pmod{P}$ が証明できます。
$\pmod{P}$ で、任意の数が $\pm1, \pm2, \ldots, \pm K$ のどれかに合同で、擬似的に「符号」が考えられます。例えば、$P=7, N=3$ としましょう。
\[\begin{align*}1\cdot N&\equiv 3\pmod{P},\\2\cdot N&\equiv -1\pmod{P},\\3\cdot N&\equiv 2\pmod{P}\end{align*}\]
のような感じで、$i\cdot N \equiv e_i a_i\pmod{P}$（$e_i\in\{\pm1\}, 1\leq a_i\leq K$） と表します。
このとき、$a_i$ は重複しないことが示せます：
\[a_i=a_j\implies i\cdot N\equiv \pm j\cdot N\pmod{P}\implies i\equiv \pm j\pmod{P}\implies i=j.\]
よって、$\prod_i a_i \equiv K!\pmod{P}$ が成り立ちます。$K$ 個の式を全部かけあわせると、$K!\cdot N^K \equiv \prod e_i\cdot \prod a_i\equiv (-1)^{n_i}K!\pmod{P}$ で、$K!$ は $P$ と互いに素なので、$N^K \equiv (-1)^{n_i}\pmod{P}$ が示されました。
コメント
後半パートは、有名な（？）証明です。平方剰余の第１補充則、第２補充則などはこの方法を使って $-i$ や $2i$ が「負の数」になる回数を数えると証明されます。もう少し頑張ると、平方剰余の相互法則の証明になります。
