Topic link :http://codeforces.com/problemset/problem/577/B

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])$ ...