题解

思路

先将 $A$ 从小到大排序，原式就变成所有 $A_j-A_i$ 的乘积。

做法

若有两个数模 $N$ 同余，答案显然为 $0$；否则这些余数恰好组成 $0,1,\ldots,N-1$ 的一个排列。标准顺序下的乘积为 $\prod_{0\le i<j<N}(j-i)=\prod_{j=1}^{N-1}j!$，可以在线性时间内递推阶乘并累乘。

排列中交换任意两个余数都会使范德蒙德乘积变号，所以只需再求排序后余数排列的逆序对奇偶性：奇数时把答案改为其相反数，偶数时保持不变。

复杂度

用树状数组统计奇偶性，总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$；所有测试数据的复杂度按 $N$ 的总和计算。