Rare Coins (Codeforces 1948F)
Tags: Math, probabilities

There are $$$n$$$ bags numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th bag contains $$$a_i$$$ golden coins and $$$b_i$$$ silver coins.The value of a gold coin is $$$1$$$. The value of a silver coin is either $$$0$$$ or $$$1$$$, determined for each silver coin independently ($$$0$$$ with probability $$$\frac{1}{2}$$$, $$$1$$$ with probability $$$\frac{1}{2}$$$).You have to answer $$$q$$$ independent queries. Each query is the following:   $$$l$$$ $$$r$$$ — calculate the probability that the total value of coins in bags from $$$l$$$ to $$$r$$$ is strictly greater than the total value in all other bags. 

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of bags and the number of queries, respectively.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the number of gold coins in the $$$i$$$-th bag.The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^6$$$) — the number of silver coins in the $$$i$$$-th bag.Next $$$q$$$ lines contain queries. The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the description of the $$$j$$$-th query.Additional constraints on the input:   the sum of the array $$$a$$$ doesn't exceed $$$10^6$$$;  the sum of the array $$$b$$$ doesn't exceed $$$10^6$$$. 

Output: For each query, print one integer — the probability that the total value of coins in bags from $$$l$$$ to $$$r$$$ is strictly greater than the total value in all other bags, taken modulo $$$998244353$$$.Formally, the probability can be expressed as an irreducible fraction $$$\frac{x}{y}$$$. You have to print the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$.

Note: In both queries from the first example, the answer is $$$\frac{1}{4}$$$.

Sample Inputs:
2 2
1 0
0 2
2 2
1 1

4 3
2 3 4 5
1 0 7 3
3 3
2 3
1 4

Sample Outputs:
748683265 748683265

997756929 273932289 1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
(n, q) = map(int, input().split())
mod = 998244353
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
    a[i] += a[i - 1]
    b[i] += b[i - 1]
s = b[n]
l = s + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
c = [0] * (s + 1)
for i in range(s + 1):
    c[i] = comb(s, i)
for i in range(1, s + 1):
    c[i] += c[i - 1]
z = pow(inv[2], s, mod)
ans = []
for _ in range(q):
    (l, r) = map(int, input().split())
    u = b[r] - b[l - 1]
    v = 2 * (a[r] - a[l - 1]) - a[n]
    i = min(u + v - 1, s)
    ans0 = 0 if i < 0 else c[i] % mod * z % mod
    ans.append(ans0)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
inv2 = 499122177
(n, q) = map(int, input().split())
A = [0]
A.extend(map(int, input().split()))
for i in range(n):
    A[i + 1] += A[i]
B = [0]
B.extend(map(int, input().split()))
for i in range(n):
    B[i + 1] += B[i]
N = B[-1] + 1
fact = [1] * N
inv = [1] * N
fact_inv = [1] * N
for i in range(2, N):
    fact[i] = i * fact[i - 1] % MOD
    inv[i] = -(MOD // i) * inv[MOD % i] % MOD
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD
pwr = 1
for _ in range(1, N):
    pwr = pwr * inv2 % MOD
pref_cmb = [1] * N
for i in range(1, N):
    pref_cmb[i] = (pref_cmb[i - 1] + fact[N - 1] * fact_inv[i] % MOD * fact_inv[N - 1 - i] % MOD) % MOD
res = []
for _ in range(q):
    (l, r) = map(int, input().split())
    l -= 1
    g0 = A[r] - A[l]
    s0 = B[r] - B[l]
    g1 = A[-1] - g0
    s1 = B[-1] - s0
    if g0 + s0 <= g1:
        res.append(0)
    elif g0 > g1 + s1:
        res.append(1)
    else:
        k = s1 - g0 + g1
        ans = (1 - pwr * pref_cmb[k]) % MOD
        res.append(ans)
print(' '.join(map(str, res)))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
mod = 998244353
(n, m) = map(int, input().split())
gold = list(map(int, input().split()))
silver = list(map(int, input().split()))
total_s = sum(silver)
fac = [1] * (total_s + 1)
for i in range(1, total_s + 1):
    fac[i] = fac[i - 1] * i % mod
f = fac[total_s]
fac_rev = [1] * (total_s + 1)
fac_rev[-1] = pow(f, -1, mod)
for i in range(total_s - 1, 0, -1):
    fac_rev[i] = fac_rev[i + 1] * (i + 1) % mod
pre_comb = [1] * (total_s + 1)
for i in range(1, total_s + 1):
    pre_comb[i] = (pre_comb[i - 1] + f * fac_rev[i] * fac_rev[total_s - i]) % mod
pre_g = [0] * (n + 1)
pre_s = [0] * (n + 1)
for (i, x) in enumerate(gold, 1):
    pre_g[i] = pre_g[i - 1] + x
for (i, x) in enumerate(silver, 1):
    pre_s[i] = pre_s[i - 1] + x
y_ = pow(pow(2, total_s, mod), mod - 2, mod)
ans = []
for i in range(m):
    (l, r) = map(int, input().split())
    cur_g = pre_g[r] - pre_g[l - 1]
    res_g = pre_g[-1] - cur_g
    x = cur_g - res_g
    p = pre_s[r] - pre_s[l - 1]
    y = 0 if p + x - 1 < 0 else pre_comb[min(x + p - 1, total_s)]
    ans.append(str(y_ * y % mod))
print(' '.join(ans))