AtCoder Beginner Contest 252 D

https://atcoder.jp/contests/abc252/tasks/abc252_d

例1を考えると、

4
3 1 4 1

3と1と4を取るしかないですが、1が2つあるので、全体で2通りですね。
例3を考えると、

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

同じ数がいくつあるか数えると、

1: 2, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 8: 1, 9: 3

この9つの中から3つ選ぶことになります。1と2と3を選ぶと、2×1×2 = 4になります。
こういう計算を一度に行えるのが母関数です。がいくつあるかをとすると、

が同じものをまとめると、上の例だと、となります。必要なのはの項までなので、べき乗の計算量はです。べき乗の項はしかないので、母関数の計算自体は速いです。

# coding: utf-8
# Distinct Trio

#################### library ####################

def read_int():
    return int(raw_input())

def read_list():
    return list(map(int, raw_input().split()))


#################### process ####################

def read_input():
    N = read_int()
    A = read_list()
    return A

# (1 + nx)^e
def make_polynomial(n, e):
    f = [1] + [0] * 3
    for k in range(1, 4):
        f[k] = f[k-1] * (e-k+1) / k * n
    return f

def poly_mul(f, g):
    h = [0] * 4
    for k in range(4):
        for l in range(4 - k):
            h[k+l] += f[k] * g[l]
    return h

from collections import Counter
def F(A):
    c = Counter(A)
    c2 = Counter(c.values())
    gs = [ make_polynomial(n, e) for n, e in c2.items() ]
    G = reduce(poly_mul, gs)
    return G[3]


#################### main ####################

A = read_input()
print F(A)