codeforces#319BModuloSum(抽屉原理，dp)

作者：儒妹妹_761 | 来源：互联网 | 2023-09-24 16:30

B-ModuloSumTimeLimit:2000MSMemoryLimit:262144KB64bitIOFormat:%I64d&%I64uSubmitStatusDescri

B - Modulo Sum

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

You are given a sequence of numbers a₁, a₂, ..., 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.

Input

The first line contains two numbers, n and m (1 ≤ n ≤ 10⁶, 2 ≤ m ≤ 10³) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹).

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.

Sample Input

Input

3 5
1 2 3

Output

YES

Input

1 6
5

Output

NO

Input

4 6
3 1 1 3

Output

YES

Input

6 6
5 5 5 5 5 5

Output

YES

Hint

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.

背包还是理解的不够透彻．．

因为每次都是用那个一维形式的．

这道题的做法类似01背包.

此外还可以有一个优化...

当n>m的时候．．．根绝抽屉原理．．一定为yes..

复杂度可以从o(nm)优到　o(m^2)

 1 /*************************************************************************
 2     > File Name: code/#319/BB.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年09月15日 星期二 21时31分12秒
 6  ************************************************************************/
 7 
 8 #include
 9 #include
10 #include
11 #include
12 #include
13 #include
14 #include<string>
15 #include
16 #include<set>
17 #include
18 #include
19 #include
20 #include
21 #define y1 hust111qqz
22 #define yn hez111qqz
23 #define j1 cute111qqz
24 #define ms(a,x) memset(a,x,sizeof(a))
25 #define lr dying111qqz
26 using namespace std;
27 #define For(i, n) for (int i=0;i28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 const int N=1E3+7;
32 int n,m;
33 int a[N];
34 int dp[N][5];
35 int main()
36 {
37   #ifndef  ONLINE_JUDGE 
38 
39   #endif
40     cin>>n>>m;
41     if (n>m)
42     {
43     puts("YES");
44     return 0;
45     }
46     for (int i = 1 ; i <= n ; i++)
47     {
48     int x;
49     scanf("%d",&x);
50     a[i] = x % m;
51     }
52     int x = 0 ;
53     for ( int i = 1 ; i <= n ; i++)
54     {
55     
56     dp[a[i]][1-x] = 1;
57     for ( int j = 1 ; j )
58     {
59         if(dp[j][x])
60         {
61         
62         dp[(j+a[i])%m][1-x] = 1;
63         dp[j][1-x] = 1;
64         }
65     }
66     x = 1-x;
67     if (dp[0][x])
68     {
69         puts("YES");
70         return 0;
71     }
72     
73     }
74     puts("NO");
75     return 0;
76 
77 
78 
79   
80   
81  #ifndef ONLINE_JUDGE  
82   fclose(stdin);
83   #endif
84     return 0;
85 }

View Code

codeforces #319 B - Modulo Sum (抽屉原理，dp)

推荐阅读

function
Lua脚本深入解析：元表与元方法的应用

本文探讨了Lua中元表和元方法的使用，通过具体的代码示例展示了如何利用这些特性来实现类似C语言中的运算符重载功能。 ... [详细]

蜡笔小新 2024-11-27 19:31:10
function
拖拉切割直线

拖拉切割直线 ... [详细]

蜡笔小新 2024-11-27 19:20:38
char
13、单向链表

头文件：LinkList.hLinkList.cmain.cVS2 ... [详细]

蜡笔小新 2024-11-27 14:45:45
char
UVA 401 - 镜像回文字符串

本题探讨了如何判断一个字符串是否为普通回文、镜像回文或两者都不是。通过特定的字符映射表来实现字符串的镜像转换，并根据转换后的结果进行分类。 ... [详细]

蜡笔小新 2024-11-27 13:54:55
char
抽象工厂模式 c++

抽象工厂模式包含如下角色：AbstractFactory：抽象工厂ConcreteFactory：具体工厂AbstractProduct：抽象产品Product：具体产品https ... [详细]

蜡笔小新 2024-11-27 13:21:30
filter
Python全栈之旅：SQLAlchemy ORM中的外键与关系

本文探讨了SQLAlchemy ORM框架中如何利用外键和关系（relationship）来建立表间联系，简化复杂的查询操作。通过示例代码详细解释了relationship的定义、使用方法及其与外键的相互作用。 ... [详细]

蜡笔小新 2024-11-27 11:20:01
filter
最新CUUG OCP 071考试题库更新 - 12c版本（共70题）

本文提供最新的CUUG OCP 071考试题库，包含70道题目，旨在帮助考生更好地准备Oracle Certified Professional (OCP) 考试。 ... [详细]

蜡笔小新 2024-11-27 20:01:37
bash
四月个人任务：Linux基础操作与网络管理

本文介绍了两项主要任务：编写一个脚本来检测192.168.1.0/24子网中当前在线的IP地址，以及如何在Linux系统中挂载Windows网络共享目录。通过具体步骤和代码示例，帮助读者理解和掌握相关技能。 ... [详细]

蜡笔小新 2024-11-27 19:13:58
bash
解析 HTTP 头 'Vary: Accept-Encoding' 的作用与重要性

本文详细探讨了 'Vary: Accept-Encoding' HTTP 头的作用，即指导缓存系统（如代理服务器和 CDN）根据不同的编码需求存储和提供适当的资源版本，确保不同类型的客户端能够接收到适合自己的内容。 ... [详细]

蜡笔小新 2024-11-27 19:36:14
go
C语言初学者指南：利用二维数组与结构体实现贪食蛇游戏

本文面向非计算机专业背景的编程爱好者，介绍如何仅使用基础的C语言知识——二维数组和结构体，无需掌握复杂的数据结构如链表，即可编写一款经典的贪食蛇游戏。通过本教程，您将了解游戏开发的基本原理和实现方法。 ... [详细]

蜡笔小新 2024-11-27 18:05:55
jar
Python中调用Java代码的方法与实践

本文探讨了如何在Python环境中集成并调用Java代码，通过具体的步骤和示例展示了这一过程的技术细节。适合对跨语言编程感兴趣的开发者阅读。 ... [详细]

蜡笔小新 2024-11-27 17:54:57
window
如何在Android Studio中移除Activity的标题栏

本文介绍了在Android Studio中通过代码和配置文件两种方法来移除Activity的标题栏，并讨论了当Activity继承自AppCompatActivity时的特殊处理方法。 ... [详细]

蜡笔小新 2024-11-27 17:40:30
client
Redis 单节点安装指南

本文详细介绍了如何在Linux系统上安装和配置单节点的Redis服务，包括下载、解压、编译安装以及启动服务的具体步骤。 ... [详细]

蜡笔小新 2024-11-27 17:28:07
client
第25周工作与生活反思

本周六上午11点左右到达公司，回顾了一周的行业动态并完成了昨日的任务。下午主要解决了Axis2缓存问题以及DBS和KMS的相关技术难题。由于服务替换导致平台访问错误，经过多方查找未能解决，最终决定暂时搁置。此外，还分享了与朋友之间的沟通障碍及个人成长的思考。 ... [详细]

蜡笔小新 2024-11-27 16:38:51
client
Pandas中使用sort_values方法进行数据排序

本文介绍了如何利用Python的Pandas库中的sort_values方法对DataFrame对象进行排序。首先通过Numpy库生成随机数据，然后详细解释了DataFrame的创建过程及其参数，并重点探讨了sort_values方法的使用技巧。 ... [详细]

蜡笔小新 2024-11-27 15:54:29

儒妹妹_761

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章