P14446 [ICPC 2025 Xi'an Practice] Zelda

Zelda 被给定了两个整数 $l, r$（满足 $l \leq r$），以及两个长度为 $n$ 的序列 $a$ 和 $b$（下标从 $1$ 开始计数）。Zelda 将使用这两个序列进行一个游戏，游戏规则如下： - 从区间 $[l, r]$ 中 **等概率随机** 选择一个整数 $x$。 - 对于每一个 $i = 1, 2, \cdots, n$，依次执行以下操作：首先令 $x \gets \min(x, a_i)$，然后令 $x \gets \max(x, b_i)$。 Zelda 想知道最终得到的 $x$ 的**期望值**。 然而，不幸的是，Zelda 忘记了序列 $a$ 和 $b$ 中的一些整数。因此，她希望你在这些被遗忘的整数也从区间 $[l, r]$ 中 **等概率随机选择** 的情况下，计算最终 $x$ 的期望值，并将结果对 $10^9 + 7$ 取模。由于 Zelda 将进行多次游戏，因此你需要针对多个不同的 $r$ 值回答查询。

输入的第一行包含三个整数 $n, q, l$（$1 \leq n, l \leq 200$，$1 \leq q \leq 5 \times 10^4$），分别表示两个序列的长度、Zelda 游戏的次数，以及随机选择的下界。 第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$（$a_i = 0$ 或 $l \leq a_i \leq 200$）。若 $a_i = 0$，则表示该数被 Zelda 忘记。 第三行包含 $n$ 个非负整数 $b_1, b_2, \cdots, b_n$（$b_i = 0$ 或 $l \leq b_i \leq 200$）。若 $b_i = 0$，则表示该数被 Zelda 忘记。 第四行包含 $q$ 个整数 $r_1, r_2, \cdots, r_q$（$l \leq r_i \leq 10^9$），表示每次游戏中对应的 $r$ 值。

输出共 $q$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次游戏的答案，对 $10^9 + 7$ 取模。 形式化地，设 $M = 10^9 + 7$。可以证明，答案可以表示为一个既约分数 $\dfrac{p}{q}$，其中 $p, q$ 为整数，且 $q \not\equiv 0 \pmod M$。你应输出满足以下条件的整数： $$ x \equiv p \cdot q^{-1} \pmod M, $$ 即输出满足 $0 \leq x < M$ 且 $x \cdot q \equiv p \pmod M$ 的整数。

在第一个示例中，序列为 $a = [2, 2]$，$b = [0, 1]$（其中 $b_1 = 0$ 表示被遗忘的值），且有 $q = 5$ 次查询。 在第一次查询中，$l = r = 1$，因此 $x = b_1 = 1$ 始终成立。游戏过程如下： - 初始时，$x = 1$。 - 当 $i = 1$ 时，首先执行 $x \gets \min(x, a_1) = 1$，然后执行 $x \gets \max(x, b_1) = 1$。 - 当 $i = 2$ 时，首先执行 $x \gets \min(x, a_2) = 1$，然后执行 $x \gets \max(x, b_2) = 1$。 因此第一次查询的答案为 $1$。 在第二次查询中，$l = 1, r = 2$，因此 $x$ 和 $b_1$ 均从区间 $[1, 2]$ 中随机选择。 - 若 $x = 1, b_1 = 1$，则最终 $x = 1$； - 若 $x = 1, b_1 = 2$，则最终 $x = 2$； - 若 $x = 2, b_1 = 1$，则最终 $x = 2$； - 若 $x = 2, b_1 = 2$，则最终 $x = 2$。 每种情况的概率均为 $\dfrac{1}{4}$，因此期望值为 $$ \dfrac{1}{4} \times (1 + 2 + 2 + 2) = \dfrac{7}{4}. $$ 翻译由 ChatGPT-5 完成