独特三元组｜排列组合与容斥

第四题 - A24633.独特三元组

题目链接跳转：A24633.独特三元组

这道题有很多做法，这里提供一个基于排列组合的算法。

假设有 $N$ 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这 $N$ 个元素中任意取 $3$ 个元素的组合。也就是 $\binom{n}{3} = n \times (n-1) \times (n-2) / 1$​。

如果有重复的元素呢？我们只需要把重复的元素再“去除”掉就行。

具体地说，如果某个元素的出现次数 arr[i] 大于等于 $3$，则可以从这些重复的元素中选出三个元素组成一个三元组 $(A_i,A_i,A_i)$，这是不符合条件的，因此再删除掉这些重复元素的组合数即可。即 $\binom{arr[i]}{3}$。

如果某个元素的出现次数 arr[i] 大于等于 $2$，则可以从这些重复的元素中选出两个元素，再从数组中的其他元素中选出一个不同的元素组成三元组 $(A_i,A_i,A_j)$，其中 $A_i \neq A_j$，即 $\binom{arr[i]}{2}$​。

最后本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int n, ans, arr[N];

signed main(){
    cin >> n;
    ans = n * (n-1) * (n-2) / 6;
    for (int i=1, t; i<=n; i++){
        cin >> t;
        arr[t] += 1;
    }  
    for (int i=1; i<=N-1; i++){
        int p1 = 0, p2 = 0;
        if (arr[i] == 0) continue;
        if (arr[i] >= 3) p1 = arr[i] * (arr[i] - 1) * (arr[i] - 2) / 6;
        if (arr[i] >= 2) p2 = (n - arr[i]) * arr[i] * (arr[i] - 1) / 2;
        ans -= p1 + p2;
    }
    cout << ans << endl;
    return 0;
}