同じ数同士の掛け算をまとめて一回で行うことを考えます。

\(A_i=k\)を満たす\(i\)の数を\(C_k\)とすると
\(i\)と\(j(>i)\)の掛け算が\(C_iC_j\)回行われ、\(i\)と\(i\)の掛け算が\(\frac{C_i(C_i-1)}{2}\)回行われることから

\[\sum_{1\le i<j\le N}A_i A_j=\left(\sum_{1\le i <j\le \max{C} }ijC_iC_j\right)+\left(\sum_{1\le i \le \max{C} }i^2\frac{C_i(C_i-1)}{2}\right)\]

のように変形可能です。

\(1\le A_i \le 10^4\)から\(\max{C}\)は最大でも\(10^4\)ですので\(O((\max{C})^2)\)でも間に合います。

ACコード例(C++)