[南湖的瓜-续] 前缀和的妙用

南湖的瓜-续 前缀和的妙用

题意：给你一个长度为 n的序列，请你求出一组子序列的和是n的整数倍。

$1\le n\le 10^6,1\le a[i]\le 10^{9}1\; \backslash le\; n\; \backslash le\; 10^6,1\; \backslash le\; a[i]\backslash le\; 10^9$

思路：

首先数据小的话，允许$n^{2}n^2$的时间复杂度的话，这个题目是可以采用01背包来求得。但是这里明显不行。

所以就要观察题目的特殊性，这里取模取得是n。如果对原序列做一个前缀和并对n取模的话。

• 情况一：如果存在一个位置取模之后等于0，那么从头到该位置这一段一定是可以的。
• 情况二：如果不存在等于0的位置，那么一定存在两个或两个以上取模之后相等的位置。因为总共长度就为n，取模之后最多也就0~n-1，又没有0，那么一定有两个相等的。所以一定存在有解。两个取模之间的和一定是 n 的倍数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int a[N],sum[N],p[N];


int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=(sum[i-1]+a[i])%n;
	}
	//如果存在前缀和为 0 ，那肯定是可以的
	for(int i=1;i<=n;i++){
		if(sum[i]==0){
			cout<<i<<endl;
			for(int j=1;j<=i;j++) cout<<j<<" ";
			return 0;
		}
	}
	//存在两个取模为 0 的前缀和，那么两个之间的数一定是n的倍数

	for(int i=1;i<=n;i++){
		if(p[sum[i]]){
			int l=p[sum[i]];
			cout<<i-l<<endl;
			for(int j=l+1;j<=i;j++) cout<<j<<" ";
			return 0;
		}
		p[sum[i]]=i;
	}
	return 0;
}