luogu#P11070. 「QMSOI R1」 三服同构

    ID: 14996 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划,dpSpecial JudgeO2优化概率论期望

「QMSOI R1」 三服同构

题目背景

前不久,三国杀上线了一位三服同构的赛事专属武将...

那这道题与SP孙策的关系呢?

题目描述

现在有 44 种扑克牌:红桃 A,红桃 K,黑桃 A,黑桃 K,小 Q 的手上现在有 nn 张黑桃牌,mm 张红桃牌,其中有 uu 张黑桃 A,vv 张红桃 A,而对手有 kk 张牌。

现在小 Q 知道对手第 ii 张牌点数为 A 的概率为 aia_i,接下来他将持续执行以下操作,直到他的回合结束。

  1. 若你手中有至少 11 张红桃 A 或红桃 K,则你必须等概率随机弃置 11 张花色为红桃的牌,并与对手进行决斗。
  2. 否则,你结束你的回合。

决斗的流程如下:

从对手开始,双方交替进行以下操作:

  1. 若其手上有至少 11 张红桃 A 或黑桃 A,则其必须等概率随机弃置 11 张点数为 A 的牌。
  2. 否则,其受到 11 点伤害,并结束此次决斗。

现在你想要知道在你的回合结束前,对手期望会受到多少点伤害。

输入格式

第一行 55 个整数分别表示 n,m,u,v,kn,m,u,v,k

第二行 kk 个实数,依次表示 a1,a2,,aka_1,a_2,\cdots,a_k

输出格式

输出一行一个实数,表示期望伤害。

本题使用 Special Judge 进行评测,只要你的答案与标准输出绝对误差10610^{-6} 以内,则判定答案正确。

2 2 1 1 2
0.2 0.8
1.670000000

提示

样例解释

可以得出对手牌中有 0,1,20,1,2 张 A 的概率分别为 0.16,0.68,0.160.16,0.68,0.16

当对手牌中有 00 张 A 时,无论小 Q 每次耗费的哪张红色牌,都能对对手造成伤害,所以这种情况期望伤害为 0.162=0.320.16*2=0.32

当对手牌中有 11 张 A 时,假设小 Q 第一次耗费的是 A 进行决斗,那对手打出 A 后,小 Q 就会打出一张黑桃 A,对手没 A 了就会受到伤害,而小 Q 的另一张红桃 K 依然能被耗费,以进行决斗对对手造成伤害,所以这种情况期望伤害为 0.680.52=0.680.68*0.5*2=0.68

当对手牌中有 11 张 A 时,假设小 Q 第一次耗费的是 K 进行决斗,那对手打出 A 后,小 Q 打出黑桃 A 或红桃 A 的概率就是相等的,然后对手没 A 了就会受到伤害,但是如果打出的是红桃 A 就无法再进行决斗了,而打出黑桃 A 另一张红桃 A 依然被耗费,进行决斗对对手造成伤害,所以这种情况期望伤害为 0.680.50.51+0.680.50.52=0.510.68*0.5*0.5*1+0.68*0.5*0.5*2=0.51

当对手牌中有 22 张 A,这时如果小 Q 先耗费的 A 进行决斗,那对手打出 A 后,小 Q 就会打出一张黑桃 A,对手再打出 A 后,小 Q 就会受到伤害,而小 Q 的另一张红桃 K 依然能被耗费,以进行决斗对对手造成伤害,所以这种情况期望伤害为 0.160.51=0.080.16*0.5*1=0.08

当对手牌中有 22 张 A,这时如果小 Q 先耗费的 K 进行决斗,双方就会各打出两张 A,然后敌人受到伤害,小 Q 就不能再进行决斗了,所以这种情况期望伤害同样为 0.160.51=0.080.16*0.5*1=0.08

所以对手受到的期望伤害就是 0.32+0.68+0.51+0.08+0.08=1.670.32+0.68+0.51+0.08+0.08=1.67

数据范围

本题使用 subtask 进行捆绑测试,每个 subtask 的具体分值如下: | 子任务 | 值域 | 分值 | | :----------: | :----------: | :----------: | | 00 | 1n,m101\le n,m\le 10 | 3030 | | 11 | 1n,m20001\le n,m\le 2000 | 7070 |

对于所有的数据,满足 1n,m,k2000,1u<n,1v<m1 \leq n,m,k \leq 2000,1\le u<n,1\le v <m