鉴于数组$ a $，我们必须找到$ a_ {j} $ - $ a_ {i} $ modulo $ 998244353 $ fly $ 998244353 $ over $ i $和$ j $ j> i $

Question

给定数组 $ a $ ，我们必须找到 $ a_ {j} $ 的乘积 - $ a_ {i} $ modulo $ 998244353 $ over $ i $ 和 $ j $ 给定 $ j> i $ 。
例如。让数组是 $ 1,2,3 $ 然后我的答案将计算为 -
$（2-1）$ 。 $（3-1）$ 。 $（3-2）$ = $ 2 $
由于阵列中的元素数量很大（Upto $ 10 ^ 5 $ ）我正在寻找订单 $ nlogn的解决方案$ 。
我尝试代表数组作为多项式，但可以从中获取任何东西。 请帮忙。

Answer 1

产品 $$ v=prod_ {i 是 Vandermonde矩阵数字 $ a_1，a_2，...，a_n $ 。

这个数字的平方是判别 $$ 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 $ points $ a_1，a_2，...，a_n $ 及其产品。然后计算平方根。 $ v $ 您可以通过排序和计算交换机数的奇偶校验。

您可以在 $ o（n \ log ^ 2（n））$ 。

中

参见相关算法
< / a>。

对于模块化方形root，您可以使用 tonelli-shanks 效率。虽然此步骤的理论顺序是常量，因为Prime $ 998244353 $ 固定。