309596: CF1704D. Magical Array
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Magical Array
题意翻译
给定一个数组 $b$，长度为 $n$。 现选定 $k$ 并构建数组 $c_1,c_2,\dots,c_m$，并且长度均为 $n$。 起初，对于任意的 $i\in[1,m]$ 和 $j\in[1,n]$ 有 $c_{i_j}=b_j$。 现有两种操作。 > 选定 $i,j$ 使得 $1< i< j< n$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+1}$ 自增。 > 选定 $i,j$ 使得 $1< i< j< n-1$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+2}$ 自增。 对 $c_k$ 执行 $x$ 次第二种操作。对其他的数组执行若干次（可能不同的次数）第一种操作。给出 $c_1,c_2,\dots,c_m$，求出 $k$ 和 $x$。题目描述
Eric has an array $ b $ of length $ m $ , then he generates $ n $ additional arrays $ c_1, c_2, \dots, c_n $ , each of length $ m $ , from the array $ b $ , by the following way: Initially, $ c_i = b $ for every $ 1 \le i \le n $ . Eric secretly chooses an integer $ k $ $ (1 \le k \le n) $ and chooses $ c_k $ to be the special array. There are two operations that Eric can perform on an array $ c_t $ : - Operation 1: Choose two integers $ i $ and $ j $ ( $ 2 \leq i < j \leq m-1 $ ), subtract $ 1 $ from both $ c_t[i] $ and $ c_t[j] $ , and add $ 1 $ to both $ c_t[i-1] $ and $ c_t[j+1] $ . That operation can only be used on a non-special array, that is when $ t \neq k $ .; - Operation 2: Choose two integers $ i $ and $ j $ ( $ 2 \leq i < j \leq m-2 $ ), subtract $ 1 $ from both $ c_t[i] $ and $ c_t[j] $ , and add $ 1 $ to both $ c_t[i-1] $ and $ c_t[j+2] $ . That operation can only be used on a special array, that is when $ t = k $ .Note that Eric can't perform an operation if any element of the array will become less than $ 0 $ after that operation. Now, Eric does the following: - For every non-special array $ c_i $ ( $ i \neq k $ ), Eric uses only operation 1 on it at least once. - For the special array $ c_k $ , Eric uses only operation 2 on it at least once. Lastly, Eric discards the array $ b $ . For given arrays $ c_1, c_2, \dots, c_n $ , your task is to find out the special array, i.e. the value $ k $ . Also, you need to find the number of times of operation $ 2 $ was used on it.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Description of test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 3 \leq n \leq 10^5 $ , $ 7 \leq m \leq 3 \cdot 10^5 $ ) — the number of arrays given to you, and the length of each array. The next $ n $ lines contains $ m $ integers each, $ c_{i,1}, c_{i,2}, \dots , c_{i,m} $ . It is guaranteed that each element of the discarded array $ b $ is in the range $ [0,10^6] $ , and therefore $ 0 \leq c_{i,j} \leq 3 \cdot 10^{11} $ for all possible pairs of $ (i,j) $ . It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 10^6 $ . It is guaranteed that the input is generated according to the procedure above.
输出格式
For each test case, output one line containing two integers — the index of the special array, and the number of times that Operation 2 was performed on it. It can be shown that under the constraints given in the problem, this value is unique and won't exceed $ 10^{18} $ , so you can represent it as a $ 64 $ -bit integer. It can also be shown that the index of the special array is uniquely determined. In this problem, hacks are disabled.
输入输出样例
输入样例 #1
7
3 9
0 1 2 0 0 2 1 1 0
0 1 1 1 2 0 0 2 0
0 1 2 0 0 1 2 1 0
3 7
25 15 20 15 25 20 20
26 14 20 14 26 20 20
25 15 20 15 20 20 25
3 9
25 15 20 15 25 20 20 20 20
26 14 20 14 26 20 20 20 20
25 15 20 15 25 15 20 20 25
3 11
25 15 20 15 25 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20
25 15 20 15 25 20 15 20 20 20 25
3 13
25 15 20 15 25 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 15 20 20 20 20 25
3 15
25 15 20 15 25 20 20 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 20 15 20 20 20 20 20 25
3 9
909459 479492 676924 224197 162866 164495 193268 742456 728277
948845 455424 731850 327890 304150 237351 251763 225845 798316
975446 401170 792914 272263 300770 242037 236619 334316 725899输出样例 #1
3 1
3 10
3 15
3 20
3 25
3 30
1 1378716说明
In the first test case, the secret array $ b $ is $ [0, 1, 1, 1, 1, 1, 1, 1, 0] $ . Array $ c_1 $ and array $ c_2 $ are generated by using operation 1. Array $ c_3 $ is generated by using operation 2. For Array $ c_1 $ ,you can choose $ i=4 $ and $ j=5 $ perform Operation 1 one time to generate it. For Array $ c_2 $ , you can choose $ i=6 $ and $ j=7 $ perform Operation 1 one time to generate it. For Array $ c_3 $ ,you can choose $ i=4 $ and $ j=5 $ perform Operation 2 one time to generate it. In the second test case, the secret array $ b $ is $ [20, 20, 20, 20, 20, 20, 20] $ . You can also find that array $ c_1 $ and array $ c_2 $ are generated by using Operation 1. Array $ c_3 $ is generated by using Operation 2. In the third test case, the secret array $ b $ is $ [20, 20, 20, 20, 20, 20, 20, 20, 20] $ . You can also find that array $ c_1 $ and array $ c_2 $ are generated by using Operation 1. Array $ c_3 $ is generated by using Operation 2.Input
题意翻译
给定一个数组 $b$，长度为 $n$。 现选定 $k$ 并构建数组 $c_1,c_2,\dots,c_m$，并且长度均为 $n$。 起初，对于任意的 $i\in[1,m]$ 和 $j\in[1,n]$ 有 $c_{i_j}=b_j$。 现有两种操作。 > 选定 $i,j$ 使得 $1< i< j< n$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+1}$ 自增。 > 选定 $i,j$ 使得 $1< i< j< n-1$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+2}$ 自增。 对 $c_k$ 执行 $x$ 次第二种操作。对其他的数组执行若干次（可能不同的次数）第一种操作。给出 $c_1,c_2,\dots,c_m$，求出 $k$ 和 $x$。Output
**题意翻译：**
给定一个长度为 $ n $ 的数组 $ b $，然后构建长度也为 $ n $ 的数组 $ c_1, c_2, \dots, c_m $。初始时，对于任意的 $ i \in [1, m] $ 和 $ j \in [1, n] $ 有 $ c_{i_j} = b_j $。有两种操作：
1. 选择 $ i, j $ 使得 $ 1 < i < j < n $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+1} $ 各自加一。此操作只能用于非特殊数组。
2. 选择 $ i, j $ 使得 $ 1 < i < j \leq n-1 $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+2} $ 各自加一。此操作只能用于特殊数组。
对 $ c_k $ 执行 $ x $ 次第二种操作，对其他数组执行若干次（可能不同次数）第一种操作。给出 $ c_1, c_2, \dots, c_m $，求出 $ k $ 和 $ x $。
**题目描述：**
Eric 有一个长度为 $ m $ 的数组 $ b $，然后他生成 $ n $ 个额外的数组 $ c_1, c_2, \dots, c_n $，每个数组的长度都是 $ m $，从数组 $ b $ 通过以下方式生成：
初始时，$ c_i = b $ 对于每个 $ 1 \le i \le n $。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] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+1] $ 各自加一。该操作只能用于非特殊数组，即当 $ t \neq k $ 时。
- 操作 2：选择两个整数 $ i $ 和 $ j $（$ 2 \leq i < j \leq m-2 $），从 $ c_t[i] $ 和 $ c_t[j] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+2] $ 各自加一。该操作只能用于特殊数组，即当 $ t = k $ 时。注意，如果操作后数组的任何元素将小于 $ 0 $，Eric 不能执行该操作。
现在，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} $。
- 输出格式：对于每个测试用例，输出一行包含两个整数——特殊数组的索引和对其执行操作 2 的次数。
**输入输出样例：**
- 输入样例：
```
7
3 9
0 1 2 0 0 2 1 1 0
0 1 1 1 2 0 0 2 0
0 1 2 0 0 1 2 1 0
3 7
25 15 20 15 **题意翻译：** 给定一个长度为 $ n $ 的数组 $ b $，然后构建长度也为 $ n $ 的数组 $ c_1, c_2, \dots, c_m $。初始时，对于任意的 $ i \in [1, m] $ 和 $ j \in [1, n] $ 有 $ c_{i_j} = b_j $。有两种操作： 1. 选择 $ i, j $ 使得 $ 1 < i < j < n $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+1} $ 各自加一。此操作只能用于非特殊数组。 2. 选择 $ i, j $ 使得 $ 1 < i < j \leq n-1 $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+2} $ 各自加一。此操作只能用于特殊数组。 对 $ c_k $ 执行 $ x $ 次第二种操作，对其他数组执行若干次（可能不同次数）第一种操作。给出 $ c_1, c_2, \dots, c_m $，求出 $ k $ 和 $ x $。 **题目描述：** Eric 有一个长度为 $ m $ 的数组 $ b $，然后他生成 $ n $ 个额外的数组 $ c_1, c_2, \dots, c_n $，每个数组的长度都是 $ m $，从数组 $ b $ 通过以下方式生成： 初始时，$ c_i = b $ 对于每个 $ 1 \le i \le n $。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] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+1] $ 各自加一。该操作只能用于非特殊数组，即当 $ t \neq k $ 时。 - 操作 2：选择两个整数 $ i $ 和 $ j $（$ 2 \leq i < j \leq m-2 $），从 $ c_t[i] $ 和 $ c_t[j] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+2] $ 各自加一。该操作只能用于特殊数组，即当 $ t = k $ 时。注意，如果操作后数组的任何元素将小于 $ 0 $，Eric 不能执行该操作。 现在，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} $。 - 输出格式：对于每个测试用例，输出一行包含两个整数——特殊数组的索引和对其执行操作 2 的次数。 **输入输出样例：** - 输入样例： ``` 7 3 9 0 1 2 0 0 2 1 1 0 0 1 1 1 2 0 0 2 0 0 1 2 0 0 1 2 1 0 3 7 25 15 20 15
给定一个长度为 $ n $ 的数组 $ b $，然后构建长度也为 $ n $ 的数组 $ c_1, c_2, \dots, c_m $。初始时，对于任意的 $ i \in [1, m] $ 和 $ j \in [1, n] $ 有 $ c_{i_j} = b_j $。有两种操作：
1. 选择 $ i, j $ 使得 $ 1 < i < j < n $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+1} $ 各自加一。此操作只能用于非特殊数组。
2. 选择 $ i, j $ 使得 $ 1 < i < j \leq n-1 $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+2} $ 各自加一。此操作只能用于特殊数组。
对 $ c_k $ 执行 $ x $ 次第二种操作，对其他数组执行若干次（可能不同次数）第一种操作。给出 $ c_1, c_2, \dots, c_m $，求出 $ k $ 和 $ x $。
**题目描述：**
Eric 有一个长度为 $ m $ 的数组 $ b $，然后他生成 $ n $ 个额外的数组 $ c_1, c_2, \dots, c_n $，每个数组的长度都是 $ m $，从数组 $ b $ 通过以下方式生成：
初始时，$ c_i = b $ 对于每个 $ 1 \le i \le n $。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] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+1] $ 各自加一。该操作只能用于非特殊数组，即当 $ t \neq k $ 时。
- 操作 2：选择两个整数 $ i $ 和 $ j $（$ 2 \leq i < j \leq m-2 $），从 $ c_t[i] $ 和 $ c_t[j] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+2] $ 各自加一。该操作只能用于特殊数组，即当 $ t = k $ 时。注意，如果操作后数组的任何元素将小于 $ 0 $，Eric 不能执行该操作。
现在，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} $。
- 输出格式：对于每个测试用例，输出一行包含两个整数——特殊数组的索引和对其执行操作 2 的次数。
**输入输出样例：**
- 输入样例：
```
7
3 9
0 1 2 0 0 2 1 1 0
0 1 1 1 2 0 0 2 0
0 1 2 0 0 1 2 1 0
3 7
25 15 20 15 **题意翻译：** 给定一个长度为 $ n $ 的数组 $ b $，然后构建长度也为 $ n $ 的数组 $ c_1, c_2, \dots, c_m $。初始时，对于任意的 $ i \in [1, m] $ 和 $ j \in [1, n] $ 有 $ c_{i_j} = b_j $。有两种操作： 1. 选择 $ i, j $ 使得 $ 1 < i < j < n $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+1} $ 各自加一。此操作只能用于非特殊数组。 2. 选择 $ i, j $ 使得 $ 1 < i < j \leq n-1 $，将 $ a_i $ 和 $ a_j $ 各自减一，将 $ a_{i-1} $ 和 $ a_{j+2} $ 各自加一。此操作只能用于特殊数组。 对 $ c_k $ 执行 $ x $ 次第二种操作，对其他数组执行若干次（可能不同次数）第一种操作。给出 $ c_1, c_2, \dots, c_m $，求出 $ k $ 和 $ x $。 **题目描述：** Eric 有一个长度为 $ m $ 的数组 $ b $，然后他生成 $ n $ 个额外的数组 $ c_1, c_2, \dots, c_n $，每个数组的长度都是 $ m $，从数组 $ b $ 通过以下方式生成： 初始时，$ c_i = b $ 对于每个 $ 1 \le i \le n $。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] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+1] $ 各自加一。该操作只能用于非特殊数组，即当 $ t \neq k $ 时。 - 操作 2：选择两个整数 $ i $ 和 $ j $（$ 2 \leq i < j \leq m-2 $），从 $ c_t[i] $ 和 $ c_t[j] $ 各自减一，并给 $ c_t[i-1] $ 和 $ c_t[j+2] $ 各自加一。该操作只能用于特殊数组，即当 $ t = k $ 时。注意，如果操作后数组的任何元素将小于 $ 0 $，Eric 不能执行该操作。 现在，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} $。 - 输出格式：对于每个测试用例，输出一行包含两个整数——特殊数组的索引和对其执行操作 2 的次数。 **输入输出样例：** - 输入样例： ``` 7 3 9 0 1 2 0 0 2 1 1 0 0 1 1 1 2 0 0 2 0 0 1 2 0 0 1 2 1 0 3 7 25 15 20 15