#P5407. [2018年湖南省队集训]girls

    ID: 4419 传统题 1000ms 256MiB 尝试: 450 已通过: 101 难度: 8 上传者: 标签>CF2400提高+/省选-容斥原理贡献法等差数列求和一维前缀和三元环计数按度数定向时间戳避免清空数组同余的加减乘运算计数杂项三元环

[2018年湖南省队集训]girls

题目描述

有 nn 个人,编号为 00 至 n−1n-1,其中有 mm 对存在冲突。选取三个人 i<j<ki<j<k,要求三人中没有任何一对存在冲突。该方案的愉悦值为 Ai+Bj+CkAi+Bj+Ck。

求所有合法方案的愉悦值之和对 2642^{64} 取模的结果。

输入格式

第一行两个整数 n,mn,m,分别表示人数和冲突数。

第二行三个整数 A,B,CA,B,C。

接下来 mm 行,每行两个整数 x,yx,y,表示编号为 xx 和 yy 的两个人存在冲突。编号从 00 开始。

输出格式

输出一行,表示所有合法方案的愉悦值之和模 2642^{64} 的结果。

样例

4 1
2 3 4
1 0
38

数据范围

  • 对于 20%20\% 的数据,n≤200n\le200。
  • 对于另外 10%10\% 的数据,m=0m=0。
  • 对于另外 20%20\% 的数据,n≤2000n\le2000。
  • 对于另外 10%10\% 的数据,A=1,B=C=0A=1,B=C=0。
  • 对于所有数据,n,m≤min⁡{2⋅105,n(n−1)/2}n,m\le\min\{2\cdot10^5,n(n-1)/2\}。

原 PDF 题面