The title mean ： Is to give n Number （a1, a2, ..., an） and m, Ask if you can get it from here n Choose some of the numbers （ Can't be empty ）, Make the sum of these numbers divisible m .

No secret , No idea at all ... Look at the explanation , There's a place I can't understand ： n > m The situation of . Ask for help from Wu Dongzi , I've been criticized for English >___<. Thanks to him , Step by step guide me .

It seems that many people also have this doubt . He said it was a special case optimization , Forgive me for being lazy , Just extract it ~

First of all, we need to know some parameters .

The prefix and Sl  = a1 + a2 + ... + al-1 + al

Sr = a1 + a2 + ... + al-1 + al + al+1 + ... + ar-1 + ar

Sr - Sl = al+1 + al+2 + ...ar-1 + ar

That translation is , If there are two prefixes and mod m equal （Sr = Sl(mod m) ）, Then there is the transformation from prefix sum to interval sum .

Sr = Sl (mod m)
==> Sr - Sl = 0 (mod m)
==> a[l+1] + a[l+2] .. + a[r] = 0 (mod m)
And by the n <= m The situation of , After is 01 Knapsack nest ~~ Don't write , What a tragedy = =
Or use it set simple ....
It's my turn to use the method （ They're all reference people , It's amazing ）
*****************************************
General train of thought ： Save various combinations of selected numbers , Find different results for various sums , Save in set In container mods in . There's another one to use set ：mods_tmp. Used to save the number of current processing a And mods Each part of and , But in the original mods And... That don't appear in . After a round of iterations , Put this mods_tmp Add to mods in . So we don't have to do it next time ~~~~ Be careful ,mod m At most, there will be m Seed result ：0, 1, 2, ..., m-1. So don't worry about overtime .
By the way, why do you insert in the code at the beginning 0, Because you can only select the current input a Well ~~~ Ha ha ha ·~~~
（1） It's better than that （2） fast （124ms）

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
using namespace std;

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE

int n, m;
while (scanf("%d%d", &n, &m) != EOF) {

int a, r;
set<int> mods;
set<int> mods_tmp;

mods.insert();
for (int i = ; i < n; i++) {
scanf("%d", &a);
for (set<int>::iterator it = mods.begin(); it != mods.end(); ++it) {
int r = (*it + a) % m;
if (r == ) {
printf("YES\n");
return ;
}
mods_tmp.insert(r);
mods_tmp.insert(a);
}
mods.insert(mods_tmp.begin(), mods_tmp.end());
mods_tmp.clear();
}
printf("NO\n");
}
return ;
}

（2） It's easy to understand , The compasses （218ms）

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
using namespace std;

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE

int n, m;
while (scanf("%d%d", &n, &m) != EOF) {

int a, r;
set<int> mods;
set<int> mods_tmp;

mods.insert();
for (int i = ; i < n; i++) {
scanf("%d", &a);
for (set<int>::iterator it = mods.begin(); it != mods.end(); ++it) {
int r = (*it + a) % m;
if (r == ) {
printf("YES\n");
return ;
}
mods_tmp.insert(r);
mods_tmp.insert(a);
}
mods.insert(mods_tmp.begin(), mods_tmp.end());
mods_tmp.clear();
}
printf("NO\n");
}
return ;
}

## codeforces 577B. Modulo Sum More related articles on problem solving report

1. Codeforces 577B Modulo Sum

http://codeforces.com/problemset/problem/577/B The question : Yes n Number , Find if there is a subsequence satisfying the sum of m Multiple Ideas : Use the backpack under the mold to make , Find out n It's the sixth power of ten , But there's a God ...

2. Codeforces 577B Modulo Sum： mathematics Conclusion 【 The sum of the selected numbers is m Multiple 】

Topic link :http://codeforces.com/problemset/problem/448/C The question : Here you are. n A digital , Given m. Ask if you can pick some numbers from them , So that the sum of these numbers is m Multiple . Answer key ...

3. codeforces D. Toy Sum Problem solving report

Topic link :http://codeforces.com/problemset/problem/405/D The title mean : from 1 - 1000000 Choose from n Number :x1,x2,...,xn, Yes x1-1, ...

4. Codeforces Round 665 Post game problem solving report （ temporary A-D）

Codeforces Round 665 Post game problem solving report A. Distance and Axis We set up $$B$$ spot Coordinate for $$x(x\leq n)$$. We know from the meaning of the title \[\mid(n-x)- ...

5. Codeforces Round 662 Post game problem solving report （A-E2）

Codeforces Round 662 Post game problem solving report Dream start to 1400+ The tragic story of A. Rainbow Dash, Fluttershy and Chess Coloring The problem is very simple , We ...

6. LeetCode 2 Add Two Sum Problem solving report

LeetCode 2 Add Two Sum Problem solving report LeetCode The second question is Add Two Sum First of all, let's look at the topic requirements : You are given two linked lists repres ...

7. LeetCode 1 Two Sum Problem solving report

LeetCode 1 Two Sum Problem solving report I heard it by chance leetcode This platform , There are not many questions in it 200 Multiple questions , I plan to finish it when I am free in my graduate school , Exchange ideas with more people who practice algorithms , definite ACM Algorithm product ...

8. LeetCode: Combination Sum Problem solving report

Combination Sum Combination Sum Total Accepted: 25850 Total Submissions: 96391 My Submissions Questi ...

9. Codeforces Round #277.5 Problem solving report

Stay up late again cf, Today is more than normal . It's not over yet, but I know F I can't make it , An hour and a half to contribute to F I still haven't -- There should be no one Hack. Write a problem-solving report = =. Problem solving report, such as the following : A topic : Choose Sort to do it directly , Since there is no requirement for optimal exchange times ...

## Random recommendation

1. json relevant , Browser open json Format api Interface , format ,chrome plug-in unit

stay chrome Install... In browser Google jsonview Plug ins can automatically format json Formatted data .

2. html5 Quick start （ Four ）—— JavaScript

Preface : 1.HTML5 It's developing very fast , It can be said that it is the standard configuration for front-end developers , In the e-commerce type APP It is widely used in many fields , This series of articles is arranged by myself , Try to eliminate those that are not commonly used in development , Take out the ones that are often used , Make friends in need really ...

3. ECharts Study （2）-- Nightingale in the pie chart

1. The last one talked about how to draw a simple histogram , This time it's a pie chart , Pie chart mainly shows the proportion of different categories of data in the total through the arc of the sector , Its data format is simpler than the histogram , Only one-dimensional values , There is no need to give a category . Because it's not in rectangular coordinates , the ...

4. 【Thinking in Java-CHAPTER 3】 The operator

priority assignment Object is using c=d, that c and d All point to the original only d The object that points to . Alias problems in method calls : When an object is passed as a parameter to a function , Function changes this parameter , The object passed in is changed : Self increase and self decrease Floating point ...

5. WebScarab Instructions

Installation instructions : Software is based on java Developed , So before installation , Require that your machine has been installed Java Running environment     Software specifications : One is used to analyze and use HTTP and HTTPS Protocol application framework , Can be used to learn HTTP I use agreements more to ...

6. Spring In the framework IOC and DI The difference between

Last time I was asked IOC and DI Difference time , I don't care much about , I was asked again yesterday , It's a bit of a pity . I've got some time tonight , Look at the spring Official documents . Find out ,IoC It's more like an idea ,DI It's an act . To reduce the coupling of programs , utilize spri ...

7. to Oracle The locked line unlocks

1. Find the database of serial#, To kill : select t2.username,t2.sid,t2.serial#,t2.logon_time from v$locked_object t1,v$s ...

8. Fried with gold JS from 0 At the beginning ------- Now nothing （1）

The new year is over . In retrospect, the only fun left was playing with friends at home . So there is this article . I'm sorry , I don't have a train of thought yet . Let me stroke . ... ... Give it a go ... ... Okay . Let's start today : (1) Sort out all of them first ...

9. use Arduino Making a QR code display

First map The scene is like this , I'll give it to you these days CS The system is a wechat payment function ,  But the generated QR code is on the front desk computer .. It's impossible for users to scan on the front desk computer ... And then he took it out N I bought it a year ago Arduino Made a two-dimensional code display . ...

10. BZOJ4218 : I don't know where it is

set up $degi[x]$ and $dego[x]$ It represents the in degree and out degree of each point respectively , Write out the limitations of linear programming : Objective function : $\max.\ \sum_{x=1}^n(dego[x]P[x]-degi[x]Q[x])$ ...