[ABC252D] Distinct Trio Solution

更好的阅读体验戳此进入

题面

给定序列 $a_n$$a_n$，求满足以下条件的三元组 $(i,j,k)$$(i, j, k)$ 的数量：

$1\le i<j<k\le n,a_i\ne a_j\ne a_k$$1 \le i \lt j \lt k \le n, a_i \neq a_j \neq a_k$。

Solution

首先不难想到三元组满足 $i<j<k$$i \lt j \lt k$，那么就可以认为是去掉这个条件然后求本质不同三元组，也就是求组合数。

然后考虑正难则反，直接求不好求，考虑先求 $(\genfrac{}{}{0ex}{}{n}{3})$$n \choose 3$，然后考虑从中去掉不合法的方案。

显然要去掉的就是有两个数相同的组合数和有三个数相同的组合数。当然这个从容斥的角度来看三个数相同的似乎应该是加上，但是实现的时候会发现这个实际上不算是容斥。

我们实现的时候不难发现值域较小，于是想到需要建桶。枚举每个桶，令 $i$$i$ 的个数为 $cn{t}_i$$cnt_i$，如果 $cn{t}_i\ge 2$$cnt_i \ge 2$，那么直接减掉 $(\genfrac{}{}{0ex}{}{cn{t}_i}{2})\times (n-cn{t}_i)$${cnt_i \choose 2} \times (n - cnt_i)$，这个式子很显然，并且这个是有且仅有两个数相同的方案数，所以不需要容斥，再次枚举，如果 $cn{t}_i\ge 3$$cnt_i \ge 3$ 再减去 $(\genfrac{}{}{0ex}{}{cn{t}_i}{3})$$cnt_i \choose 3$ 即可。

Code

xxxxxxxxxx
56
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int a[210000];
27
int cnt[210000];
28
ll ans(0);
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i)cnt[a[i] = read()]++;
33
    ans = (ll)N * (N - 1) * (N - 2) / (3 * 2 * 1);
34
    for(int i = 1; i <= 201000; ++i){
35
        if(cnt[i] >= 2)ans -= (ll)cnt[i] * (cnt[i] - 1) / (2 * 1) * (N - cnt[i]);
36
        if(cnt[i] >= 3)ans -= (ll)cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / (3 * 2 * 1);
37
    }printf("%lld\n", ans);
38
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
39
    return 0;
40
}
41

42
template < typename T >
43
inline T read(void){
44
    T ret(0);
45
    int flag(1);
46
    char c = getchar();
47
    while(c != '-' && !isdigit(c))c = getchar();
48
    if(c == '-')flag = -1, c = getchar();
49
    while(isdigit(c)){
50
        ret *= 10;
51
        ret += int(c - '0');
52
        c = getchar();
53
    }
54
    ret *= flag;
55
    return ret;
56
}

UPD

update-2022_12_03 初稿