Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $$$ 10^9 + 7 $$$
Best approach I can think of is finding frequency of primes in product by grouping elements with same modular residue, which allows $$$ O(N * M / \log M) $$$ if $$$M$$$ is maximum number in array.
I have considered mathematical ways by polynomial multiplication and divide and conquer, which seems most promising but can't solve completely.
Is there any way to find this for arrays of length upto $$$ 10^ 5 $$$, and numbers upto $$$ 10 ^ 9 $$$?
For some $$$l, r$$$, let $$$P_{l,r}$$$ be the polynomial $$$\Pi_{i=l}^{r} (x-a_i)$$$. Find $$$P_{l,r}$$$ using your preferred method of polynomial multiplication for all $$$l,r$$$ which correspond to a segment tree node over a length $$$N$$$ array.
The sub product for some $$$j$$$ is the product of evaluations for all $$$P_{l,r}(x)$$$ at $$$x=a_j$$$ such that you take the segments $$$[l,r]$$$ whose union is precisely $$$[1,j-1]$$$. For each of the segments, find the set of points you're evaluating it at and then use mulit-point evaluation. You will evaluate a segment of length $$$w$$$ with at most $$$w$$$ points. Complexity of multi-point evaluation for a degree $$$w$$$ polynomial at $$$w$$$ points is $$$O(w \log w)$$$ (I think). Summing up over $$$w$$$ as powers of two from $$$1$$$ to $$$N$$$, the total complexity is $$$O(N \log^2 N)$$$. This is also the complexity of constructing the polynomials in the first place.
Thanks for explanation, I think multi-point evaluation was the part I was stuck at in my divide and conquer method, didn't know that was possible, if it indeed works in w log w, then I think divide and conquer and forming the polynomial while merge would suffice, will explore multi-point evaluation technique, thanks for the help.
i asked chatGPT and gPT saY it's O(w log^2 w)