codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1062C.md (2663B)


      1 Source: https://codeforces.com/problemset/problem/1062/C
      2 
      3 C. Banh-mi
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.
     22 
     23 First, he splits the Banh-mi into $n$ parts, places them on a row and numbers them from $1$ through $n$. For each part $i$, he defines the deliciousness of the part as $x_i \in \{0, 1\}$. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the $i$-th part then his enjoyment of the Banh-mi will increase by $x_i$ and the deliciousness of all the remaining parts will also increase by $x_i$. The initial enjoyment of JATC is equal to $0$.
     24 
     25 For example, suppose the deliciousness of $3$ parts are $[0, 1, 0]$. If JATC eats the second part then his enjoyment will become $1$ and the deliciousness of remaining parts will become $[1, \_, 1]$. Next, if he eats the first part then his enjoyment will become $2$ and the remaining parts will become $[\_, \_, 2]$. After eating the last part, JATC's enjoyment will become $4$.
     26 
     27 However, JATC doesn't want to eat all the parts but to save some for later. He gives you $q$ queries, each of them consisting of two integers $l_i$ and $r_i$. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range $[l_i, r_i]$ in some order.
     28 
     29 All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $10^9+7$.
     30 
     31 Input
     32 
     33 The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$).
     34 
     35 The second line contains a string of $n$ characters, each character is either '0' or '1'. The $i$-th character defines the deliciousness of the $i$-th part.
     36 
     37 Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query.
     38 
     39 Output
     40 
     41 Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 4 2  
     49 1011  
     50 1 4  
     51 3 4
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 14  
     58 3
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 3 2  
     65 111  
     66 1 2  
     67 3 3
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 3  
     74 1
     75 ```
     76 
     77 Note
     78 
     79 In the first example:
     80 
     81 * For query $1$: One of the best ways for JATC to eats those parts is in this order: $1$, $4$, $3$, $2$.
     82 * For query $2$: Both $3$, $4$ and $4$, $3$ ordering give the same answer.
     83 
     84 In the second example, any order of eating parts leads to the same answer.