Compte tenu d'un tableau $ A $, nous devons trouver le produit de $ a_ {j} $ - $ a_ {i} $ $ Modulo $ € $ € $ €

Question

donné une matrice $ a $ , nous devons trouver le produit de $ a_ {j} $ - $ a_ {i} $ $ modulo $ 9982444353 $ sur tout $ i $ et $ j $ donné $ j> i $ .de
Pour par exemple.Laissez la matrice être 1,2,3 $ $ alors ma réponse sera calculée en tant que-
$ (2-1) $ . $ (3-1) $ . $ (3-2) $ = 2 $
Comme le nombre d'éléments dans le tableau pourrait être grand (jusqu'à 10 $ ^ 5 $ ) Je cherche la solution de commande $ nlogn$ .
J'ai essayé de représenter une arraie comme un polynôme mais que vous pourriez obtenir quelque chose. S'il vous plaît aider.

Answer 1

Le produit $$ v=prod_ {i est le déterminant de la VANDERMONDE Matrix des numéros $ A_1, A_2, ..., A_n $ .

Le carré de ce numéro est le discriminant $ D $ du polynomial $$ p (x)=prod_i (x-a_i) $$

ceci à son tour est égal à $$ v ^ 2= d= (- 1) ^ {n (n-1) / 2} \ prod_ip '(a_i) $$

Vous pouvez calculer rapidement les coefficients de $ p (x) $ et donc $ p '(x) $ < / SPAN>, Évaluez-le à la N $ N $ POINTS $ A_1, A_2, ..., A_N $ et leur produit. Puis calculez la racine carrée. Le signe de $ v $ Vous déterminez en triant et en comptant la parité du nombre de commutateurs.

Vous pouvez faire tout cela dans $ o (n \ log ^ 2 (n)) $ .

Voir les algorithmes pertinents ici < / a>.

Pour la racine carrée modulaire, vous pouvez utiliser Tonelli-Shanks pour l'efficacité. Bien que l'ordre théorique de cette étape soit constant depuis la principale 9982444353 $ est fixe.