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

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.

• To get an idea, start by computing (a+b+c)(a+b+c). Jul 5 '20 at 21:10
• I don't think it will help as I want product of difference and not sum in the array. Jul 5 '20 at 21:25
• Can you credit the original source where you encountered this task?
– D.W.
Jul 6 '20 at 1:05
• @ViplawSrivastava Oops, sorry, you are right. Jul 6 '20 at 10:58

The product $$V=\prod_{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.

• @ViplawSrivastava FFT does that. A book that has the algorithms for all these steps is Aho, Hopcroft,Ullman The design and analysis of computer algorithms. For lack of a book, it seems that that particular step is mentioned here.
– plop
Jul 5 '20 at 23:03