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

http://codeforces.com/problemset/problem/577/B

n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103)

sequence의 길이 n과 m 이 주어지는데 원소의 합이 m 으로 나누어 떨어지는 subsequence 가 있는지 없는지 판별 하는 문제이다.

처음엔 일종의 dp 로

dp[i][j] = subArray[~i] 의 subsequence 중 원소들의 합을 m으로 나눈나머지가 j 인 subsequence 가 있는지

로 매 배열의 원소마다 선택을 하는 경우와 선택을 하지 않는경우로 나누어서 배열을 update 해주는 식으로 했는데

생각해보니 그렇게 되면 시간 복잡도가 O(n*m) 이어서 TLE 가 난다.

좀 생각을 해봤는데 잘 모르겠어서 Editorial 을 봤는데 두가지 케이스로 나누어서 풀어야했다.

첫번째로, n>=m 인경우, 비둘기 집의 정리에 의해 pSum[i] (1<=i<=n) 을 m 으로 나눈 나머지가 같은 서로 다른 두 i 가 적어도 한 쌍 있거나 나머지가 0인 i가 적어도 하나 있을 수 밖에없다. 즉 무조건 YES다.

두번째로, n<m 인경우는 원래 내가 생각했던 방식대로 풀면된다. 그러면 O(m^2) 이기 때문에 시간내에 돌아간다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int n,m;
int dp[1003][1003];
int arr[1000003];
int main() {
    inp2(n,m);
    REP(i,1,n) inp1(arr[i]);
    if(n>=m) {
        printf("YES");
        return 0;
    }
    REP(i,1,n){
        FOR(j,m) dp[i][j]=dp[i-1][j];
        FOR(j,m) if(dp[i-1][j]) dp[i][(j+arr[i])%m] = 1;
        dp[i][arr[i]%m]=1;
    }
    if(dp[n][0]) printf("YES");
    else printf("NO");
    return 0;
}