頻度表
N個の数があって、Nが大きすぎてO(N^2)ができない時
数の順序に意味がなく、数の種類がNよりだいぶ少ないMなら
種類別の頻度表を作ることで計算量を減らせる
頻度→三角数
N個の数から2つ選ぶペアについて、二つが同じ値であるものをカウントするケース
素朴にループするとO(N^2)
頻度を数えて、各値の頻度nごとに三角数$ T_{n-1} = n(n-1)/2
これならO(N)
多重集合、multiset