HDU 5776 sum（鸽巢定理简单题）

题意：给一个长为 n 的串，问是否有子串的和是 m 的倍数。

思路：典型鸽巢定理的应用，但是这里 n，m 的大小关系是不确定的，如果 n >= m 根据定理可以很简单的判定是一定有解的，当 n < m 的时候就需要去具体寻找一下了，这里构造一个新串 Si = a1 + a2 + a3 + ...... + ai ，如果新串 Si % m = 0 自然就yes了，对于任意一个串 Si % m 的余数范围在 [ 0 , m - 1 ] ，如果出现两个余数相同的新串 S 则就能构成 ( Sj - Si ) % m = 0 （ i < j ）

/*************************************************************************

    > File Name: hdu5776.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年04月29日 星期六 23时00分52秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100010;

int a[maxn] , vis[maxn];

int t,n,m;

int S;

int main(){

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;i++)	scanf("%d",a+i);

		if(n>=m)	printf("YES\n");

		else{

			memset(vis,0,sizeof(vis));

			int ok = 0;

			S = 0;

			for(int i=1;i<=n;i++){

				S = ( S + a[i] ) % m;

				if(S==0)  {	ok = 1;	break;	}

				if(vis[S]){	ok = 1;	break;	}

				vis[S] = i;

			}

			if(ok)	printf("YES\n");

			else	printf("NO\n");

		}

	}

	return 0;

}

巴特西

HDU 5776 sum（鸽巢定理简单题）

最新文章

热门文章

巴特西

HDU 5776 sum（ 鸽巢定理简单题 ）

最新文章

热门文章

HDU 5776 sum（鸽巢定理简单题）