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

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

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

思路：

首先数据小的话，允许的时间复杂度的话，这个题目是可以采用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;
}