ARC223 C - Whole Product of Pairwise Distances

考え方

A の順番は、積の値に影響を与えない。
よって、A をソートすることで、絶対値記号を外して $A_j-A_i$ の積と考えてよい。

まず、$N$ で割った余りが等しい $2$ つの数があれば、積の中に $0$ が含まれるので答えは $0$。
しかし、数列は長さ $N$ である。
したがって結局は、余りが $0$ から $N-1$ まで $1$ 回ずつ登場するパターンのみ考えればよい。

しかも、$N$ が合成数の場合も明らかに $0$ となる。
異なる素因数を含む場合、$N=pq$ と互いに素な $2$ 以上の $2$ つの数の積に分ける。
求める積の中に $p$ の倍数も $q$ の倍数も含まれるので、これは $pq$ の倍数。
同じ素数の累乗 $N=p^r$ の場合、その素因数の倍数は積の中に $r$ 個以上含まれる。
よって、$N$ が素数の場合のみ考えればよい。

さらに、$N=2$ の場合は、偶数と奇数が $1$ つずつなら $1$、そうでなければ $0$。
したがって、あとは $N$ が奇素数の場合のみ考えればよい。

剰余を、通常の剰余ではなく、絶対値最小剰余で取る。
つまり、$N=2k+1$ で割った余り $R$ を、通常の $0\leq R \leq 2k$ ではなく、$-k\leq R \leq k$ で取る。

こうすると、$N(N-1)/2=k(2k+1)$ 個の積の絶対値は、$(k!)^{2k+1}$ である。
なぜなら、A の中には余りが $0$ から $N-1$ まで $1$ 回ずつ登場するからである。
この時点で答えは二択で、あとは負の数を何回かけたかを考えればよい。
これは各回ごと、$A_j$ の余りと、過去に調べた値にどんな余りが何個出たかから求められる。
愚直にやれば $O(N^2)$ になるが、Fenwick木などを用いることで $O(N\log N)$ で処理できる。

以上を実装すればよい。
うまく実装すれば、$N=2$ のときや合成数のときも奇素数の場合のコードに任せて問題なくなる。

入力例1での動作

$3$ つ目のテストケースのみ考える。

入力を受け取る。
a はソートしておく。

n: 5
a: {11, 22, 33, 44, 55}

$n=5$ は素数なので、処理を続ける。
剰余類環の法を $5$ に設定する。

$n/2=2$ なので、$(n/2)! = 2! = 2$ である。
これを $n$ 乗して、仮の結果としておく。
すなわち、仮の結果は $2^5 \% 5 = 2$ となる。

前から順に、$5$ で割った余りを確認していく。

まず、$11$ を見る。
$11 \% 5 = 1$ である。
余り $1$ はまだ出ていないので、処理を続ける。
余り $2$ または $3$ のものはこれまでに $0$ 個出ているので、結果に $(-1)^0$ をかける。
余り $1$ が出たことを記録する。

次に、$22$ を見る。
$22 \% 5 = 2$ である。
余り $2$ はまだ出ていないので、処理を続ける。
余り $3$ または $4$ のものはこれまでに $0$ 個出ているので、結果に $(-1)^0$ をかける。
余り $2$ が出たことを記録する。

次に、$33$ を見る。
$33 \% 5 = 3$ である。
余り $3$ はまだ出ていないので、処理を続ける。
余り $4$ または $0$ のものはこれまでに $0$ 個出ているので、結果に $(-1)^0$ をかける。
余り $3$ が出たことを記録する。

次に、$44$ を見る。
$44 \% 5 = 4$ である。
余り $4$ はまだ出ていないので、処理を続ける。
余り $0$ または $1$ のものはこれまでに $1$ 個出ているので、結果に $(-1)^1$ をかける。
仮の結果は $-2$ になる。
余り $4$ が出たことを記録する。

最後に、$55$ を見る。
$55 \% 5 = 0$ である。
余り $0$ はまだ出ていないので、処理を続ける。
余り $1$ または $2$ のものはこれまでに $2$ 個出ているので、結果に $(-1)^2$ をかける。
余り $0$ が出たことを記録する。

以上より、仮の結果は $-2$ である。
$5$ で割った余りとして正の値に直すと、答えは $3$ である。

注意点

$N$ が素数の場合は、法 $N$ の剰余類環で計算する。
符号も含めて管理する必要がある。

別解

特になし。