【loj#6220】sum

　　题意：对于一个序列$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 \bmod n$只有$n$种取值，那么根据抽屉原理，必定存在$x,y \in [0,n],x \neq 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=; char c=getchar(),f=;

    for(;c<''||''<c;c=getchar())if(c=='-')f=-;

    for(;''<=c&&c<='';c=getchar())x=x*+c-'';

    return x*f;

}

inline void write(ll x)

{

    static int buf[],len; len=;

    if(x<)x=-x,putchar('-');

    for(;x;x/=)buf[len++]=x%;

    if(!len)putchar('');

    else while(len)putchar(buf[--len]+'');

}

inline void writeln(ll x){write(x); putchar('\n');}

inline void writesp(ll x){write(x); putchar(' ');}

ll a[maxn];

int pos[maxn];

int n;

int main()

{

    n=read();

    pos[]=;

    int sum=;

    for(int i=;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 ;

        }

        else pos[sum]=i+;

    }

    return ;

}

loj6220

巴特西

【loj#6220】sum

最新文章

热门文章