原题:Codeforces 985G. Team Players
题意:有nn个编号从 0~n-1 的数,从中选出三个数 ( i<j<ki<j<k ),定义此次得分为: Ai+Bj+CkA \cdot i + B \cdot j + C \cdot k 。给出 m 组矛盾关系 (i,j)(i,j) ,即 ii, jj 不可同时选择。请计算得分总和对 2642^{64} 取模的结果。

Description

There are n n players numbered from 00 to with ranks. The ii -th player has rank ii .

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 i , j j , k k be the ranks of players in the team and i<j<ki < j < k , then the rank of the team is equal to :

Ai+Bj+CkA \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 2642^{64}.

Input

The first line contains two space-separated integers nn and mm ( 3n21053 \le n \le 2 \cdot 10^5, 0m21050 \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 AA , BB and CC ( 1A,B,C1061 \le A, B, C \le 10^6) — coefficients for team rank calculation.

Each of the next mm lines contains two space-separated integers uiu_i and viv_i ( 0ui,vi<n,uivi0 \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.

Output

Print single integer — the total sum of ranks over all possible teams modulo 2642^{64}.

Solution

考虑容斥,对于 一次矛盾,两次矛盾 都可以很容易的算出来。

考虑 (i,j,k)(i,j,k) 同时三次矛盾的情况。对于 (i,j)(i,j) 的矛盾,我们在 iijj 之间连一条双向边。考虑最后连成三元环的情况。我们提取入度小的点连向入度大的点的边,枚举 ii 为入度最小的点,对 ii 的连边上的点给出标记 ii 。如果 ii 是入度最小的点,且存在含有 ii 的三元环 (i,j,k)(i,j,k) 。那么 i,j,ki,j,k 三点的标记都 =i ,计入答案即可。复杂度

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cctype>
#include <algorithm>
// #include <iostream>
using namespace std;
#define re register int
const int N = 2e5+5;
template <class T>inline void read(T &x) {
x=0;
int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}

int cnt=0, nxt[N<<2], head[N], to[N<<2], Head[N], ru[N];
#define add(u,v) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,++ru[v])
#define Add(u,v) (nxt[++cnt]=Head[u],Head[u]=cnt,to[cnt]=v)

unsigned long long ans=0;
int n, m, f[N], k[N], s[N];
unsigned long long A, B, C;

int main() {
read(n), read(m), read(A), read(B), read(C);
int u, v;
while(m--)
read(u), read(v), add(u,v), add(v,u);
for(re u=0;u<n;++u)
for(int i=head[u];i;i=nxt[i]) {
v = to[i];
if(ru[u]<ru[v] || (ru[u]==ru[v]&&u<v)) Add(u,v);
}
// deg(u) < deg(v) 约定入度小的点连大的点

for(re i=0;i<n;++i) //m=0
ans += A*(n-i-1)*(n-i-2)/2*i+B*(n-1-i)*i*i+C*i*(i-1)/2*i;
for(re i=0;i<n;++i) { m=0;
for(int z=head[i];z;z=nxt[z])
k[++m]=to[z], f[to[z]]=i+1;
sort(k+1, k+m+1); s[m+1]=0;
//-1
for(re z=1;k[z]<i&&z<=m;++z) { // -1
ans -= (A*k[z]+B*i)*(n-i-1)+C*(i+n)*(n-i-1)/2; // z<i<j
ans -= (A*k[z]+C*i)*(i-k[z]-1)+B*(k[z]+i)*(i-k[z]-1)/2; // z<j<i
ans -= (B*k[z]+C*i)*k[z]+A*k[z]*(k[z]-1)/2;
}
// cout << ans << endl;
// +2 (i与z,j矛盾)
for(re z=1;k[z]<i&&z<=m;++z) // j<z<i
s[z]=s[z-1]+k[z], ans+=A*s[z-1]+(z-1)*(B*k[z]+C*i);
for(re z=m;k[z]>i&&z;--z) // i<z<j
s[z]=s[z+1]+k[z], ans+=C*s[z+1]+(m-z)*(B*k[z]+A*i);
for(re z=1;z<m;++z) // z<i<j
if(k[z]<i&&k[z+1]>i) ans+=A*s[z]*(m-z)+B*i*z*(m-z)+C*s[z+1]*z;
// -3
// cout << ans << endl;
int v1, v2;
for(int p=Head[i];p;p=nxt[p])
for(int q=Head[v1=to[p]];q;q=nxt[q])
if(f[v2=to[q]]==i+1) {
int c[3]={i,v1,v2}; sort(c,c+3);
ans -= A*c[0]+B*c[1]+C*c[2];
}
// cout << ans << endl;
}
printf("%llu\n", ans);
return 0;
}