题面

Subset with Zero Sum

给出 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，对于所有的 $1\le i\le n$ 满足 $i-n\le a_i\le i-1$。

找出这些整数的非空子集，满足元素和为 $0$。根据题目，一定存在子集满足条件。如果有多个满足条件的子集，输出任意一个。

输入

每个测试包含多个测试用例。第一行是测试用例的数量 $t$（$1\le t\le 10^6$）。每个用例的输入格式如下。

每个用例的第一行包括一个单独的整数 $n$（$1\le n\le 10^6$）。

第二行包括 $n$ 个整数 $a_1,a_2,\cdots ,a_n$（$i-n\le a_i\le i-1$）。

保证所有用例的 $n$ 的总和不超过 $10^6$。

输出

对于每个测试用例，输出两行。

在第一行，输出 $s$（$1\le s\le n$）表示子集中的元素个数。

在第二行，输出 $s$ 个整数 $i_1,i_2,\cdots ,i_s$（$1\le i_k\le n$）。所有整数不同，且 $a_{i_1}+a_{i_2}+\cdots +a_{i_s}=0$。

思路

$\text{tag}$：graphs math

对“一定存在子集满足条件”的证明。

对 $i-n\le a_i\le i-1$ 进行移项变形，得 $1\le i-a_i\le n$。又 $i$ 的取值为 $1\le i\le n$，且 $a_i$ 的下标取值也为 $1$ 到 $n$，故若将 $1$ 到 $n$ 设为点，$1\le i\le n$ 的所有 $i$ 向 $i-a_i$ 连有向边，则得到一个 $n$ 个点，$n$ 条边的有向图，每个点出度为 $1$。

这时容易发现，因为点数与边数相等，故图不可能为树，即图中存在一个环，那么由于收尾相连，所以环上点的编号和会与环上点的子节点的编号和相等，即 $\sum i=\sum (i-a_i)$。移项，得 $\sum a_i=0$。于是，环上点的编号集合即为答案集合。

图上找环的时间复杂度为 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
int a[maxn];
bool vis[maxn];
int cnt[maxn];
int n;
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[i]=0;
	}
	int now=1,all=1;
	while(!vis[now]){
		vis[now]=1,cnt[now]=all;
		now-=a[now],all++;
	}
	cout<<all-cnt[now]<<"\n";
	int x=now;
	do{
		cout<<x<<" ";
		x=x-a[x];
	}while(x!=now);
	cout<<"\n";
}
signed main(){
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}