数列 \(A\) に \(0\) が含まれる場合と、含まれない場合に分けて数え上げることを考えます。具体的には \(A_i, A_j, A_k\) に \(0\) が含まれる場合で、条件 \(A_i \times M^{A_j} = A_k\) を満たす \((i, j, k)\) の組合せの数を数えた後、 \(A\) から \(0\) を除外することで \(A_i, A_j, A_k\) に \(0\) が含まれない場合の組合せを数え上げます。

\(A_i, A_j, A_k\) に \(0\) が含まれる場合と、含まれない場合に分けて数え上げます。

まず \(A_i, A_j, A_k\) に \(0\) が含まれる場合を考えます。 はじめに \(A_i = A_k = 0\) となる場合も条件を満たすので、この場合の \((i, j, k)\) の組合せの数を考えます。 この場合の組合せの数は \(c_0 (c_0 - 1) (N - 2)\) となります。 次に \(A_i = A_k \neq 0\) かつ \(A_j = 0\) となる場合も条件を満たすので、この場合の \((i, j, k)\) の組合せの数を考えます。 この場合の組合せの数は \(\sum_{x \neq 0} c_x (c_x - 1) c_0\) となります。

次に \(A_i, A_j, A_k\) に \(0\) が含まれない場合を考えます。 この場合は予め \(A\) から \(0\) を除外しておくことで、はじめから \(A\) が \(0\) を含まないとしてよいです。　 \(M=1\) と \(M>1\) の場合に分けて考えます。 \(M=1\) のとき、条件を満たすのは \(A_i=A_k\) となる場合のみです。 この場合の組合せの数は \(\sum_{x} c_x (c_x - 1) (N - 2)\) となります。 \(M > 1\) のとき、\(y = A_j\) とすると \(y \le \log_M(A_k) \le 60\) より \(y\) の候補が \(60\) 通りしかないことがわかるので、これに着目して数え上げます。 \(i\) と \(A_j = y\) を固定すると、\(i \neq j\) かつ \(A_j = y\) となる \(j\) の選び方は、\(A_i = y\) のとき \(c_y - 1\) 通り、それ以外のとき \(c_y\) 通りです。 さらにこのとき \(k\) の選び方は \(c_{A_i \times M^y}\) 通りです。 以上よりこの場合の組合せの数は \(\sum_y \sum_{i=1}^N (c_y - \delta_{A_i, y}) c_{A_i \times M^y}\)（ただし \(\delta_{A_i, y}\) は \(A_i = y\) のとき \(1\) それ以外のとき \(0\) となる関数）となります。 また、 \(A_i \times M^{A_j}\) は非常に大きくなる場合があるので、オーバーフローに注意してください。

このように場合分けして求めた組合せの数を足し合わせることで答えを求めることができます。

計算量は \(O(N\log N\log(\max(A_i)))\) 時間で、hash を使った場合は \(O(N\log(\max(A_i)))\) 時間となり、これは十分高速です。

クレジット

原案： US_cube

解法： US_cube

問題準備・解説： S0ni

レビュー： nu50218, null0124

テスター： DEGwer

校正： nu50218, ngtkana