値 \(i\) が \(A\) 上で出現する回数を \(d_i\) と置きます。 \(d_i=0\) なる \(i\) に興味はないので、適当に圧縮して \(d_i>0\) とし、 \(d_i>0\) となる \(i\) の個数を \(M\) と置きます。

この時、答えは\[ [x^3] \prod_{i=1}^M (d_i x + 1) \]です。

また、この方法では3種類に限らず \(K\) 種類の値を選ぶこともでき、計算量は多項式が小さい方から順に畳み込むことで \(O(M \log ^2 K)\) となります。