Dada una matriz $ A $, tenemos que encontrar producto de $ A_ {J} $ - $ A_ {I} $ Modulo $ 998244353 $ en todos los $ i $ y $ J $ dados $ J> i $

Question

Dada una matriz $ A $ , tenemos que encontrar producto de $ a_ {j} $ - $ a_ {i} $ módulo $ 998244353 $ sobre todo $ i $ y $ j $ Dado $ j> i $ .
Por ejemplo.Deje que la matriz sea $ 1,2,3 $ , entonces mi respuesta se calculará como-
$ (2-1) $ . $ (3-1) $ . $ (3-2) $ = $ 2 $
Como el número de elementos en la matriz podría ser grande (hasta $ 10 ^ 5 $ ) Estoy buscando una solución de orden $ nlogn$ .
He intentado representar la matriz como polinomial, pero podría sacar algo. Por favor ayuda.

Answer 1

El producto $$ v=prod_ {i es el determinante de la matrix de vandermonde de los números $ A_1, A_2, ..., A_N $ .

El cuadrado de este número es el discriminante $ D $ del polinomio $$ p (x)=prod_i (x-a_i) $$

Esto a su vez es igual a $$ v ^ 2= d= (- 1) ^ {n (n-1) / 2} \ prod_ip '(A_I) $$

Puede calcular rápidamente los coeficientes de $ P (x) $ y, por lo tanto, $ P '(x) $ < / span>, evalúelo en el $ n $ puntos $ A_1, A_2, ..., A_N $ Y su producto. Luego calcula la raíz cuadrada. El signo de $ v $ Usted determina clasificando y contando la paridad del número de interruptores.

Puede hacer todo esto en $ o (n \ log ^ 2 (n)) $ .

Consulte los algoritmos relevantes aquí < / a>.

Para la raíz cuadrada modular, puede usarla tonelli-shanks por eficiencia. Aunque el orden teórico de este paso es constante desde el primer $ 998244353 $ se fija.