Light Bulb Queries 2

Full solution

Precompute the following prefix products and prefix sums. All arithmetic is performed modulo $M=998\,244\,353$, and division means multiplication by a modular inverse.

$$C_0=1,\qquad C_i=\prod_{j=1}^{i}P_j$$ $$R_i=\sum_{j=1}^{i}C_{j-1}^{-1},\qquad U_i=\sum_{j=1}^{i}C_jR_j,\qquad V_i=\sum_{j=1}^{i}C_j,\qquad W_i=\sum_{j=1}^{i}P_j.$$

Set $R_0=U_0=V_0=W_0=0$. For a query , compute

$$H(l,r)=(U_r-U_{l-1})-R_{l-1}(V_r-V_{l-1}).$$

The answer is

$$2H(l,r)-(W_r-W_{l-1}).$$

Preprocessing takes $O(N)$ time, and each query takes $O(1)$ time. The total time complexity is $O(N+Q)$.

Each input probability is $P_i=\cfrac{a_i}{100}$ for an integer between and . Precompute these possible probabilities and their inverses. Then both and can be updated with one multiplication each. Add , not , when computing . All required inverses exist because every probability is nonzero.

Proof

A block of length $L$ contains $L^2$ ordered pairs of bulbs, allowing the same bulb to be chosen twice. Thus, the sum of squared block lengths equals the number of ordered pairs belonging to the same lit block.

For $l\leq a\leq b\leq r$, the two positions belong to the same lit block if and only if every bulb from through is lit. By independence, this event has probability

Subtask 1

Every bulb is guaranteed to light up. A query interval contains one block of length $r-l+1$, so its answer is $(r-l+1)^2$. Including input processing, the running time is .