Modulo Sum(背包 + STL)

时间:2022-11-14 12:56:42
 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 bym.

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
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.

题意:

取任意个数的和能否组成M的倍数;宇神用背包写的,参谋了下,很聪明的解法,还可以用set做;

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e3 + ;
int num[MAXN * MAXN];
int v[MAXN * MAXN];
int dp[ * MAXN][MAXN];
int val[MAXN * MAXN];
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
memset(num, , sizeof(num));
memset(v, , sizeof(v));
memset(dp, , sizeof(dp));
memset(val, , sizeof(val));
int tp = ;
int temp;
int ans = ;
for(int i = ; i < n; i++){
scanf("%d", &temp);
if(temp == m){
ans = ;
}
if(!num[temp % m])
v[tp++] = temp % m;
num[temp % m]++;
}
n = tp;
/*
printf("tp = %d\n",tp);
for(int i = 0; i < tp; i++){
printf("v = %d num = %d \n", v[i], num[v[i] ]);
}puts("");
*/
tp = ;
for(int i = ; i < n; i++){
for(int j = ; j <= num[v[i]]; j <<= ){
if(j * v[i] % m == ){
ans = ;
}
num[v[i]] -= j;
val[tp++] = j * v[i] % m;
}
if(num[v[i]] > ){
if(v[i] * num[v[i]] % m == )
ans = ;
val[tp++] = v[i] * num[v[i]] % m;
}
}
/*
printf("tp = %d\n",tp);
for(int i = 0; i < tp; i++){
printf("v = %d num = %d \n", val[i], num[v[i] ]);
}puts("");
*/
dp[][v[]] = ;dp[][] = ;
// printf("ans = %d\n",ans);
for(int i = ; i < tp - ; i++){
for(int j = ; j <= m; j++){
if(dp[i][j]){
// printf("i = %d j = %d\n",i,j);
dp[i + ][j] = ;
if((j + val[i + ]) % m == ){
ans = ;
}
dp[i + ][(j + val[i + ]) % m] = ;
}
}
}
if(ans)puts("YES");
else puts("NO");
}
return ;
}

set:

#include<iostream>
#include<cmath>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
const int MAXN = 1e6 + ;
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
int temp, ans = ;
set<int>st, _st;
st.insert();
set<int>::iterator iter;
for(int i = ; i < n; i++){
scanf("%d", &temp);
for(iter = st.begin(); iter != st.end(); iter++){
if((*iter + temp) % m == ){
printf("YES\n");
return ;
}
_st.insert((*iter + temp) % m);
}
st.insert(_st.begin(), _st.end());
_st.clear();
}
puts("NO");
}
return ;
}

vector:

#include<iostream>
#include<cmath>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int MAXN = 1e6 + 100;
int vis[MAXN];
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
int temp, ans = 0;
vector<int>st, _st;
st.push_back(0);
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; i++){
scanf("%d", &temp);
if(ans)continue;
for(int i = 0; i < st.size(); i++){
int x = (st[i] + temp) % m;
if(x == 0){
ans = 1;
break;
}
if(!vis[x])vis[x] = 1,_st.push_back(x);
}
for(int i = 0; i < _st.size(); i++){
st.push_back(_st[i]);
}
_st.clear();
}
if(ans)puts("YES");
else puts("NO");
}
return 0;
}