Codeforces 577B(dp)-白红宇的个人博客

Codeforces 577B(dp)

发布日期：2021-06-29 21:39:49 浏览次数：2 分类：技术文章

本文共 1470 字，大约阅读时间需要 4 分钟。

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

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 51 2 3
            output 
YES
            input 
1 65
            output 
NO
            input 
4 63 1 1 3
            output 
YES
            input 
6 65 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.

题意：求序列中是否存在任意数之和为一个数倍数。

代码：

#include
          
           using namespace std;const int maxn=1e6+6;int dp[maxn];int flag[maxn];int num[maxn];int main(){
              int n,number;    scanf("%d%d",&n,&number);    int i,t;    for(t=0;t

转载地址：https://dh-butterfly.blog.csdn.net/article/details/72330931 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Codeforces 804B

下一篇：数位dp

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章