#286. [JSOI2015] 非诚勿扰

[JSOI2015] 非诚勿扰

[JSOI2015] 非诚勿扰

题目背景

JYY 赶上了互联网创业的大潮,为非诚勿扰开发了最新的手机 App 实现单身大龄青年之间的“速配”。然而随着用户数量的增长,JYY 发现现有速配的算法似乎很难满足大家的要求,因此 JYY 决定请你来调查一下其中的原因。

题目描述

应用的后台一共有 NN 个女性和 NN 个男性,他们每个人都希望能够找到自己的合适伴侣。为了方便,每个男性都被编上了 11NN 之间的一个号码,并且任意两个人的号码不一样。每个女性也被如此编号。

JYY 应用的最大特点是赋予女性较高的选择权,让每个女性指定自己的“如意郎君列表”。每个女性的如意郎君列表都是所有男性的一个子集,并且可能为空。如果列表非空,她们会在其中选择一个男性作为自己最终接受的对象。

JYY 用如下算法来为每个女性速配最终接受的男性:将“如意郎君列表”中的男性按照编号从小到大的顺序呈现给她。对于每次呈现,她将独立地以 PP 的概率接受这个男性(换言之,会以 1P1-P 的概率拒绝这个男性)。如果她选择了拒绝,App 就会呈现列表中下一个男性,以此类推。如果列表中所有的男性都已经呈现,那么中介所会重新按照列表的顺序来呈现这些男性,直到她接受了某个男性为止。显然,在这种规则下,每个女性只能选择接受一个男性,而一个男性可能被多个女性所接受。当然,也可能有部分男性不被任何一个女性接受。

这样,每个女性就有了自己接受的男性(“如意郎君列表”为空的除外)。现在考虑任意两个不同的、如意郎君列表非空的女性 aabb,如果 aa 的编号比 bb 的编号小,而 aa 选择的男性的编号比 bb 选择的编号大,那么女性 aa 和女性 bb 就叫做一对不稳定因素。

由于每个女性选择的男性是有一定的随机性的,所以不稳定因素的数目也是有一定随机性的。JYY 希望你能够求得不稳定因素的期望个数(即平均数目),从而进一步研究为什么速配算法不能满足大家的需求。

输入格式

输入第一行包含 22 个自然数 N,MN,M,表示有 NN 个女性和 NN 个男性,以及所有女性的“如意郎君列表”长度之和是 MM

接下来一行一个实数 PP,为女性接受男性的概率。

接下来 MM 行,每行包含两个整数 a,ba,b,表示男性 bb 在女性 aa 的“如意郎君列表”中。

输出格式

输出 11 行,包含一个实数,四舍五入后保留到小数点后 22 位,表示不稳定因素的期望数目。

样例 #1

样例输入 #1

5 5
0.5
5 1
3 2
2 2
2 1
3 1

样例输出 #1

0.89

提示

对于 100%100\% 的数据,1N,M5×1051\leq N,M\leq 5\times 10^50.4P<0.60.4\leq P<0.6

输入保证每个女性的“如意郎君列表”中的男性出现且仅出现一次。