题目背景

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}$.

题目大意

你赢得了自己的岛屿，在未开发海洋的最深处！那里有一个小型军事基地，当他们收拾行李飞走时，留下了各种碎片、弹药、隧道、炸弹……以及未爆炸的防御弹药。你现在拥有了自己的雷区。

雷场由 $m\times n$ 的网格组成，网格的任何正方形都有 0 或 1 枚地雷。幸运的是，你能够从工程师部署地雷时恢复他们的计划。不幸的是，地雷的确切位置从未被写下来：工程师们在每个方格部署地雷的预先选择的独立概率。然而，你知道总共埋设了多少枚地雷。

你想估计一下你所在岛屿的各个部分有多安全。请编写一个程序来计算雷区各子集上地雷计数的概率。误差需小于 $10^{-6}$。

2 2 1 2
0.05 0.05
0.05 0.05
1 1 1
2 2 1 1 2

0.75 0.25
0.5 0.5 0

3 4 3 4
0.02 0.04 0.06
0.005 0.07 0.035 0.09
1 3 2
3 1 4 2 4 3 4
4 1 2 2 3 3 1 1 4
8 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3

0.649469772 0.350530228
0.219607636 0.527423751 0.237646792 0.015321822
0.267615440 0.516222318 0.201611812 0.014550429 0
0.054047935 0.364731941 0.461044157 0.120175967 0 0 0 0 0