首先求出每个女性接受某个男性的概率。这个概率显然是一个无穷等比数列求和。

  然后按编号从小到大考虑每个女性,维护出每个男性被选择的期望次数,BIT上查询后缀和即可。

  需要long double。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 500010
#define double long double
int n,m;
double p,tree[N],q[N],ans;
vector<int> a[N];
double query(int k){double s=;while (k) s+=tree[k],k-=k&-k;return s;}
void ins(int k,double s){while (k<=n) tree[k]+=s,k+=k&-k;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4481.in","r",stdin);
freopen("bzoj4481.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();cin>>p;
for (int i=;i<=m;i++)
{
int x=read(),y=read();
a[x].push_back(y);
}
int cnt=;
for (int i=;i<=n;i++)
{
sort(a[i].begin(),a[i].end());
int s=a[i].size();
double v=;
for (int j=;j<s;j++) q[j]=v*p,v*=-p;
for (int j=;j<s;j++) q[j]/=-v;
for (int j=;j<s;j++) ans+=q[j]*(cnt-query(a[i][j]));
for (int j=;j<s;j++) ins(a[i][j],q[j]);
cnt+=s>;
}
#undef double
double p=ans;printf("%.2f",p);
return ;
}

最新文章

  1. ASP.NET Core 中文文档 第二章 指南(1)用 Visual Studio Code 在 macOS 上创建首个 ASP.NET Core 应用程序
  2. 前端ps常用的小技巧
  3. 【FOL】第三周
  4. Autodesk 招人了,开发顾问,感兴趣的或者有推荐的人扔简历过来啊
  5. C++中各种容器特点总结
  6. 前端们,gulp该用起来了,简单的demo入门——gulp系列(一)
  7. SVN命令使用详解
  8. 怎么学习C++?
  9. Nmap / NetCat(nc) / 网络安全工具
  10. API风格
  11. noip模拟 市长选举
  12. 刚实习的自己-php
  13. IO模型浅析
  14. 经典Hash函数的实现
  15. 创建简单的npm脚手架
  16. vertx.FileResolver文件解析
  17. redis学习-散列表常用命令(hash)
  18. linux内核分析实践二学习笔记
  19. [No000013A]Windows WMIC命令使用详解(附实例)
  20. HELLO JAVA!

热门文章

  1. Docker 入坑教程笔记
  2. IDEA中解决Edit Configurations中没有tomcat Server选项的问题(附配置Tomcat)
  3. docker API 配置与使用
  4. thinkphp5一些文件夹用法
  5. flask 中访问时后台错误 error: [Errno 32] Broken pipe
  6. Python特别low的一个文字游戏
  7. logger模块的使用
  8. uva 508 - Morse Mismatches(摩斯码)
  9. maven中settings文件的配置
  10. 【WPF】创建基于模板的WPF控件(经典)