#P6194. 「THUPC 2021 初赛」独立

    ID: 5484 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>图论动态规划CF2200树形DP枚举网络流杂项随机化

「THUPC 2021 初赛」独立

「THUPC 2021 初赛」独立

题目描述

给定一张 nn 个点 mm 条边的无向图。

对于 {1,2,…,n}\{1, 2, \ldots , n\} 的某个子集 AA,AA 的分数为:

  1. 初始分数为 00;
  2. 对于所有 i∈Ai \in A,分数加 aia_i;
  3. 对于所有边 (u,v,k)(u, v, k)(代表从 uu 到 vv 值为 kk 的边)满足 u∈Au \in A 并且 v∈Av \in A,分数减 kk;

现在请你计算出所有的 AA 中,分数最高是多少。

输入格式

令 q=101q = 101,b=137b = 137,p=1,000,000,007p = 1, 000, 000, 007。

第一行包含六个整数 n,m,x0,y0,a0,z0n, m, x_0, y_0, a_0, z_0(1≤n≤1000001 \le n \le 100000,0≤m≤n20 \le m \le \frac{n}{2},0≤x0,y0,a0,z0<p0 \le x_0, y_0, a_0, z_0 < p)。

对于 1≤i≤n1 \le i \le n,有 ai=(q×ai−1+b) mod pa_i = (q \times a_{i - 1} + b) \bmod p。

对于 1≤i≤m1 \le i \le m, 有 xi=(q×xi−1+b) mod px_i = (q \times x_{i - 1} + b) \bmod p,yi=(q×yi−1+b) mod py_i = (q \times y_{i - 1} + b) \bmod p,zi=(q×zi−1+b) mod pz_i = (q \times z_{i - 1} + b) \bmod p。对于每一组 (xi,yi,zi)(x_i, y_i, z_i) 描述了一条连接 (xi mod n)+1,(yi mod n)+1(x_i \bmod n) + 1, (y_i \bmod n) + 1 的值为 ziz_i 的边,先令 ui=(xi mod n)+1u_i=(x_i\bmod n)+1、vi=(yi mod n)+1v_i=(y_i\bmod n)+1。若 ui=viu_i=v_i,或者此前已经保留过连接这两个端点的无向边(不区分端点顺序),则忽略本次生成的边。

所有递推仍严格进行 mm 次,被忽略的边不补生成;最终保留的边数可以少于 mm。子集 AA 可以为空,答案为最高分的普通整数值,不取模。

输出格式

输出一行一个整数表示最高分数。

样例输入 1

10 5 1 2 3 4

样例输出 1

3909327860