题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4481

太弱了这种题都要看半天TJ...:https://blog.csdn.net/chai_jing/article/details/72870473

等比数列求和的公式是 ( a1 * ( 1 - q^n ) ) / ( 1 - q ),如果 n 是无穷大的话,若 0 < q < 1,那么 q^n 趋近于 0 ,所以公式就成了 a1 / ( 1 - q );

计算每个女性选中每个男性的概率,放进树状数组里求逆序对期望即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double ld;
int const maxn=5e5+;
int n,m;
ld f[maxn],ans,p;
struct N{int a,b;}q[maxn];
bool cmp(N x,N y){return (x.a==y.a)?x.b<y.b:x.a<y.a;}
void add(int x,ld v){for(;x<=n;x+=(x&-x))f[x]+=v;}
ld query(int x){ld ret=; for(;x;x-=(x&-x))ret+=f[x]; return ret;}
int main()
{
scanf("%d%d%Lf",&n,&m,&p);
for(int i=;i<=m;i++)scanf("%d%d",&q[i].a,&q[i].b);
sort(q+,q+m+,cmp);
for(int i=,lst;i<=m;i=lst+)
{
lst=i; ld up=p,dn=;
while(q[lst+].a==q[lst].a)lst++;
for(int j=;j<=lst-i+;j++)dn*=(-p);
dn=-dn;
for(int j=i;j<=lst;j++)
{
if(j!=i)up*=(-p);
add(q[j].b,up/dn);
ans+=(up/dn)*(query(n)-query(q[j].b));
}
}
printf("%.2Lf\n",ans);
return ;
}

最新文章

  1. jahshaka 2.0 环境配置
  2. [MFC] 梳理一个简单的图片处理桌面软件中用到的MFC控件技巧
  3. C# 根据身份证号码获取简易信息
  4. SQL SERVER2012中使用游标来备份数据库
  5. SeaJS 模块化加载框架使用
  6. ArcGIS API for Silverlight加载google地图(后续篇)
  7. php多维数组化一维数组
  8. Winfrom巧用Using设置鼠标为WaitCursor
  9. MGTemplateEngine 模版引擎简单使用(转)
  10. TensorFlow-相关 API(学习笔记 )
  11. MyBatis源码解析(六)——DataSource数据源模块之池型数据源
  12. vue常见前端UI库
  13. 【算法】map的应用
  14. .net core build docker image
  15. devstack 部署 openstack(pick/mitaka)
  16. WIN10系统右击开始菜单没有属性选项怎么办
  17. [Warning] TIMESTAMP with implicit DEFAULT value is deprecated
  18. datagridview 如何禁止行被选中
  19. python中web应用与mysql数据库交互
  20. 修改tcp数据内容

热门文章

  1. THREE.js代码备份——canvas - geometry - earth(球体贴纹理)
  2. 错误处理:vmware下克隆centos7配置静态ip地址网卡问题
  3. (转)Arcgis for javascript实现百度地图ABCD marker的效果
  4. java同学毕业后学习之路建议
  5. maven常用dos命令
  6. sublime右键菜单,anaconda设置
  7. 洛谷——P2574 XOR的艺术
  8. Mysql数据库操作(二)
  9. PAT 1093. Count PAT&#39;s
  10. Codeforces 912D - Fishes