ABC D - Distinct Trio (Number of k-tuples

D - Distinct Trio
题意：
given a sequence,求出 $1\le i<j<k\le n,A_i,A_j,A_k$ Tuples that are distinct from each other $(i,j,k)$ 的个数
思路：
不妨设 $A_i\le A_j\le A_k$
枚举 $A_j$,Maintain a prefix sum to get the answer

拓展：$K$ 元组
code：

n = int(input())
a = [int(x) for x in input().split()]
maxn = int(2e5 + 1)
cnt = [0 for x in range(maxn)]
vis = [0 for x in range(maxn)]
for x in a :
    cnt[x] += 1
    vis[x] = 1
for i in range(1, maxn) :
     cnt[i] += cnt[i-1]
ans = 0
for i in range(maxn) :
    if vis[i] == 0 :
        continue
    ans += (n - cnt[i]) * (cnt[i] - cnt[i-1]) * cnt[i-1]
print(ans)

$dp$ 解法
code：

maxn = int(2e5 + 9)
n = int(input())
a = [int(x) for x in input().split()]
#给所有x-1存到列表a
dp = [[0 for i in range(5)] for j in range(maxn)]
#n*5的数组
cnt = [0 for i in range(maxn)]
for x in a :
    cnt[x] += 1
dp[0][0] = 1
#dp[i][j]表示选了j个数,每个数都<=i,且这iThe number of methods differs from each other
#dp[2e5][3]就是答案
for i in range(1, maxn) :
    for j in range(5) :
        if i + 1 < maxn :
            dp[i][j] += dp[i - 1][j]#不选i
        if i + 1 < maxn and j + 1 < 5 :
            dp[i][j] += dp[i - 1][j - 1] * cnt[i]#选i
print(dp[maxn-9][3])