P14446 [ICPC 2025 Xi'an Practice] Zelda

Zelda is given integers $l, r$ ($l \leq r$) and she has two sequences $a$ and $b$ of length $n$, indexed from $1$ to $n$. Zelda will use these two sequences to play a game, which proceeds as follows: - Uniformly and randomly select an integer $x$ from the interval $[l, r]$. - For $i = 1, 2, \cdots, n$, execute the following operations in order: first let $x \gets \min(x, a_i)$, then let $x \gets \max(x, b_i)$. Zelda wants to know the expected value of the final $x$. Unfortunately, Zelda has forgotten some of the integers in sequences $a$ and $b$, so she wants you to calculate the expected value of the final $x$ when all forgotten integers are also uniformly and randomly selected from the interval $[l, r]$, modulo $10^9 + 7$. Since Zelda will play the game multiple times, you need to answer queries for multiple different values of $r$.

The first line of the input contains three integers $n, q, l$ ($1 \leq n, l \leq 200$, $1 \leq q \leq 5 \times 10^4$), indicating the length of the two sequences, the number of times Zelda plays the game, and the lower bound for uniform random selections. The next line of the input contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$ ($a_i = 0$ or $l \leq a_i \leq 200$). $a_i = 0$ means the integer was forgotten by Zelda. The next line of the input contains $n$ non-negative integers $b_1, b_2, \cdots, b_n$ ($b_i = 0$ or $l \leq b_i \leq 200$). $b_i = 0$ means the integer was forgotten by Zelda. The next line of the input contains $q$ integers $r_1, r_2, \cdots, r_q$ ($l \leq r_i \leq 10^9$), indicating the value of $r$ each time Zelda plays a game.

The output contains $q$ lines, where the $i$-th line contains a single integer representing the answer for the $i$-th game, modulo $10^9 + 7$. Formally, let $M = 10^9 + 7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod M$. Output the integer equal to $p \cdot q^{-1} \pmod M$. In other words, output such an integer $x$ that $0 \leq x < M$ and $x \cdot q \equiv p \pmod M$.

In the first example, sequences $a = [2, 2]$ and $b = [0, 1]$ (where $b_1 = 0$ indicates a forgotten value), and there are $q = 5$ queries. In the first query, $l = r = 1$, so $x = b_1 = 1$ always. The game process is as follows: - Initially, $x = 1$. - Do operations with $i = 1$, $x \gets \min(x, a_1) = 1$ first, and then $x \gets \max(x, b_1) = 1$. - Do operations with $i = 2$, $x \gets \min(x, a_2) = 1$ first, and then $x \gets \max(x, b_2) = 1$. So the answer for the first query is $1$. In the second query, $l = 1, r = 2$, so $x, b_1$ should be selected from $[1, 2]$. - $x = 1, b_1 = 1$, $x$ becomes $1$ after all operations. - $x = 1, b_1 = 2$, $x$ becomes $2$ after all operations. - $x = 2, b_1 = 1$, $x$ becomes $2$ after all operations. - $x = 2, b_1 = 2$, $x$ becomes $2$ after all operations. Each case has probability $\frac{1}{4}$, so the answer for the second query is $\frac{1}{4} \times (1 + 2 + 2 + 2) = \frac{7}{4}$.