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$ は素数なので、処理を続ける。
$n/2=2$ なので、$(n/2)!=2!=2$ である。
符号を考えない積は $2^5\bmod 5=2$ となる。

前から順に、$5$ で割った余りを確認する。

負の数をかける回数は合計 $3$ 回で奇数である。
したがって、符号を含めた積は $-2$ となる。

$5$ で割った余りとして非負の値に直すと、答えは $3$ である。

注意点

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

別解

特になし。