Codeforces Round #319 (Div. 2)B. Modulo Sum DP

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B. Modulo Sum

time limit per test

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2 seconds

memory limit per test

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?256 megabytes

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.

Sample test(s)

input

3 5
1 2 3

output

YES

Note

In the first sample test you can choose numbers?2?and?3, the sum of which is divisible by?5.

In the second sample test the single non-empty subsequence of numbers is a single number?5. Number?5?is not divisible by?6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers?3?on the ends.

In the fourth sample test you can take the whole subsequence.

?

題意：給你n,m，n個數，讓你從中找出任意數的和mod M==0

題解：背包dp

//1085422276
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<bitset>
#include<set>
#include<vector>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,127,sizeof(a));
#define memfy(a) memset(a,-1,sizeof(a))
#define TS printf("111111\n");
#define FOR(i,a,b) for( int i=a;i<=b;i++)
#define FORJ(i,a,b) for(int i=a;i>=b;i--)
#define READ(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define maxn 1000005
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
//****************************************
int hashs[maxn],a[maxn*3];
bool  dp[3][maxn];
int main()
{mem(hashs);int flag=0;int n=read(),m=read();FOR(i,1,n){scanf("%d",&a[i]);a[i]=a[i]%m;if(a[i]==0)a[i]=m;}dp[0][0]=true;dp[1][0]=true;for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){if(dp[1][j]){if(j+a[i]==m){puts("YES");return 0;}dp[0][(j+a[i])%m]=true;}}memcpy(dp[1],dp[0],sizeof(dp[0]));}cout<<"NO"<<endl;return 0;
}

?