P16657 [GKS 2018 #G] Combining Classes

Supervin 教授了 $N$ 个班级，班级编号为 $1$ 到 $N$。在他最近一次考试后，他注意到每个班级中学生的考试成绩构成了一个连续整数序列。因此，Supervin 可以将第 $i$ 个班级的成绩总结为两个整数 $L_i$ 和 $R_i$。这意味着第 $i$ 个班级有 $R_i - L_i + 1$ 名学生，并且对于每个 $x$（$L_i \le x \le R_i$），恰好有一名学生的成绩为 $x$。 Supervin 希望将所有班级的学生成绩合并，并按非递增顺序排序。他有 $Q$ 个问题（编号为 $1$ 到 $Q$）关于这个列表；对于第 $i$ 个问题，他想知道第 $K_i$ 高的成绩是多少。（如果 $K_i$ 大于学生总数，则第 $i$ 个问题的答案为 $0$。） 你能帮助 Supervin 回答所有问题吗？由于答案可能很多，我们不输出所有答案，而是输出一个证明你已回答它们的结果：对于所有 $1 \le i \le Q$，计算 $(S_i \times i)$ 的和，其中 $S_i$ 是第 $i$ 个问题的答案。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含四行。第一行包含两个整数 $N$ 和 $Q$，如上所述。接下来的三行每行分别包含六个整数，格式如下： - $X_1$ $X_2$ $A_1$ $B_1$ $C_1$ $M_1$ - $Y_1$ $Y_2$ $A_2$ $B_2$ $C_2$ $M_2$ - $Z_1$ $Z_2$ $A_3$ $B_3$ $C_3$ $M_3$ 这些值用于生成 $L_i$、$R_i$ 和 $K_i$，生成方式如下： 定义： - 对于 $i = 3$ 到 $N$：$X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1) \bmod M_1$。 - 对于 $i = 3$ 到 $N$：$Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2) \bmod M_2$。 - 对于 $i = 3$ 到 $Q$：$Z_i = (A_3 \times Z_{i-1} + B_3 \times Z_{i-2} + C_3) \bmod M_3$。 同时定义： - 对于 $i = 1$ 到 $N$：$L_i = \min(X_i, Y_i) + 1$。 - 对于 $i = 1$ 到 $N$：$R_i = \max(X_i, Y_i) + 1$。 - 对于 $i = 1$ 到 $Q$：$K_i = Z_i + 1$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有 $1 \le i \le Q$ 的 $(S_i \times i)$ 之和，其中 $S_i$ 是第 $i$ 个问题的答案。

在样例 #1 中，生成的数组 X、Y、Z 为： - $X = [3, 1, 3, 0, 8]$。 - $Y = [2, 7, 7, 2, 6]$。 - $Z = [4]$。 因此， - $L = [3, 2, 4, 1, 7]$。 - $R = [4, 8, 8, 3, 9]$。 - $K = [5]$。 每个班级的学生成绩分别为：$[3, 4]$、$[2, 3, 4, 5, 6, 7, 8]$、$[4, 5, 6, 7, 8]$、$[1, 2, 3]$ 和 $[7, 8, 9]$。这意味着所有班级合并后的学生成绩为：$[3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]$。将它们按非递增顺序排序后为：$[9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]$。因此，第 $5$ 高的成绩为 $7$。于是 $S = [7]$，答案为 $7 \times 1 = 7$。 ### 限制条件 $1 \le T \le 100$。 $1 \le N \le 4 \times 10^5$。 对于所有 $i$，$0 \le A_i < M_i$。 对于所有 $i$，$0 \le B_i < M_i$。 对于所有 $i$，$0 \le C_i < M_i$。 $0 \le X_1 < M_1$。 $0 \le X_2 < M_1$。 $0 \le Y_1 < M_2$。 $0 \le Y_2 < M_2$。 $0 \le Z_1 < M_3$。 $0 \le Z_2 < M_3$。 对于所有 $i$，$1 \le M_i \le 10^9$。 **小数据集（测试集 1 – 可见）** $Q = 1$。 **大数据集（测试集 2 – 隐藏）** $1 \le Q \le 10^5$。 翻译由 DeepSeek V4 Pro 完成