本文共 939 字，大约阅读时间需要 3 分钟。

正题

题目链接:

题目大意

$n$个数，求这个序列中一个非空子集的和是$n$的倍数。

解题思路

可以知道一定有一种解法是一段连续的序列。

证明:设$s_x$表示$({\sum }_{i=1}^x{a}_i)\%n$，那么我们要找到一个$s_l=s_r$。

若有$s_i=0$，那么显然有答案

若没有$s_i$为0，那么在这$n$个数中有$n-1$个可能的取值，那么就必定有一个$s_l=s_r$。

证毕

然后$O(n)$搞$s_i$就好了。

$code$

#include
   
    #include
    
     #include
     
      using namespace std;const int N=100010;int T,n,a[N],sum,l,r,v[N*2];int main(){
   	//freopen("checkin.in","r",stdin);	//freopen("checkin.out","w",stdout);	scanf("%d",&T);	while(T--){
   		scanf("%d",&n);		memset(v,0,sizeof(v));		sum=0;l=-1;r=-1;		for(int i=1;i<=n;i++){
   			scanf("%d",&a[i]);			sum=(sum+a[i])%n;			if(!sum){
   l=0;r=i;}			if(v[sum+n]){
   l=v[sum+n];r=i;} 			v[sum+n]=i;		}		if(l==-1){
   			printf("-1\n");			continue;		}		printf("%d\n",r-l);		for(int i=l+1;i<=r;i++)			printf("%d ",a[i]);		putchar('\n');	}}
     
    
   

转载地址：http://luwaf.baihongyu.com/