sum
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5776
Description
Given a sequence, you're asked whether there exists a consecutive subsequence whose sum is divisible by m. output YES, otherwise output NO
Input
The first line of the input has an integer T (1≤T≤10), which represents the number of test cases.
For each test case, there are two lines:
1.The first line contains two positive integers n, m (1≤n≤100000, 1≤m≤5000).
2.The second line contains n positive integers x (1≤x≤100) according to the sequence.
Output
Output T lines, each line print a YES or NO.
Sample Input
2
3 3
1 2 3
5 7
6 6 6 6 6
Sample Output
YES
NO
##题意:
判断给定的数串中是否存在连续子串的和能被m整除.
##题解:
维护每个前缀和的余数即可. 如果有两个前缀和的余数相同,那么这两段之差构成的字串一定能被m整除.
WA了一发:cnt[0]要初始化为1.
##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 201000
#define mod 1000000007
#define inf 0x3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;
int n,m;
int cnt[5100];
int main(void)
{
//IN;
int t; cin >> t;
while(t--)
{
memset(cnt, 0, sizeof(cnt));
cin >> n >> m;
int sum = 0;
cnt[0]++;
for(int i=1; i<=n; i++) {
int x; scanf("%d", &x);
sum = (sum + x) % m;
cnt[sum]++;
}
bool flag = 0;
for(int i=0; i<m; i++) if(cnt[i] > 1) {
flag = 1; break;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}