bzoj2720: [Violet 5]列队春游(概率期望+组合数学)
Description
Input
Output
Sample Input
Sample Output
HINT
数学题都这么骚的么……怎么推出来的啊……我是真的想不出来……
首先,要算总的视野期望,我们可以把每一个小朋友的视野期望算出来,然后求和
于是考虑如何计算每个小朋友的视野期望,设$L$表示视野长度,视野期望为$ans$,则有$$ans=\sum_{i=1}^n i*P(L=i)$$
然后考虑转化一下,我们原来是枚举视野长度然后考虑概率,那么我们换一个想法,考虑它前面的第$i$个人如果被看到就会对答案有$1$的贡献,那么我们只要考虑前面的第$i$个人会被看到的概率就可以了,可以直接求和$$ans=\sum_{i=1}^n P(L\geq i)$$
考虑概率如何计算。设不小于第$i$个小朋友身高的有$k$个人(不包括他自己),那么$$ans=\sum_{i=1}^n \frac{(n-i+1)A^k_{n-i}}{A^{k+1}_n}$$
上面的式子意思就是,会挡住小朋友的人包括自己随便放总共有$A^{k+1}_n$种情况,其中那些会挡住小朋友的人不能放在小朋友前面的$i-1$个位置,也不能放在小朋友的位置,所以方案数为$A^k_{n-i}$,然后又因为小朋友自己有$n-i+1$个位置可以放,所以乘上一个$n-i+1$
然后考虑乱推式子$$ans=\sum_{i=1}^n \frac{(n-i+1)\frac{(n-i)!}{(n-i-k)!}}{\frac{n!}{(n-k-1)!}}$$
$$ans={\frac{(n-k-1)!}{n!}}\sum_{i=1}^n \frac{(n-i+1)!}{(n-i-k)!}$$
$$ans={\frac{(n-k-1)!}{n!}}(k+1)!\sum_{i=1}^n \frac{(n-i+1)!}{(n-i-k)!(k+1)!}$$
$$ans={\frac{(n-k-1)!}{n!}}(k+1)!\sum_{i=1}^n C_{n-i+1}^{k+1}$$
$$ans={\frac{(n-k-1)!}{n!}}(k+1)!C_{n+1}^{k+2}$$
$$ans=\frac{n+1}{k+2}$$
然后对每一个高度都带进去做就行了
ps:一开始没想通倒数第二行怎么化出来的……后来发现是自己组合数姿势不够……把求和拆开来然后前面加上一项$C_1^{k+2}$然后用组合数递推公式带进去化一下就好了……
时间复杂度$O(n)$
//minamoto
#include<bits/stdc++.h>
using namespace std;
const int N=;
int h[N],n,sum;double ans;
int main(){
scanf("%d",&n);
for(int i=,x;i<=n;++i)
scanf("%d",&x),++h[x];
for(int i=;i<=;++i) ans+=1.0*h[i]*(n+)/(n-sum+),sum+=h[i];
printf("%.2lf\n",ans);
return ;
}
最新文章
- AE+C# 版本更新问题 命名空间“ESRI”中不存在类型或命名空间名称“Arcgis”(是缺少程序集引用吗?)
- VBA 实现批量excel文件复制
- Virtual DOM 算法
- [ZZ]良好的编码习惯
- Java基础知识强化之集合框架笔记62:Map集合之HashMap嵌套HashMap
- Unity用户自定义圆角头像
- 用css怎么制作下拉列表
- IDEA github的应用
- 关于cocos2d-x面试的问题
- SimpleDateFormat用法大全及易错分析
- FFPLAY的原理(五)
- 并发包 concurrent(一) Atomic
- BZOJ4698 差分 + 二分 + SA
- 使用CSS选择器定位页面元素
- mysql分页优化方法
- MFC 如何为控件关联变量
- ubuntu中查看各种设备和资源的命令汇总
- C#实现在注册表中保存信息
- 神经网络损失函数中的正则化项L1和L2
- linux随机数
热门文章
- 怎么删除";自豪地采用WordPress";
- PAT (Advanced Level) 1039. Course List for Student (25)
- BZOJ——T 1707: [Usaco2007 Nov]tanning分配防晒霜
- hdu——3861 The King’s Problem
- 2017icpc乌鲁木齐网络赛Colored Graph (构造)
- 解决Win7 64bit + VS2013 使用opencv时出现提“应用程序无法正常启动(0xc000007b)”错误
- POJ-2240 -Arbitrage(Bellman)
- 理解Android ANR的触发原理(转)
- glTF格式初步了解
- AIDL/IPC Android AIDL/IPC 进程通信机制——超具体解说及使用方法案例剖析(播放器)