CF577B Modulo Sum

# 题面描述 给出 $1$ 个长度为 $n$ 的序列，以及 $1$ 个正整数 $m$。问这个原序列中是否存在非空子序列，使其元素之和能被 $m$ 整除。

第 $1$ 行，有 $2$ 个正整数，分别为原序列的长度 $n$ 和 除数 $m$。 （数据范围：$1 \leqslant n \leqslant 10^{6}$，$2 \leqslant m \leqslant 10^{3}$） 第 $2$ 行，有 $n$ 个自然数，表示该原序列的元素 $a_i$。 （数据范围：$0 \leqslant a_i \leqslant 10^{9}$）

仅 $1$ 行，如果存在符合条件的子序列，输出 **YES**，否则输出 **NO**。 # 样例解释 - 第 $1$ 组样例的解释： 存在符合条件的子序列 $\{2,3\}$，其元素之和为 $2 + 3 = 5$，$5$ 可以被 $5$ 整除。 - 第 $2$ 组样例的解释： 由于原序列中只有 $1$ 个元素，因此它只有 $1$ 个子序列 $\{5\}$，但显然 $5$ 不可以被 $6$ 整除。 - 第 $3$ 组样例的解释： 存在符合条件的子序列 $\{3,3\}$，其元素之和为 $3 + 3 = 6$，$6$ 可以被 $6$ 整除。 - 第 $4$ 组样例的解释： 选择整个原序列作为子序列，其元素之和为 $5 + 5 + 5 + 5 + 5 + 5 = 30$，$30$ 可以被 $6$ 整除。 Translated by Sooke

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.