アレイ$ A $を考えると、$ a_ {j} $ - $ a_ {i} $ moduloの商品を見つける必要があります$ 998244353 $ $ j> i $ J> i $

Question

a配列 $ A $ を指定して、 $ a_ {j} $ の積を見つける必要があります。 - $ a_ {i} $ modulo $ 998244353 $ すべて$ i $ と $ j $ $ j> i $ 。
例えば。アレイを $ 1,2,3 $ にすることで、私の答えは

$（2-1）$ 。 $（3-1）$ 。 $（3-2）$ = $ 2 $
アレイ内の要素数が大きくなる可能性がある（ $ 10 ^ 5 $ ）である可能性があります。 $ nlognの解決策を探しています。$ 。
私は多項式としてアレイを代表することを試みましたが、それから何かを得ることができました。 助けてください。

Answer 1

$$ v=prod_ {i は Vanderdee Matrix 番号 $ a_1、a_2、...、a_n $ 。

この数の2乗は弁別 $ 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>、 points $ a_1、a_2、...、a_n $ そして彼らの製品。それから平方根を計算します。 $ v $ のサインは、スイッチの数のパリティをソートして数えることによって決まります。

これをすべて実行できます。 $ o（n \ log ^ 2（n））$ 。

関連するアルゴリズムこちら< / a>。

モジュール式平方根の場合は、 tonelli-shanks 効率について。 Prime $ 998244353 $ が固定されているため、この手順の理論順は一定ですが。