算法
(容斥原理) $O(N)$
先考虑不除去某个数,任选两个相同数的方案数为在所有相同数的集合中任选两个数的方案数之和。
比如,$1, 1, 2, 1, 2$
这里的 $1$ 有 $3$ 个,$2$ 有 $2$ 个
任选两个相同数的方案数为 $_3C_2 + {_2C_2}$
再考虑除去某个数,不能看出它对其他和它不同的数不会造成影响
比如,$1, 1, 2, 1, 2$
我们可以考虑去掉第二个数,数字 $2$ 对答案的贡献依然是 $_2C_2$
而数字 $1$ 对答案的贡献就是 $_2C_2$
计算量为 $O(N)$,若依次删掉每个数的答案的总计算量就是 $O(N^2)$,而这里的 $N \leqslant 2e5$,所以时间显然会炸。
我们可以利用容斥原理来考虑,也就是用不删任何数的答案先减去 $_3C_2$($3$ 个 $1$ 都删去),再加上 $_2C_2$(有 $2$ 个 $1$ 是多删去的,所以要加上)。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
ll choose2(ll n) {
return n * (n - 1) / 2;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n) a[i]--;
vector<int> cnt(n);
rep(i, n) cnt[a[i]]++;
ll tot = 0;
rep(i, n) {
tot += choose2(cnt[i]);
}
rep(i, n) {
ll ans = tot;
ans -= choose2(cnt[a[i]]);
ans += choose2(cnt[a[i]] - 1);
cout << ans << '\n';
}
return 0;
}