P8139 [ICPC 2020 WF] Sweep Stakes

ICPC2020 WF L

你可能已经赢了！事实上，你确实赢了！你赢得了属于你自己的岛屿，位于未被探索的海洋最深处！嗯，几乎未被探索。事实是，在你之前那里有一个小型军事基地，当他们打包飞走时，留下了一些废料、弹药、隧道，等等，当然还有未爆炸的防御军火。没错：你现在拥有了你自己的雷区。 雷区由一个 $m \times n$ 的网格组成，网格的任意方格上可能有 0 或 1 个地雷。幸运的是，你找到了工程师们布雷时的计划。不幸的是，地雷的具体位置从未被记录下来：工程师们在每个方格上布雷的概率是预先独立选择的。然而，你知道总共放置了多少个地雷。 你想估计你岛屿各个部分的安全性。编写一个程序来计算雷区各个子集上的地雷数量的概率。

输入的第一行包含四个整数 $m$、$n$、$t$ 和 $q$，其中 $m$ 和 $n$（$1 \leq m,n \leq 500$）是雷区的维度，$t$（$0 \leq t \leq mn$）是地雷的总数，$q$（$0 \leq q \leq 500$）是查询的数量。第二行包含 $m$ 个实数 $p_1, p_2, \ldots, p_m$（对于所有 $i$，$0 \leq p_i \leq 0.1$，小数点后最多六位），第三行包含 $n$ 个实数 $q_1, q_2, \ldots, q_n$（对于所有 $j$，$0 \leq q_j \leq 0.1$，小数点后最多六位）。工程师在方格 $(i, j)$ 上放置地雷的预选概率是 $p_i + q_j$。是否在给定方格上放置地雷的选择是独立进行的，并且 $t$ 的值是选择的，使得恰好布置 $t$ 个地雷的概率至少为 $10^{-5}$。 接下来的每一行描述一个查询。每行以一个整数 $s$（$0 \leq s \leq 500$）开始，后面是 $s$ 对整数 $i$ 和 $j$（$1 \leq i \leq m$，$1 \leq j \leq n$），它们是网格中 $s$ 个不同方格的坐标。

对于每个包含 $s$ 个方格的查询，输出 $s+1$ 个实数，表示 $s$ 个给定方格中包含 $0, 1, \ldots, s$ 个地雷的概率。你的答案的绝对误差应不超过 $10^{-6}$。

题面翻译由 ChatGPT-4o 提供。