Angesichts eines Arrays $ A $, müssen wir Produkt von $ A_ {j} $ - $ A_ {I} $ modulo $ 998244353 $ über alle $ i $ und $ J $ gegeben $ j> i $

Question

Angesichts eines Arrays $ A $ , müssen wir Produkt von $ A_ {j} $ finden- $ A_ {I} $ modulo $ 998244353 $ über alle $ i $ und $ J $ angegeben $ j> i $ .Kummer Zum Beispiel.Lassen Sie das Array $ 1,2,3 $ dann meine Antwort berechnet werden $ (2-1) $ . $ (3-1) $ . $ (3-2) $ = $ 2 $

Wenn Anzahl der Elemente im Array groß sein könnten (bis 10 ^ 5 $ ) Ich suche nach einer Lösung von Order $ nlogg$ .
Ich habe versucht, ein Array als Polynom zu repräsentieren, kann aber etwas davon abhalten. Bitte helfen.

Answer 1

Das Produkt $$ v=prod_ {i ist die Determinante des Vandermonde Matrix der Zahlen $ A_1, A_2, ..., A_N $ .

Das Quadrat dieser Nummer ist das diskriminierend $ D $ der Polynom $$ P (x)=prod_i (x-a_i) $$ $$

Dies ist wiederum gleich $$ V ^ 2= d= (- 1) ^ {n (n-1) / 2} \ prod_ip '(A_i) $$

Sie können die Koeffizienten von $ p (x) $ und somit $ p '(x) $ < / span>, bewerten Sie es in der $ N $ Points $ A_1, A_2, ..., A_N $ und ihr Produkt. Dann berechnen Sie Quadratwurzel. Das Zeichen von $ V $ Sie bestimmen, indem Sie die Parität der Anzahl der Switches sortieren und zählen.

Sie können das alles in $ O (n \ log ^ 2 (n)) $ .

siehe den relevanten Algorithmen hier < / a>.

Für die modulare Quadratwurzel können Sie Tonelli-Shanks aus Effizienz. Obwohl die theoretische Reihenfolge dieses Schritts konstant ist, ist der Prime $ 998244353 $ fixiert.