P8139 [ICPC 2020 WF] Sweep Stakes

ICPC2020 WF L

You may have already won! In fact, you did already win! You won your very own island, in the deepest reaches of the unexplored ocean! Well, mostly unexplored. As it happens, there was a small military base there before you, and when they packed up and flew out they left behind an assortment of scraps, munitions, tunnels, $\ldots$ and unexploded defensive ordnance. That's right: You now possess your very own minefield. The minefield consists of an $m\times n$ grid, with any square of the grid holding 0 or 1 mines. Fortunately, you were able to recover the engineers' plans from when they deployed the mines. Unfortunately, the exact locations of the mines were never written down: the engineers had a preselected independent probability of deploying a mine in each square. However, you do know how many mines were placed in total. You would like to estimate how safe various parts of your island are. Write a program to compute the probability of mine counts over various subsets of the minefield.

The first line of input contains four integers $m$, $n$, $t$, and $q$, where $m$ and $n$ ($1 \leq m,n \leq 500$) are the dimensions of the minefield, $t$ ($0 \leq t \leq mn$) is the total number of mines, and $q$ ($0 \leq q \leq 500$) is the number of queries. The second line contains $m$ real numbers $p_1, p_2, \ldots, p_m$ ($0 \leq p_i \leq 0.1$ for all $i$, with at most six digits after the decimal point specified), and the third line contains $n$ real numbers $q_1, q_2, \ldots, q_n$ ($0 \leq q_j \leq 0.1$ for all $j$, with at most six digits after the decimal point specified). The preselected probability of the engineers placing a mine on square $(i, j)$ is $p_i + q_j$. All choices of whether to place a mine on a given square were made independently, and the value of $t$ is chosen so that the probability of deploying exactly $t$ mines is at least $10^{-5}$. Each of the remaining $q$ lines describes a single query. Each of those lines begins with an integer $s$ ($0 \leq s \leq 500$), followed by $s$ pairs of integers $i$ and $j$ ($1 \leq i \leq m$, $1 \leq j \leq n$), which are the coordinates of $s$ distinct squares in the grid.

For each query with $s$ squares, output $s+1$ real numbers, which are the probabilities of the $s$ given squares containing $0, 1, \ldots, s$ mines. Your answer should have an absolute error of at most $10^{-6}$.