CF2124E Make it Zero

给定一个由 $n$ 个正整数组成的数组 $a$。你可以进行如下操作： - 选择一个大小为 $n$ 的数组 $b$，满足以下条件： - 对于每个 $1 \leq i \leq n$，有 $0 \leq b_i \leq a_i$； - 存在某个下标 $1 \leq i < n$，使得 $b_1+b_2+\ldots+b_i = b_{i+1}+b_{i+2}+\ldots+b_n$，即前缀长度为 $i$ 的和等于后缀长度为 $n-i$ 的和。 - 然后，对每个 $1 \leq i \leq n$，用 $a_i-b_i$ 替换 $a_i$。 你的任务是将所有元素都变为 $0$。请你求出最少需要多少次操作。 然后，输出一种实现操作的方法。如果无论进行多少次操作都无法将 $a$ 的所有元素变为 $0$，则输出 $-1$。可以证明，在本题的约束下，所需的最少操作次数不超过 $17$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 5\cdot 10^4$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^{12}$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $5\cdot 10^4$。

对于每个测试用例，如果无解，输出 $-1$。 否则，首先输出一个整数 $s$（$1 \leq s \leq 17$），表示将所有元素变为 $0$ 所需的最少操作次数。 接下来 $s$ 行，每行输出 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$0 \leq b_i \leq a_i$），表示每次操作中选择的数组 $b$。 操作完成后，$a$ 的所有元素都应变为 $0$。

在第一个测试用例中，我们可以直接选择 $b=a$ 进行操作。这是合法的，因为 $b_1+b_2=b_3$。 在第二个测试用例中，可以证明无论如何都无法将 $a$ 的所有元素变为 $0$。 由 ChatGPT 4.1 翻译