BestCoder Round #85 hdu5776 sum

时间：2022-09-25 21:31:19

sum

题意：

问题描述

给定一个数列，求是否存在连续子列和为m的倍数，存在输出YES，否则输出NO

输入描述

输入文件的第一行有一个正整数T，表示数据组数。

接下去有T组数据，每组数据的第一行有两个正整数n,m .

第二行有n个正整数x 表示这个数列。

输出描述

输出T行，每行一个YES或NO。

输入样例

2

3 3

1 2 3

5 7

6 6 6 6 6

输出样例

YES

NO

题解：

这题虽说是1001，但当时真的不会，最后问了学长才知道，要用什么鸽巢定理，大致是这样的：给你一个n个数的数列，一定有连续的m（m<=n）个数是n的倍数，可以简单证明下：

假设有一n个数的序列，把他们的前缀和存到S[i]数组中，代表从第1个到第i个相加的和，把他们全对n取余，那范围肯定只有0n-1这n个数，特判0，肯定yes，那只剩下1n-1了，如果没有0那n个数，不可能只有n-1种情况，所以必定有重复的，不妨假设S[i]%n == S[j]%n !=0 (i < j) 此时用(S[j]-S[i])%n肯定为0，也就是说i到j为连续的序列是n的倍数。

根据上面的证明，最后我们只要求一个Sn（1~n之和）对m取余，看是否有=0的情况，或者有两个相等的情况就yes，否则no。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PU puts("");

#define PI(A) cout<<A<<endl

#define SI(N) cin>>N

#define SII(N,M) cin>>N>>M

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<x<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 100000 + 9 ;

int a[MAXN],n,m;

ll b[MAXN];

int main()

{

    iostream::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int o;

    SI(o);

    while(o--)

    {

        set<int> si;

        ll sum=0;

        cle(b,0);

        SII(n,m);

        int fl=0;

        rep(i,n)

        {

            SI(a[i]);

            sum+=a[i];

            b[i]=sum;

            if (b[i]%m==0)

                fl=1;

            if (si.count(b[i]%m)) fl=1;

            si.insert(b[i]);

        }

        if (fl) puts("YES");

        else puts("NO");

    }

    return 0;

}

相关文章