1
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – plop Jul 5 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.