Banh-mi (Codeforces 1062C)
Tags: Implement, math

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.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$$$.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$$$.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.All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $$$10^9+7$$$.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 100\,000$$$).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.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.

Output: Print $$$q$$$ lines, where $$$i$$$-th of them contains a single integer — the answer to the $$$i$$$-th query modulo $$$10^9 + 7$$$.

Note: In the first example:   For query $$$1$$$: One of the best ways for JATC to eats those parts is in this order: $$$1$$$, $$$4$$$, $$$3$$$, $$$2$$$.  For query $$$2$$$: Both $$$3$$$, $$$4$$$ and $$$4$$$, $$$3$$$ ordering give the same answer. In the second example, any order of eating parts leads to the same answer.

Sample Inputs:
4 2
1011
1 4
3 4

3 2
111
1 2
3 3

Sample Outputs:
14
3

3
1

Solution (Python):
def beki(a, b):
    waru = 10 ** 9 + 7
    ans = 1
    while b > 0:
        if 1 & b:
            ans = ans * a % waru
        b >>= 1
        a = a * a % waru
    return ans
(n, m) = map(int, input().split())
s = input()
ans = []
waru = 10 ** 9 + 7
ruiseki = [0] * (n + 1)
bekij = [1] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + int(s[i])
    bekij[i + 1] = bekij[i] * 2 % waru
for i in range(m):
    (l, r) = map(int, input().split())
    ko = ruiseki[r] - ruiseki[l - 1]
    ans.append((bekij[ko] - 1) * bekij[r + 1 - l - ko] % waru)
print('\n'.join(list(map(str, ans))))

Solution (Python):
def beki(a, b):
    waru = 10 ** 9 + 7
    ans = 1
    while b > 0:
        if 1 & b:
            ans = ans * a % waru
        b >>= 1
        a = a * a % waru
    return ans
(n, m) = map(int, input().split())
s = input()
ans = []
waru = 10 ** 9 + 7
ru = [0] * (n + 1)
b = [1] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + int(s[i])
    b[i + 1] = b[i] * 2 % waru
for i in range(m):
    (l, r) = map(int, input().split())
    ko = ru[r] - ru[l - 1]
    ans.append((b[ko] - 1) * b[r + 1 - l - ko] % waru)
print('\n'.join(list(map(str, ans))))

Solution (Python):
def beki(a, b):
    waru = 10 ** 9 + 7
    ans = 1
    while b > 0:
        if 1 & b:
            ans = ans * a % waru
        b >>= 1
        a = a * a % waru
    return ans
(n, m) = map(int, input().split())
s = input()
ans = []
waru = 10 ** 9 + 7
ruiseki = [0] * (n + 1)
bekij = [1] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + int(s[i])
    bekij[i + 1] = bekij[i] * 2 % waru
for i in range(m):
    (l, r) = map(int, input().split())
    ko = ruiseki[r] - ruiseki[l - 1]
    ans.append(str((bekij[ko] - 1) * bekij[r + 1 - l - ko] % waru))
print('\n'.join(ans))