Description
Analysis
对于每个女性，开一个vector记录可选的男性
扫一遍，可以O(1)算出该女性选择第i个男性的期望（推推公式发现是等比数列）
有了这个就好办啦，按女性为第一关键字男性第二关键字排个序，用树状数组记录下前面的女性选择比当前大的男性的概率和
O(nlogn)
在算期望时涉及除法运算，精度误差较大，所以要开long double或者强行不用等比数列直接乘多几次
Code
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long double db;
const int N=;
db P,BIT[N];
int n,m,num;
vector<int> a[N];
struct node
{
int x,y;
db p;
}b[N];
bool cmp(node a,node b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
int lowbit(int x)
{
return x&-x;
}
db get(int x)
{
db t=;
for(int i=x;i;i-=lowbit(i)) t+=BIT[i];
return t;
}
void add(int x,db y)
{
for(int i=x;i<=n;i+=lowbit(i)) BIT[i]+=y;
}
int main()
{
freopen("cross.in","r",stdin);
freopen("cross.out","w",stdout);
int x,y;
scanf("%d %d %Lf",&n,&m,&P);
fo(i,,m)
{
scanf("%d %d",&x,&y);
a[x].push_back(y);
}
fo(i,,n)
{
int s=a[i].size();
sort(a[i].begin(),a[i].end());
fo(id,,s-)
{
int j=a[i][id];
b[++num].x=i,b[num].y=j;
db t1=pow(-P,id)*P,t2=-pow(-P,s);
b[num].p=t1/t2;
}
}
sort(b+,b+num+,cmp);
db ans=;
fo(i,,num)
{
db t=get(n)-get(b[i].y);
ans+=b[i].p*t;
add(b[i].y,b[i].p);
}
printf("%.2Lf",ans);
return ;
}