HDU 5776 sum （模拟）

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;

}