CF1704D Magical Array

Eric 有一个长度为 $m$ 的数组 $b$，然后他通过以下方式，从数组 $b$ 生成了 $n$ 个额外的数组 $c_1, c_2, \dots, c_n$，每个数组的长度均为 $m$： 最开始，对于每个 $1 \le i \le n$，都有 $c_i = b$。Eric 秘密选择了一个整数 $k$（$1 \le k \le n$），并将 $c_k$ 选为特殊数组。 Eric 可以对数组 $c_t$ 执行两种操作： - 操作 1：选择两个整数 $i$ 和 $j$（$2 \leq i < j \leq m-1$），将 $c_t[i]$ 和 $c_t[j]$ 各减 $1$，同时将 $c_t[i-1]$ 和 $c_t[j+1]$ 各加 $1$。该操作只能用于非特殊数组，即 $t \neq k$。 - 操作 2：选择两个整数 $i$ 和 $j$（$2 \leq i < j \leq m-2$），将 $c_t[i]$ 和 $c_t[j]$ 各减 $1$，同时将 $c_t[i-1]$ 和 $c_t[j+2]$ 各加 $1$。该操作只能用于特殊数组，即 $t = k$。注意，如果执行操作后数组中有任何元素变为小于 $0$，则不能执行该操作。 接下来，Eric 进行了如下操作： - 对于每个非特殊数组 $c_i$（$i \neq k$），Eric 仅对其执行操作 1，且至少执行一次。 - 对于特殊数组 $c_k$，Eric 仅对其执行操作 2，且至少执行一次。 最后，Eric 丢弃了数组 $b$。 现在给定数组 $c_1, c_2, \dots, c_n$，你的任务是找出特殊数组的编号 $k$，并且需要求出在该数组上执行操作 2 的次数。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$7 \leq m \leq 3 \cdot 10^5$），分别表示给定的数组个数和每个数组的长度。 接下来的 $n$ 行，每行包含 $m$ 个整数，分别为 $c_{i,1}, c_{i,2}, \dots , c_{i,m}$。 保证被丢弃的数组 $b$ 的每个元素都在区间 $[0,10^6]$ 内，因此对于所有可能的 $(i,j)$ 对，都有 $0 \leq c_{i,j} \leq 3 \cdot 10^{11}$。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。 保证输入数据是按照上述过程生成的。

对于每个测试用例，输出一行，包含两个整数，分别表示特殊数组的编号和在其上执行操作 2 的次数。可以证明，在给定的约束下，这个值是唯一的且不会超过 $10^{18}$，因此你可以用 $64$ 位整数表示。也可以证明特殊数组的编号是唯一确定的。 本题不支持 Hack。

在第一个测试用例中，秘密数组 $b$ 为 $[0, 1, 1, 1, 1, 1, 1, 1, 0]$。数组 $c_1$ 和 $c_2$ 是通过操作 1 生成的。数组 $c_3$ 是通过操作 2 生成的。 对于数组 $c_1$，你可以选择 $i=4$ 和 $j=5$，执行一次操作 1 得到它。对于数组 $c_2$，你可以选择 $i=6$ 和 $j=7$，执行一次操作 1 得到它。对于数组 $c_3$，你可以选择 $i=4$ 和 $j=5$，执行一次操作 2 得到它。 在第二个测试用例中，秘密数组 $b$ 为 $[20, 20, 20, 20, 20, 20, 20]$。你也可以发现数组 $c_1$ 和 $c_2$ 是通过操作 1 生成的。数组 $c_3$ 是通过操作 2 生成的。 在第三个测试用例中，秘密数组 $b$ 为 $[20, 20, 20, 20, 20, 20, 20, 20, 20]$。你也可以发现数组 $c_1$ 和 $c_2$ 是通过操作 1 生成的。数组 $c_3$ 是通过操作 2 生成的。 由 ChatGPT 4.1 翻译