Segments Covering

We need the probability that the random set of existing segments covers every cell exactly once.

The direct probability sum over all subsets looks nasty:

$$\sum_{S\text{ valid}} \left(\prod_{i\in S} \frac{p_i}{q_i}\right) \left(\prod_{i\notin S}\left(1-\frac{p_i}{q_i}\right)\right)$$

where “valid” means the selected segments cover every cell exactly once.

That formula is correct, but computing it subset-by-subset is obviously dead on arrival. $2^n$ is not a vibe.

Factor out all absent probabilities

For segment $i$, define

$$a_i=\frac{p_i}{q_i}.$$

Its absent probability is

$$1-a_i=\frac{q_i-p_i}{q_i}.$$

Now factor the absent probability out of every segment, no matter whether it is chosen or not:

$$\prod_i (1-a_i).$$

If segment $i$ is not chosen, this factor already accounts for it.

If segment $i$ is chosen, we need to replace $(1-a_i)$ by $a_i$, so the chosen segment contributes an extra multiplier

$$\frac{a_i}{1-a_i} = \frac{p_i/q_i}{(q_i-p_i)/q_i} = \frac{p_i}{q_i-p_i}.$$

Call this value $w_i$.

So the answer becomes:

$$\left(\prod_i \frac{q_i-p_i}{q_i}\right) \cdot \left(\sum_{S\text{ valid}} \prod_{i\in S} w_i\right).$$

Now the probability bookkeeping is mostly gone. We just need a weighted count of valid tilings.

What does a valid subset look like?

If every cell is covered exactly once, then the chosen segments cannot overlap, and they cannot leave gaps.

So the chosen segments form a perfect chain covering:

$$[1,m].$$

For example, a valid chain might look like:

$$[1,3], [4,4], [5,10].$$

The important thing: if the last chosen segment is $[l,r]$, then everything before it must exactly cover cells $1\ldots l-1$.

That screams prefix DP.

DP definition

Let

$$dp[x] = \text{total weight of ways to exactly cover cells }1\ldots x.$$

The empty prefix has one way:

$$dp[0]=1.$$

Now take a segment $[l,r]$ with weight $w$.

If we use it as the last segment of a cover ending at $r$, then cells before it must already be exactly covered up to $l-1$.

So this segment contributes:

$$dp[l-1]\cdot w$$

to $dp[r]$.

Therefore:

$$dp[r] \mathrel{+}= dp[l-1]\cdot \frac{p}{q-p}.$$

That is the whole trick. No interval graph madness, no inclusion-exclusion hell, just factoring probabilities so the remaining structure becomes a clean tiling DP.

Why this avoids double counting

Every valid selected subset has a unique last segment: the segment covering cell $m$ in the full problem, or covering cell $r$ for prefix $r$.

Remove that last segment $[l,r]$, and what remains is a valid exact cover of $1\ldots l-1$.

So every valid subset is counted exactly once by the transition that appends its final segment. Conversely, every DP transition appends a segment directly after an exact prefix cover, so it creates no gaps and no overlaps.

That gives a bijection. Fancy word, simple idea: nothing is lost, nothing is duplicated.

Modulo details

We work modulo

$$MOD=998244353.$$

Fractions are represented with modular inverses:

$$\frac{x}{y} \equiv x\cdot y^{-1}\pmod{MOD}.$$

Since $1\le p<q<MOD$, both $q$ and $q-p$ are nonzero modulo $MOD$, so inverses exist.

For each segment:

• multiply the global base by $\frac{q-p}{q}$,
• compute its DP weight as $\frac{p}{q-p}$,
• store the transition ending at $r$.

Then process positions from $1$ to $m$, applying all segments that end there.

Finally:

$$\text{answer}=dp[m]\cdot \prod_i \frac{q_i-p_i}{q_i} \pmod{MOD}.$$

Complexity

Each segment creates one transition, and each transition is processed once.

Time complexity:

$$O(n+m) \quad \text{plus modular inverses}$$

Using fast exponentiation for inverses, this is still easily fine for $2\cdot 10^5$.

Memory complexity:

$$O(n+m).$$