分析
首先我们要求出对于第 \(i\) 位女性，她选择每个列表中的男性的概率是多少。
第一轮选择第一位的概率为 \(p\)，选择第二位的概率为 \(p(1-p)\)，以此类推。
显然第一轮选择第 \(k\) 位的概率为 \(p(1-p)^{k-1}\)。
假设列表中有 \(n\) 名男性，那么第二轮选择第一位的概率为 \(p(1-p)^n\)。
所以选择第一位的概率 \(P_1\) 为：
\[\begin{aligned} P_1&=\sum^{\infty}_{i=0}p(1-p)^{n\cdot i}\\ (1-p)P_1&=\sum^{\infty}_{i=1}p(1-p)^{n\cdot i}\\ \end{aligned} \]上下两式相减，得到：
\[\begin{aligned} (1-(1-p)^n)P_1&=\sum^{\infty}_{i=0}p(1-p)^{n\cdot i}-\sum^{\infty}_{i=1}p(1-p)^{n\cdot i}\\ (1-(1-p)^n)P_1&=p\\ P_1&=\frac{p}{1-(1-p)^n}\\ \end{aligned} \]这样我们就搞定了 \(P_1\)。
显然有：\(P_i=(1-p)P_{i-1}\)。
我们已经对于每个女性求出选择每个男性的概率，现在要考虑如何求得答案。
令 \(S_i\) 为第 \(i\) 个女性可选择的男性的集合。
答案就是下式：
\[\sum_{i=1}^n\sum_{b\in S_i}\sum_{j=1}^{i-1}\sum_{k=b+1}^n P(j\ 选\ k)\cdot P(i\ 选\ b) \]考虑从小到大枚举女性，这样就保证了后枚举的女性编号一定大于枚举过的。
我们可以维护一个序列，存储选择第 \(b\) 个男性的期望人数。
每次枚举 \(i\) 和 \(b\)，对答案的贡献就是 \([b+1, n]\) 这个区间内的期望人数。
在枚举完一个 \(i\) 后，将自己选择每个男性的概率累加到序列上。
单点修改，区间查询，用树状数组维护。
时间复杂度 \(O(m\log m)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
typedef long double f64_t;
struct BIT:vector<f64_t>
{
using vector::vector;
void modify(int p, f64_t x) {for(;p<size();p+=p&-p) at(p)+=x;}
f64_t query(int p) {f64_t r=0;for(;p;p-=p&-p) r+=at(p);return r;}
};
BIT ta(maxn);
vector<int> al[maxn];
int main()
{
int n, m;
f64_t p, ans=0;
cin>>n>>m>>p;
for(int a, b;m--;)
cin>>a>>b, al[a].emplace_back(b);
for(int i=1;i<=n;i++)
{
if(al[i].empty()) continue;
sort(al[i].begin(), al[i].end());
for(f64_t px=p/(1-pow(1-p, al[i].size()));auto b:al[i])
ans+=(ta.query(n)-ta.query(b))*px,
ta.modify(b, px), px*=1-p;
}
cout<<format("{:.2f}", ans);
}