B. Modulo Sum
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/577/problem/B
Description
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 Input
3 5
1 2 3
Sample Output
YES
HINT
题意
给你一堆数，然后问你是否有一些数加起来%m==0
题解：
当成背包dp做，空间为m，每一个物品的代价为a[i]就好了
注意滚动数组的时候，不要转移的时候被自己的状态转移了，注意一下就好了
代码：
//qscqesze
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000006
#define mod 1001
#define eps 1e-9
#define pi 3.1415926
int Num;
//const int inf=0x7fffffff;
const ll inf=;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************* int a[maxn];
bool dp[maxn][];
int main()
{
int n=read(),m=read();
for(int i=;i<=n;i++)
a[i]=read(),a[i]%=m;
int flag = ;
for(int i=;i<=n;i++)
{
dp[a[i]][-flag] = ;
for(int j=;j<m;j++)
{
if(dp[j][flag])
{
dp[(j+a[i])%m][-flag]=;
dp[j][-flag]=;
}
}
flag = -flag;
if(dp[][flag])
{
cout<<"YES"<<endl;
return ;
}
}
cout<<"NO"<<endl;
return ;
}