#CF1270G. Subset with Zero Sum

Subset with Zero Sum

好的,这是您要求的算法题目的中文翻译和排版:


G. 和为 00 的子集
每个测试点时间限制:22
每个测试点内存限制:256256 MB
输入:标准输入
输出:标准输出

给定 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n,并且对于每个 1in1 \le i \le n,满足 naii1-n \le a_i \le i-1
请找出这些整数的一个非空子集,使得该子集的和为 00。可以证明,在给定的约束条件下,这样的子集一定存在。如果有多个和为 00 的子集,输出其中任意一个即可。

输入
每个测试文件包含多个测试用例。第一行包含一个整数 tt1t1061 \le t \le 10^6),表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 nn1n1061 \le n \le 10^6)。
每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_nnaii1-n \le a_i \le i-1)。

保证所有测试用例的 nn 之和不超过 10610^6

输出
对于每个测试用例,输出两行:

  • 第一行输出一个整数 ss1sn1 \le s \le n),表示你选出的子集中元素的个数。
  • 第二行输出 ss 个整数 i1,i2,,isi_1, i_2, \dots, i_s1ikn1 \le i_k \le n),这些下标必须两两不同,并且满足 ai1+ai2++ais=0a_{i_1} + a_{i_2} + \dots + a_{i_s} = 0
    如果有多个和为 00 的子集,输出任意一个即可。

输入示例

2
5
0 1 2 3 4
4
-3 1 1 1

输出示例

1
1
4
1 4 3 2

注意
在第一个示例中,子集的和为 a1=0a_1 = 0
在第二个示例中,子集的和为 a1+a4+a3+a2=0a_1 + a_4 + a_3 + a_2 = 0


如果您需要我进一步解释解题思路或提供代码实现,也可以告诉我。