Dado uma matriz $ A $, temos que encontrar o produto de $ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ em todos $ i $ e $ j $ dado $ J> i $
-
29-09-2020 - |
Pergunta
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.
Solução
o produto $$ v=Prod_ {i
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.