Modulo Sum
2 seconds
256 megabytes
standard input
standard output
You are given a sequence of numbers
a
1
,
a
2
, …,
a
n
, and a number
m
.
Check if it is possible to choose a non-empty subsequence
a
i
j
such that the sum of numbers in this subsequence is divisible by
m
.
The first line contains two numbers,
n
and
m
(
1 ≤
n
≤ 10
6
,
2 ≤
m
≤ 10
3
) — the size of the original sequence and the number such that sum should be divisible by it.
The second line contains
n
integers
a
1
,
a
2
, …,
a
n
(
0 ≤
a
i
≤ 10
9
).
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.
3 5 1 2 3
YES
1 6 5
NO
4 6 3 1 1 3
YES
6 6 5 5 5 5 5 5
YES
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 + 100; int num[MAXN * MAXN]; int v[MAXN * MAXN]; int dp[25 * MAXN][MAXN]; int val[MAXN * MAXN]; int main(){ int n, m; while(~scanf("%d%d", &n, &m)){ memset(num, 0, sizeof(num)); memset(v, 0, sizeof(v)); memset(dp, 0, sizeof(dp)); memset(val, 0, sizeof(val)); int tp = 0; int temp; int ans = 0; for(int i = 0; i < n; i++){ scanf("%d", &temp); if(temp == m){ ans = 1; } 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 = 0; for(int i = 0; i < n; i++){ for(int j = 1; j <= num[v[i]]; j <<= 1){ if(j * v[i] % m == 0){ ans = 1; } num[v[i]] -= j; val[tp++] = j * v[i] % m; } if(num[v[i]] > 0){ if(v[i] * num[v[i]] % m == 0) ans = 1; 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[0][v[0]] = 1;dp[0][0] = 1; // printf("ans = %d\n",ans); for(int i = 0; i < tp - 1; i++){ for(int j = 0; j <= m; j++){ if(dp[i][j]){ // printf("i = %d j = %d\n",i,j); dp[i + 1][j] = 1; if((j + val[i + 1]) % m == 0){ ans = 1; } dp[i + 1][(j + val[i + 1]) % m] = 1; } } } if(ans)puts("YES"); else puts("NO"); } return 0; }
set:
#include<iostream> #include<cmath> #include<cstring> #include<cmath> #include<algorithm> #include<set> using namespace std; const int MAXN = 1e6 + 100; int main(){ int n, m; while(~scanf("%d%d", &n, &m)){ int temp, ans = 0; set<int>st, _st; st.insert(0); set<int>::iterator iter; for(int i = 0; i < n; i++){ scanf("%d", &temp); for(iter = st.begin(); iter != st.end(); iter++){ if((*iter + temp) % m == 0){ printf("YES\n"); return 0; } _st.insert((*iter + temp) % m); } st.insert(_st.begin(), _st.end()); _st.clear(); } puts("NO"); } return 0; }
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;
}