【loj#6220】sum

　　题目传送门：https://loj.ac/problem/6220

　　题意：对于一个序列$a$，找出它的一个子序列$b$，使$sum_{a_i in b}a_i equiv 0 pmod n$

　　这是一道很好的思维题。

　　全体子序列较难考虑，因此我们考虑子序列中的区间。设$sum_i=sum_{i=1}^{n} a_i$，显然$sum_{i=l}^{r} a_i equiv 0 pmod n$当且仅当$sum_{l-1}=sum_r$，而我们发现$sum_i mod n$只有$n$种取值，那么根据抽屉原理，必定存在$x,y in [0,n],x eq y$，使$sum_x=sum_y$，因此区间$[x+1,y]$就是我们的答案。

　　代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define maxn 1000020
inline ll read()
{
    ll x=0; char c=getchar(),f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
    return x*f;
}
inline void write(ll x)
{
    static int buf[20],len; len=0;
    if(x<0)x=-x,putchar('-');
    for(;x;x/=10)buf[len++]=x%10;
    if(!len)putchar('0');
    else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('
');}
inline void writesp(ll x){write(x); putchar(' ');}
ll a[maxn];
int pos[maxn];
int n;
int main()
{
    n=read();
    pos[0]=1;
    int sum=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum=(sum+a[i])%n;
        if(pos[sum]){
            for(int j=pos[sum];j<=i;j++)
                writesp(j),writeln(a[j]);
            return 0;
        }
        else pos[sum]=i+1;
    }
    return 0;
}