P16625 [GKS 2017 #D] Sherlock and Matrix Game

今天，Sherlock 和 Watson 参加了一场讲座，讲座中介绍了矩阵。Sherlock 是那种对线性代数并不真正感兴趣的程序员，但他确实想到了一个与矩阵有关的问题来让 Watson 解决。 Sherlock 给了 Watson 两个一维数组 A 和 B，长度均为 $N$。他让 Watson 构造一个 $N$ 行 $N$ 列的矩阵，其中第 $i$ 行第 $j$ 列的元素为 A 的第 $i$ 个元素与 B 的第 $j$ 个元素的乘积。 记 $(x, y)$ 表示矩阵中第 $x$ 行（行号从 $0$ 开始，从上往下数）、第 $y$ 列（列号从 $0$ 开始，从左往右数）的格子。一个子矩阵由左下角格子 $(a, b)$ 和右上角格子 $(c, d)$ 定义，其中 $a \ge c$ 且 $d \ge b$，该子矩阵包含所有满足 $c \le i \le a$ 且 $b \le j \le d$ 的格子 $(i, j)$。子矩阵的和定义为该子矩阵中所有格子值的总和。 为了考验 Watson，Sherlock 给了他一个整数 $K$，要求他输出 Watson 的矩阵中所有子矩阵的和里第 $K$ 大的值，其中 $K = 1$ 对应最大的和。（不同的 $K$ 可能对应同一个和，即可能有多个子矩阵具有相同的和。）你能帮助 Watson 吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行九个整数组成：$N$、$K$、$A_1$、$B_1$、$C$、$D$、$E_1$、$E_2$ 和 $F$。其中 $N$ 是数组 A 和 B 的长度；$K$ 是 Watson 需要输出的子矩阵和的排名；$A_1$ 和 $B_1$ 分别是数组 A 和 B 的第一个元素；其余五个值是生成数组元素的参数，生成方式如下： 首先定义 $x_1 = A_1$，$y_1 = B_1$，$r_1 = 0$，$s_1 = 0$。然后，对于 $i = 2$ 到 $N$，使用下面的递推式生成 $x_i$ 和 $y_i$： - $x_i = (C \times x_{i-1} + D \times y_{i-1} + E_1) \bmod F$。 - $y_i = (D \times x_{i-1} + C \times y_{i-1} + E_2) \bmod F$。 进一步，对于 $i = 2$ 到 $N$，使用下面的递推式生成 $r_i$ 和 $s_i$： - $r_i = (C \times r_{i-1} + D \times s_{i-1} + E_1) \bmod 2$。 - $s_i = (D \times r_{i-1} + C \times s_{i-1} + E_2) \bmod 2$。 对于所有 $i = 2$ 到 $N$，定义 $A_i = (-1)^{r_i} \times x_i$，$B_i = (-1)^{s_i} \times y_i$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是题目描述中所定义的矩阵中第 $K$ 大的子矩阵和。

在样例 1 中，使用生成方法得到的数组 A 和 B 分别为 $[1, -3]$ 和 $[1, -3]$。因此构造出的矩阵为 $$\begin{aligned} &[1, \ -3] \\ &[-3, \ 9] \end{aligned}$$ 所有可能的子矩阵和按从大到小排序为 $[9, 6, 6, 4, 1, -2, -2, -3, -3]$。由于 $K = 3$，答案为 $6$。 在样例 2 中，使用生成方法得到的数组 A 和 B 分别为 $[2]$ 和 $[2]$。因此构造出的矩阵为 $$\begin{aligned} &[4] \end{aligned}$$ 由于 $K = 1$，答案为 $4$。 在样例 3 中，使用生成方法得到的数组 A 和 B 分别为 $[1, 0]$ 和 $[2, -1]$。因此构造出的矩阵为 $$\begin{aligned} &[2, \ -1] \\ &[0, \ 0] \end{aligned}$$ 所有可能的子矩阵和按从大到小排序为 $[2, 2, 1, 1, 0, 0, 0, -1, -1]$。由于 $K = 3$，答案为 $1$。 ### 限制条件 $1 \le T \le 20$。 $1 \le K \le \min(10^5, \text{所有可能的子矩阵个数})$。 $0 \le A_1 \le 10^3$。 $0 \le B_1 \le 10^3$。 $0 \le C \le 10^3$。 $0 \le D \le 10^3$。 $0 \le E_1 \le 10^3$。 $0 \le E_2 \le 10^3$。 $1 \le F \le 10^3$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 200$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 10^5$。 翻译由 DeepSeek V4 Pro 完成