← 返回题目列表

Codeforces · 1461/C

C. 随机事件

中文机器翻译题面 查看原题

Ron 很高兴拥有长度为 $$$n$$$ 的排列 $$$a$$$。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

Ron 的排列受到以下类型的 $$$m$$$ 实验的影响:($$$r_i$$$, $$$p_i$$$)。这意味着$$$[1, r_i]$$$范围内的元素(换句话说,长度为$$$r_i$$$的前缀)必须以$$$p_i$$$的概率按升序排序。所有实验均按照输入数据中指定的顺序进行。

作为示例,让我们看一下排列 $$$[4, 2, 1, 5, 3]$$$ 和实验 ($$$3, 0.6$$$)。经过 $$$60\%$$$ 概率的实验后,排列将采用 $$$[1, 2, 4, 5, 3]$$$ 的形式,并且以 $$$40\%$$$ 概率保持不变。

您必须在 $$$m$$$ 实验之后确定排列完全按升序排序的概率。

输入

每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1 \le n, m \le 10^5)$$$ - 分别表示排列的长度和实验的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — 排列的内容。

每个测试用例的以下 $$$m$$$ 行均包含一个整数 $$$r_i$$$ 和一个实数 $$$p_i$$$ $$$(1 \le r_i \le n, 0 \le p_i \le 1)$$$ - 前缀的长度及其被排序的概率。所有概率最多保留 $$$6$$$ 小数位。

保证$$$n$$$和$$$m$$$的总和不超过$$$10^5$$$ ($$$\sum n, \sum m \le 10^5$$$)。

输出

对于每个测试用例,打印一个数字 - 在所有实验之后排列按升序排序的概率。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

4
4 3
4 3 2 1
1 0.3
3 1
4 0.6
5 3
4 2 1 3 5
3 0.8
4 0.6
5 0.3
6 5
1 3 2 4 5 6
4 0.9
5 0.3
2 0.4
6 0.7
3 0.5
4 2
1 2 3 4
2 0.5
4 0.1

输出 #1

0.600000
0.720000
0.989500
1.000000

注意

第一个测试用例的说明:可以证明最终排列是否排序仅取决于 $$$(4, 0.6)$$$ 实验中执行的排序。