Учитывая массив $ a $, мы должны найти продукт $ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ за все $ i $ и $ j $, предоставленные $ j> i $

Question

Учитывая массив $ A $ , мы должны найти продукт $ a_ {j} $ - $ a_ {i} $ модуль $ 998244353 $ по всем $ i $ и $ j $ Учитывая $ j> i $ .
Например,Пусть массив будет $ 1,2,3 $ Тогда мой ответ будет рассчитан как
$ (2-1) $ . $ (3-1) $ . $ (3-2) $ = $ 2 $
Поскольку количество элементов в массиве может быть большой (до $ 10 ^ 5 $ ) Я ищу решение заказа $ nlogn$ .

Я попытался представлять массив в качестве полинома, но мог получить что-нибудь из этого. Пожалуйста, помогите.

Answer 1

Продукт $$ v=prod_ {i - определитель https Матрица Vandermonde номеров $ a_1, a_2, ..., a_n $ .

Квадрат этого номера - Дискриминант $ D $ полиномиального $$ p (x)=prod_i (x-a_i) $$

Это в свою очередь равно $$ v ^ 2= d= (- 1) ^ {n (n - 1) / 2} \ prod_ip '(a_i) $$

Вы можете быстро выделить коэффициенты $ p (x) $ и, таким образом, $ p '(x) $ < / span>, оцените его на $ n $ Точки $ a_1, a_2, ..., a_n $ И их продукт. Затем вычислить квадратный корень. Знак $ V $ Вы определяете, сортируя и подсчитав четность количества коммутаторов.

Вы можете сделать все это в $ O (n \ log ^ 2 (n)) $ .

Смотрите соответствующие алгоритмы здесь < / a>.

Для модульного квадрата root, вы можете использовать Tonelli-Shanks Для эффективности. Хотя теоретический порядок этого шага постоянна, поскольку Prime $ 998244353 $ фиксируется.