P16513 [GKS 2015 #C] gMatrix

给定一个 $N \times N$ 的非负整数方阵 $M$。我们希望列出 $M$ 中所有 $K \times K$ 的子矩阵的最大值，然后求出这些值之和。（注意，$M$ 的同一元素可能作为多个子矩阵的最大值出现，此时它将在列表中出现多次。）你能求出这个总和吗？ 为了简化矩阵的输入，给定两个长度为 $N$ 的数组 $\mathbf{A}$ 和 $\mathbf{B}$，以及两个整数 $\mathbf{C}$ 和 $\mathbf{X}$。矩阵元素 $M_{ij}$（第 $i$ 行第 $j$ 列）等于 $(\mathbf{A}_i \times i + \mathbf{B}_j \times j + \mathbf{C}) \pmod{\mathbf{X}}$，其中 $i$ 和 $j$ 的取值范围为 $[1, N]$。

第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例首先是一行包含四个整数 $N$、$K$、$C$ 和 $X$。然后有两行，每行包含 $N$ 个整数，分别表示数组 $\mathbf{A}$ 和 $\mathbf{B}$。

对于每个测试用例，输出一行形如 `Case #x: y` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有 $K \times K$ 子矩阵的最大值之和。

在第一个测试用例中，矩阵为： ``` 3 ``` 因此最大值之和为 $3$。 在第二个测试用例中，矩阵为： ``` 9 3 1 6 ``` 因此最大值之和为 $19$。 在第三个测试用例中，矩阵为： ``` 11 11 24 13 13 26 14 14 27 ``` ### 限制 $1 \le T \le 100$。 $1 \le A_i, B_i \le 100000$。 $1 \le C \le 100000$。 $1 \le X \le 1000000007$。 $1 \le K \le N$。 **小数据集（测试集 1 - 可见）** $1 \le N \le 50$。 **大数据集（测试集 2 - 隐藏）** $1 \le N \le 3000$。 翻译由 DeepSeek V4 Pro 完成