Matching Modulo

2 secs 1024 MB

解説

$i < j$ の時、 $j$ を固定して条件を満たす $A_i$ の個数を高速に数える方法を考えます。

まず、 $A_i + A_j \equiv 0 \mod M$ の条件から $A_i \equiv M - A_j \mod M$ という条件が導き出せます。

余りごとにFenwickTreeを利用して $A_i < A_j$ を満たす $A_i$ の個数を得ることが出来ます。

左から見ていき、対応する $A_i$ の個数を数え、 $A_j \mod M$ の値をFenwicTreeに追加していけば良いです。