Dado uma matriz $ A $, temos que encontrar o produto de $ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ em todos $ i $ e $ j $ dado $ J> i $

Question

Dado uma matriz $ a $ , temos que encontrar o produto de $ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ sobre tudo $ i $ e $ j $ dado $ J> i $ .


Por exemplo.Deixe a matriz ser $ 1,2,3 $ então minha resposta será calculada $ (2-1) $ . $ (3-1) $ . $ (3-2) $ = $ 2 $
Como o número de elementos na matriz poderia ser grande (até mesmo $ 10 ^ 5 $ ) Estou à procura de solução de ordem $ nlogn$ .
Eu tentei representar matriz como um polinômio, mas poderia tirar nada disso. Por favor ajude.

Answer 1

o produto $$ v=Prod_ {i é o determinante do Matriz de Vandermonde dos números $ a_1, A_2, ..., A_N $ .

O quadrado deste número é o discriminante $ D $ da polinômio $$ p (x)=Prod_i (x-a_i) $$

Isso por sua vez é igual a $$ v ^ 2= D= (- 1) ^ {N (N-1) / 2} \ Prod_IP '(A_I) $$

Você pode rapidamente calcular os coeficientes de $ p (x) $ e, portanto, $ p '(x) $ < / Span>, avalie-o na $ n $ pontos $ a_1, A_2, ..., A_N $ e seu produto. Em seguida, compute raiz quadrada. O sinal de $ v $ você determina classificando e contando a paridade do número de switches.

Você pode fazer tudo isso em $ o (n \ log ^ 2 (n)) $ .

Veja os algoritmos relevantes Aqui < / a>.

Para a raiz quadrada modular, você pode usar Tonelli-shanks para eficiência. Embora a ordem teórica desta etapa seja constante desde a principal $ 998244353 $ é corrigido.