#1468. 「THUPC 2021 初赛」独立

「THUPC 2021 初赛」独立

题目描述

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

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

  1. 初始分数为 00
  2. 对于所有 iAi \in A,分数加 aia_i
  3. 对于所有边 (u,v,k)(u, v, k)(代表从 uuvv 值为 kk 的边)满足 uAu \in A 并且 vAv \in A,分数减 kk

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

输入格式

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

第一行包含六个整数 n,m,x0,y0,a0,z0n, m, x_0, y_0, a_0, z_01n1000001 \le n \le 1000000mn20 \le m \le \frac{n}{2}0x0,y0,a0,z0<P0 \le x_0, y_0, a_0, z_0 < P)。

对于 1in1 \le i \le n,有 ai=(q×ai1+b)modpa_i = (q \times a_{i - 1} + b) \bmod p

对于 1im1 \le i \le m, 有 xi=(q×xi1+b)modpx_i = (q \times x_{i - 1} + b) \bmod pyi=(q×yi1+b)modpy_i = (q \times y_{i - 1} + b) \bmod pzi=(q×zi1+b)modpz_i = (q \times z_{i - 1} + b) \bmod p。对于每一组 (xi,yi,zi)(x_i, y_i, z_i) 描述了一条连接 (ximodn)+1,(yimodn)+1(x_i \bmod n) + 1, (y_i \bmod n) + 1 的值为 ziz_i 的边,如果 xi=yix_i = y_i 或者之前出现过连接 xix_iyiy_i 的边,则忽视这条边(即这条边不存在)。

输出格式

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

样例

10 5 1 2 3 4

3909327860

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。