codeforces 577B B. Modulo Sum(水题)

时间：2023-03-08 17:38:53
codeforces 577B B. Modulo Sum(水题)

题目链接：

B. Modulo Sum

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence of numbers a1, a2, ..., an, and a number m.

Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m.

Input

The first line contains two numbers, n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output

In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.

Examples
input
3 5
1 2 3
output
YES
input
1 6
5
output
NO
input
4 6
3 1 1 3
output
YES
input
6 6
5 5 5 5 5 5
output
YES

题意：

能否找到一个子序列的和能被m整除;

思路：

有一道hdu的水题就是这样的,以前傻傻的居然不会做;就是把余数拿出来搞搞就好了;

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bits/stdc++.h>

#include <stack>

#include <map>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());

    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());

    F && (num=-num);

}

int stk[70], tp;

template<class T> inline void print(T p) {

    if(!p) { puts("0"); return; }

    while(p) stk[++ tp] = p%10, p/=10;

    while(tp) putchar(stk[tp--] + '0');

    putchar('\n');

}

const int mod=1e9+7;

const double PI=acos(-1.0);

const int inf=1e9;

const int N=1e6+20;

const int maxn=1e3+110;

const double eps=1e-12;

int n,m,a[N],vis[maxn],temp[maxn];

int main()

{

    read(n);read(m);

    int flag=0;

    For(i,1,n)read(a[i]);

    vis[0]=1;

    For(i,1,n)

    {

        a[i]%=m;

        int t=(m-a[i])%m;

        if(vis[t]){flag=1;break;}

        mst(temp,0);

        for(int j=0;j<m;j++)

        {

            if(vis[j])temp[(j+a[i])%m]=1;

        }

        for(int j=0;j<m;j++)

            if(temp[j])vis[j]=1;

    }

    if(flag)cout<<"YES\n";

    else cout<<"NO\n";

    return 0;

}

　　

相关文章