题目背景

搬运自 Code+ 第 6 次网络赛。

---

这天，白大哥找到了小莉。

“cp 拿不出题了，题目全被 zgg 抢走了，这次就由你来出题吧。”

于是小莉在概统课上糊出了这道题。

题目描述

设有两个离散型随机变量 $X,Y$，已知其联合分布列。

由 $X,Y$ 的线性组合构造出 $n$ 个新的随机变量：令 $Z_i=a_iX+b_iY$，其中 $i=1,2,\dots,n$，$a_i,b_i$ 为已知实系数，且不存在两对相同的 $a_i,b_i$。

现在，从 $Z_1,Z_2,\dots,Z_n$ 中随机取出 $Z_i,Z_j,Z_k$，其中 $i,j,k$ 两两不同（即从 $\binom n3$ 种组合中，随机等概率地选选出一种组合），考虑如下三个命题：

• $p_1:Z_i-Z_j$ 与 $Z_j-Z_k$ 不相关；
• $p_2:Z_j-Z_k$ 与 $Z_k-Z_i$ 不相关；
• $p_3:Z_k-Z_i$ 与 $Z_i-Z_j$ 不相关；

请求出 $p_1,p_2,p_3$ 至少有一个为真的概率。

输入格式

第一行两个正整数 $w_x,w_y$，是用来描述 $X,Y$ 联合分布列的参数，表示若 $x\ge w_x+2333$ 或 $y\ge w_y+2333$，则 $P(X=x,Y=y)=0$。

接下来 $w_x$ 行中，第 $i$ 行有 $w_y$ 个实数，第 $j$ 个数表示 $P(X=i+2332,Y=j+2332)$，即 $X$ 取值为 $i+2332$ 且 $Y$ 取值为 $j+2332$ 的概率，记为 $p_{i,j}$。

接下来一行一个正整数 $n$，表示由 $X,Y$ 构造的随机变量的个数。

接下来 $n$ 行中，第 $i$ 行为两个实数 $a_i,b_i$，表示 $Z_i=a_i X+b_iY$。

输出格式

输出一行一个 $[0,1]$ 间的实数，表示题目所求的概率。

设我们的答案为 $ans$，你的输出为 $out$，那么当且仅当 $|ans-out|<10^{-6}$ 时，你的答案才能被认为是正确的。因此在输出时，请保留足够多的小数位数（但不要超过输出长度限制）。

2 2
0.25 0.25
0.25 0.25
4
-1 0
0 0
1 0
0 1

0.75000

提示

样例解释

【样例 1】

除 $(Z_1,Z_2,Z_3)$ 不合法外，其余组合都合法，故概率为 $\frac 34$。

【样例 2】

见题目目录下的 2.in 与 2.ans。

数据范围

• Subtask1（$20$ 分）：$n\le 100$。
• Subtask2（$30$ 分）：$n\le 300$。
• Subtask3（$50$ 分）：$n\le 1500$。

对于所有的输入数据，有 $2\le w_x,w_y\le 100$，$3\le n\le 1500$，$0 < p_{i,j} <1$，且 $\sum_{i\ge 2333} \sum_{j\ge 2333}p_{i,j}=1$，$|a_i|,|b_i|<10^9$。

提示

即使 $X,Y$ 不相关，$X,Y$ 也不一定独立。

可能用到的相关知识

本题中涉及到的随机变量都是离散型随机变量，并且取值为不小于 $2333$ 的整数。

两个随机变量 $X,Y$ 不相关当且仅当 $E(XY)=E(X)E(Y)$，其中 $E(X)$ 表示随机变量 $X$ 的期望。

设 $P(X=x)$ 表示 $X$ 的取值为 $x$ 的概率。关于 $X$ 的函数 $f(X)$ 也是一个随机变量，其期望为：

$$E[f(X)]=\sum_{x=2333}^{\infty} f(x)P(X=x)$$

显然，令 $f(X)=X$，就可以得到 $X$ 的期望为：

$$E(X)=\sum_{x=2333}^{\infty} xP(X=x)$$

对于关于 $X,Y$ 的二元函数 $Z=g(X,Y)$ 也是一个随机变量，设 $Y$ 的取值集合为 $D_Y$，则 $Z$ 的期望为：

$$E[g(X,Y)]=\sum_{x=2333}^{\infty}\sum_{y=2333}^{\infty}g(x,y)P(X=x,Y=y) $$

其中，$P(X=x,Y=y)$ 表示 $X$ 取值为 $x$ 且同时 $Y$ 取值为 $y$ 的概率。

对于题目中涉及的 $E(XY)$，令 $g(X,Y)=XY$ 即可算出。