题解：CF985G Team Players
OIer_ACMer · · 题解
恐怖容斥一命速通：CF985G
关键点：
我们发现反向建边太麻烦就可以考虑和它思想差不多（去除不合格的留下合格的）但更难却更高效的方法——容斥。
思考步骤：
- 首先，我们既然要做容斥，就要知道容斥的公式：总体方案数-最多可能重复的种类数加上次多可能重复的种类数……；
- 尽管公式不会证，但我们首先来考虑我们这几种分别是什么，怎么算；
- 首先，最多可能的，也就是总体方案，肯定是任选三个点组成的三元组的答案，由于我们很容易发现
(1,2,3) 和(2,3,1) 都会在枚举过程中出现，但它们属于一种，所以我们默认a<b<c ，下面也是一样，防止重复，这样我们很快就能知道a ，b ，c 在各自的位子上的贡献是多少； - 当我们考虑要求一条边的情况时，也会有重复，我们就钦定
u<v ，那么剩下的就是再在这个分类讨论里分析下一个点w 的大小，因为w 的大小的确无法判定； - 接下来是两条边，因为我们只能确定一个点，所以剩下两个点
v 和w 又会有重复情况，所以钦定v<w ，之后就是判断u<v<w ，u>w>v ，v<u<w ，这几种的答案怎么算； - 最后一种就是三条边都选，就是三元组问题，和上一道差不多；
- 最后公式就是总方案数减去至少有一条边加上至少至少两条边减去至少三条边就是答案。
Code：
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
inline int read()
{
register int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int n, m;
int sum[2000009];
vector<int> g[2000009];
vector<int> e[2000009];
pair<int, int> E[2000009];
int du[2000009];
bool vis[2000009];
signed main()
{
n = read();
m = read();
int A = read();
int B = read();
int C = read();
int ans = 0, ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
for (int i = 1; i <= n; i++) // Section I
{
g[i].push_back(0);
ans1 += A * ((unsigned long long)(n - i - 1) * (n - i) / 2) * (i - 1) + B * (i - 1) * (n - i) * (i - 1) + C * (i - 1) * ((unsigned long long)(i - 1) * (i - 2) / 2);
}
// cout << "ans1=" << ans1 << endl;
for (int i = 1; i <= m; i++) // Section II
{
int x = read(), y = read();x++;
y++;
g[x].push_back(y);
g[y].push_back(x);
E[i] = {x, y};
du[x]++;
du[y]++;
if (x > y)
{
swap(x, y);
}
ans2 += (x - 1) * ((x - 1) * B + (y - 1) * C) + ((unsigned long long)(x - 1) * (x - 2) / 2) * A + (y - x - 1) * ((x - 1) * A + (y - 1) * C) + ((unsigned long long)(y + x - 2) * (y - x - 1) / 2) * B + (n - y) * ((x - 1) * A + (y - 1) * B) + ((unsigned long long)(y + n - 1) * (n - y) / 2) * C;
}
// cout << "ans2=" << ans2 << endl;
for (int i = 1; i <= n; i++)
{
sort(g[i].begin(), g[i].end());
}
for (int u = 1; u <= n; u++) // Section III
{
int rk = 0, cntr = 0, cnt = 0;
for (int i = 1; i <= du[u]; i++)
{
if (g[u][i] < u)
{
rk = i, cntr += g[u][i] - 1;
}
else
{
break;
}
}
for (int i = 1; i <= du[u]; i++)
{
int v = g[u][i];
if (v < u)
{
ans3 += (i - 1) * ((u - 1) * C + (v - 1) * B) + cnt * A;
}
else
{
ans3 += (i - rk - 1) * ((u - 1) * A + (v - 1) * C) + (cnt - cntr) * B;
ans3 += rk * ((u - 1) * B + (v - 1) * C) + cntr * A;
}
cnt += v - 1;
}
}
// cout << "ans3=" << ans3 << endl;
for (int i = 1; i <= m; i++)
{
if (du[E[i].first] > du[E[i].second])
{
e[E[i].second].push_back({E[i].first});
}
else if (du[E[i].second] > du[E[i].first])
{
e[E[i].first].push_back({E[i].second});
}
else
{
if (E[i].first < E[i].second)
{
e[E[i].first].push_back({E[i].second});
}
else
{
e[E[i].second].push_back({E[i].first});
}
}
}
for (int u = 1; u <= n; u++)
{
// for (int i = 0; i < e[u].size(); i++)
// {
// }
for (int i = 0; i < e[u].size(); i++)
{
vis[e[u][i]] = 1;
}
for (int i = 0; i < e[u].size(); i++)
{
int v = e[u][i];
for (int j = 0; j < e[v].size(); j++)
{
int w = e[v][j];
if (vis[w])
{
// cout << "u=" << u << " v=" << v << " w=" << w << endl;
ans4 += (min({u, v, w}) - 1) * A + (u + v + w - min({u, v, w}) - max({u, v, w}) - 1) * B + (max({u, v, w}) - 1) * C;
}
}
}
for (int i = 0; i < e[u].size(); i++)
{
vis[e[u][i]] = 0;
}
}
// cout << "ans4=" << ans4 << endl;
ans = ans1 - ans2 + ans3 - ans4;
cout << ans << endl;
return 0;
}Trick：
容斥原理实在是太困难了，为防止以后回顾这些题傻了，就放个通俗易懂的方法增援未来：