CF985G Team Players
题面翻译
有 \(n\) 个点，编号依次为 \(0,1....n-1\)。
如果一个三元组 \((i,j,k)~(i<j<k)\) 两两没有边相连，那么它的贡献为 \(A*i+B*j+C*k\)。
求出所有三元组的贡献和，答案对 \(2^{64}\) 取模。
题目描述
There are $ n $ players numbered from \(0\) to \(n-1\) with ranks. The \(i\) -th player has rank \(i\) .
Players can form teams: the team should consist of three players and no pair of players in the team should have a conflict. The rank of the team is calculated using the following algorithm: let \(i\) , \(j\) , \(k\) be the ranks of players in the team and \(i < j < k\) , then the rank of the team is equal to \(A \cdot i + B \cdot j + C \cdot k\) .
You are given information about the pairs of players who have a conflict. Calculate the total sum of ranks over all possible valid teams modulo \(2^{64}\) .
输入格式
The first line contains two space-separated integers \(n\) and \(m\) ( \(3 \le n \le 2 \cdot 10^5\) , \(0 \le m \le 2 \cdot 10^5\) ) — the number of players and the number of conflicting pairs.
The second line contains three space-separated integers \(A\) , \(B\) and \(C\) ( \(1 \le A, B, C \le 10^6\) ) — coefficients for team rank calculation.
Each of the next \(m\) lines contains two space-separated integers \(u_i\) and \(v_i\) ( \(0 \le u_i, v_i < n, u_i \neq v_i\) ) — pair of conflicting players.
It's guaranteed that each unordered pair of players appears in the input file no more than once.
输出格式
Print single integer — the total sum of ranks over all possible teams modulo \(2^{64}\) .
样例 #1
样例输入 #1
4 0
2 3 4
样例输出 #1
64
样例 #2
样例输入 #2
4 1
2 3 4
1 0
样例输出 #2
38
样例 #3
样例输入 #3
6 4
1 5 3
0 3
3 5
5 4
4 3
样例输出 #3
164
提示
In the first example all \(4\) teams are valid, i.e. triples: {0, 1, 2}, {0, 1, 3}, {0, 2, 3} {1, 2, 3}.
In the second example teams are following: {0, 2, 3}, {1, 2, 3}.
In the third example teams are following: {0, 1, 2}, {0, 1, 4}, {0, 1, 5}, {0, 2, 4}, {0, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}.
Solution
两两不连边不好计算，考虑容斥，分为所有三元组、至少有一条边相连的、至少有两条边相连的、至少有三条边相连的。
第四种很好计算，直接套三元环计数板子即可，考虑剩余的如何计算。
由于笔者习惯，以下所有节点编号改为 \([1,n]\)，因此在计算对答案的贡献的时候会 \(-1\)。
-
所有三元组 \((x,y,z)\)：
枚举 \(i\in[1,n]\)，分讨 \(i\) 在三元组中的位置：
- \(x=i\)：此时 \(y,z\) 只需要满足大于 \(x\)，因此对答案贡献 \(A\cdot\dfrac{(n-i)(n-i-1)}2\cdot (i-1)\)；
- \(y=i\)：此时 \(x\in[1,y)\)，\(z\in(y,n]\)，因此对答案贡献 \(B\cdot (i-1)(n-i)(i-1)\)；
- \(z=i\)：此时 \(x,y\) 只需要满足小于 \(z\)，因此对答案贡献 \(C\cdot\dfrac{(i-1)(i-2)}2\cdot(i-1)\)。
-
至少有一条边相连：
枚举所有边 \(u\leftrightarrow v\)，不妨设 \(u<v\)，考虑分讨第三个元素 \(t\) 与 \(u,v\) 的大小关系：
- \(x=u\)：此时只需要 \(t>x\)，因此对答案贡献为 \(A\cdot(u-1)(n-u-1)\)；
- \(y=u\)：此时只需要 \(t<x\)，因此对答案贡献为 \(B\cdot(u-1)(u-1)\)；
- \(y=v\)：此时只需要 \(t>y\)，因此对答案贡献为 \(B\cdot(v-1)(n-v)\)；
- \(z=v\)：此时只需要 \(t<y\)，因此对答案贡献为 \(C\cdot(v-1)(v-2)\)；
- \(x=t\)：此时 \(t\in[1,u)\)，利用等差数列求和公式得到贡献为 \(A\cdot \dfrac{(u-1)(u-2)}2\)；
- \(y=t\)：此时 \(t\in(u,v)\)，同理得到贡献为 \(B\cdot\dfrac{(u+v-2)(v-u-1)}2\)；
- \(z=t\)：此时 \(t\in(v,n]\)，贡献为 \(C\cdot\dfrac{(n+v-1)(n-v)}2\)。
-
至少有两条边相连：
考虑枚举每个点的出边，先将出边按照到达节点的编号排序。设当前枚举的节点是 \(u\)，到达的节点为 \(v\)，在 \(u\) 的所有可到达节点中排名第 \(i\)，\(u\) 所有可到达的节点个数为 \(tn\)。分讨一下 \(u,v\) 的大小关系，设第三个元素的编号为 \(t\)。
-
\(v<u\)：
- 若 \(t<v\)，则 \(v\) 对答案贡献 \(A\cdot (v-1)(tn-i-1)\)；
- 若 \(t>v\)，则 \(v\) 对答案贡献 \(B\cdot(v-1)(i-1)\)。
-
\(v > u\)：
- 若 \(t<v\)，则 \(v\) 对答案贡献 \(C\cdot(v-1)(i-2)\)；
- 若 \(t>v\)，则 \(v\) 对答案贡献 \(B\cdot(v-1)(tn-i)\)。
对于 \(u\) 对答案的贡献，也进行分讨：
- \(x=u\)：此时为 \(t,v>u\)，贡献为 \(A\cdot\dfrac{(tn-i)(tn-i-1)}2\cdot(u-1)\)；
- \(y=u\)：此时 \(t,v\) 分居 \(u\) 两侧，贡献为 \(B\cdot(tn-i)(i-1)\cdot(u-1)\)；
- \(z=u\)：此时 \(t,v<u\)，贡献为 \(C\cdot\dfrac{(i-1)(i-2)}2\cdot(u-1)\)。
-
分讨完了过后将所有情况乘上容斥系数加起来即是答案。
#include<bits/stdc++.h>
using namespace std;
using ui64 = unsigned long long;
int n, m;
ui64 A, B, C;
ui64 ans = 0;
constexpr int _N = 2e5 + 5;
vector<int> oe[_N], ne[_N];
int deg[_N], fr[_N], to[_N];
ui64 GetAns1() {
ui64 sum = 0;
for (int X = 1; X <= n; ++X)
for (int Y : ne[X]) {
int x = min(X, Y), y = max(X, Y);
sum += A * (x - 1) * (n - x - 1);
sum += B * (x - 1) * (x - 1);
sum += B * (y - 1) * (n - y);
sum += C * (y - 1) * (y - 2);
sum += A * (x - 1) * (x - 2) / 2;
sum += B * (y + x - 2) * (y - x - 1) / 2;
sum += C * (n + y - 1) * (n - y) / 2;
}
return sum;
}
ui64 GetAns2() {
ui64 sum = 0;
for (int X = 1; X <= n; ++X) {
oe[X].emplace_back(X);
sort(oe[X].begin(), oe[X].end());
int tn = oe[X].size() - 1;
for (int i = 0; i <= tn; ++i) {
int Y = oe[X][i];
if (Y != X) {
if (Y < X) {
sum += A * (Y - 1) * (tn - i - 1);
sum += B * (Y - 1) * i;
} else {
sum += B * (Y - 1) * (tn - i);
sum += C * (Y - 1) * (i - 1);
}
} else {
sum += A * (tn - i) * (tn - i - 1) / 2 * (X - 1);
sum += B * i * (tn - i) * (X - 1);
sum += C * i * (i - 1) / 2 * (X - 1);
}
}
}
return sum;
}
int vis[_N];
ui64 GetAns3() {
ui64 sum = 0;
for (int X = 1; X <= n; ++X) {
for (int Y : ne[X]) vis[Y] = X;
for (int Y : ne[X]) for (int Z : ne[Y]) {
if (vis[Z] != X) continue;
int t[] = {X, Y, Z};
sort(t, t + 3);
sum += (t[0] - 1) * A + (t[1] - 1) * B + (t[2] - 1) * C;
}
}
return sum;
}
ui64 GetAll() {
ui64 sum = 0;
for (int i = 1; i <= n; ++i) {
sum += A * (n - i) * (n - i - 1) / 2 * (i - 1);
sum += B * (i - 1) * (n - i) * (i - 1);
sum += C * (i - 1) * (i - 2) / 2 * (i - 1);
}
return sum;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> A >> B >> C;
for (int i = 1; i <= m; ++i) {
cin >> fr[i] >> to[i]; ++fr[i], ++to[i];
oe[fr[i]].emplace_back(to[i]);
oe[to[i]].emplace_back(fr[i]);
++deg[fr[i]], ++deg[to[i]];
}
for (int i = 1; i <= m; ++i) {
int x = fr[i], y = to[i];
if (deg[x] > deg[y] || (deg[x] == deg[y] && x > y)) swap(x, y);
ne[x].emplace_back(y);
}
ui64 all = 0, sum = 0;
all = GetAll();
sum = GetAns1() - GetAns2() + GetAns3();
cout << all - sum << '\n';
}