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

原题: http://codeforces.com/contest/577/problem/B

---

题目大意: 给n个数, 问能不能找到其中的subsequence的合可以整除k.

---

分析: 额..这题开始做的时候考虑不周, 老是过不了, 后来加了个mod k 就过了.

看了答案后, 感觉思路差不多, 首先,当n>k时, 因为鸽巢原理, n个数,每个贡献1,肯定能找到合整除k的. 而当n<=k时, 我们可以通过记录数组当前数字与前一个数组合的模来判断是不是是否可以整除, 即: 如果合的模是0, 那么找到了答案返回YES.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int k = in.readInt();
        int[] nums = IOUtils.readIntArray(in, n);
        boolean[] mod = new boolean[k];
        for (int i = 0; i < n; i++) {
            boolean[] aux = mod.clone();
            for (int j = 0; j < k; j++) {
                if (aux[j])
                    mod[(j+nums[i])%k] = true;
            }
            mod[nums[i]%k] = true;
            if (mod[0]){
                out.print("YES");
                return;
            }
        }
        out.print("NO");
    }