Dato un array $ a $, dobbiamo trovare il prodotto di $ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ su tutti $ i $ e $ j $ DONO $ J> I $

Question

Dato un array $ A $ , dobbiamo trovare il prodotto di $ a_ {j} $ - $ A_ {I} $ Modulo $ 998244353 $ Over all $ i $ e $ j $ data $ j> I $ .
. Per esempio.Lascia che l'array sia $ 1,2,3 $ Quindi la mia risposta sarà calcolata come-
$ (2-1) $ . $ (3-1) $ . $ (3-2) $ = $ 2 $

Poiché il numero di elementi nell'array potrebbe essere grande (fino a $ 10 ^ 5 $ ) Sto cercando soluzione di ordine $ Nlogn$ .
Ho provato a rappresentare l'array come polinomiale ma potrebbe ottenerne qualcosa. Per favore aiuto.

Answer 1

Il prodotto $$ v=PROD_ {I è il determinante del vandermonde matrice dei numeri $ A_1, A_2, ..., A_N $ .

Il quadrato di questo numero è il discriminante $ D $ del polinomio $$ p (x)=PROD_I (X-A_I) $$

Questo a turno è uguale a $$ v ^ 2= d= (- 1) ^ {n (n-1) / 2} \ PROD_IP '(A_I) $$

È possibile calcolare rapidamente i coefficienti di $ p (x) $ e quindi $ p '(x) $ < / span>, valutarlo alla $ n $ punti $ A_1, A_2, ..., A_N $ e il loro prodotto. Quindi calcolare la radice quadrata. Il segno di $ V $ Determinata ordinando e contando la parità del numero di interruttori.

Puoi fare tutto questo in $ o (n \ log ^ 2 (n)) $ .

Vedere gli algoritmi pertinenti qui < / a>.

Per la radice quadrata modulare, è possibile utilizzare TONELLI-SHANKS per l'efficienza. Sebbene l'ordine teorico di questo passaggio sia costante dalla Prime $ 998244353 $ è fisso.