Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

Question

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$.
For eg. Let the array be $1,2,3$ then my answer will be calculated as-
$(2-1)$.$(3-1)$.$(3-2)$=$2$
As number of elements in the array could be large (upto $10^5$) I am looking for solution of order $nlogn$.
I have tried representing array as a polynomial but could get anything out of it. Please help.

Answer 1

The product $$V=\prod_{i<j}(a_j-a_i)$$ is the determinant of the Vandermonde matrix of the numbers $a_1,a_2,...,a_n$.

The square of this number is the discriminant $D$ of the polynomial $$p(x)=\prod_i(x-a_i)$$

This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod_ip'(a_i)$$

You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it at the $n$ points $a_1,a_2,...,a_n$ and their product. Then compute square root. The sign of $V$ you determine by sorting and counting the parity of the number of switches.

You can do all this in $O(n\log^2(n))$.

See the relevant algorithms here.

For the modular square root, you can use Tonelli-Shanks for efficiency. Although the theoretic order of this step is constant since the prime $998244353$ is fixed.