問題

1が2つのとき。

例えば、以下の例だと、$_4C_3-2 = 2$と読み解くことができそうなので、そういう感じでやってみたい。

4
1 1 2 3

とりあえず、引く前の組み合わせ数は$_nC_3$です。ここから引いていくことを考えます。

まず、上の例の1のように、2つのときを考えます。このとき、数字の組み合わせとしては[1,1,x]となるときが、ダメなものです。xは2か3なので、2つです。

1が3つのとき。

3つになるとどうなるか考えます。以下の例の最終的な答えが3であることは簡単に分かります。$_5C_3=10$なので、7ぐらい引けると嬉しいことが分かります。

5
1 1 1 2 3

1が3つあるのでここに注目します。このとき、数字の組み合わせとしては[1,1,x]となるときがダメなものです。xは2か3です。一方で、それぞれの1は区別可能(それぞれはインデックスで管理されているので区別可能です)なので記号をふって1a, 1b, 1cなどとすると、[1a,1b,x], [1b,1c,x], [1c,1a,x]の3パターンがあります。つまり、

$$ _3C_2 \times 2 = 6$$

後、[1a,1b,1c]もダメなパターンです。これは1通りで、$_3C_3$の計算でできそうです。

合計で$6+1=7$になりました。この方法で良さそうです。

1がd個のとき。

さて、与えられた数字がn個、重複する数字である1がd個のとき、引くべき数は以下のようになります。左は[1,1,x]を、右は[1,1,1]の個数を数えています。

$$ _dC_2 \times (n-d) + _dC_3$$

一般化

さて、ありがたいことに、1がd(>1)個、2がe(>1)個あったとしても、[1,1,x]と[2,2,x]は互いに排反なので、引くべき数はそれぞれ独立に計算できます。つまり、全ての2個以上ある数字に関して$ _dC_2 \times (n-d) + _dC_3$を引いていけば良いだけです。

実装例

pythonで雑な実装をしています。ちなみにC言語では無事overflowをしたのでご留意を。


def main():
    N = int(input())
    array_ = list(map(int,input().split()))

    d = {}
    for a in array_:
        if not a in d.keys():
            d[a] = 1
        else:
            d[a]+=1
    
    comp_unique = (N)*(N-1)*(N-2)/(3*2*1)
    for v in d.values():
        if v == 1:
            continue
        d = v
        n = N
        comp_unique -= (d * (d - 1) / 2) * (n - d) + ((d * (d - 1) * (d - 2)) / (3 * 2 * 1))
    
    print(int(comp_unique))

if __name__ == "__main__":
	main()