AT1445 乱数生成 题解
Description
有一个机器会等概率从 \(1\) 到 \(n\) 的正整数中选出一个整数。显然地,这个机器运行 \(3\) 次后会得到 \(3\) 个整数。求这 \(3\) 个整数的中位数是 \(k\) 的概率。
数据范围:\(1\leqslant k\leqslant n\leqslant 10^6\)。
Solution
发现自己快到 CSP 了完全不会概率,于是随便在 AtCoder 上面找了个题玩玩。
首先我们发现,由于选取的整数个数为奇数,那么要想这 \(3\) 个数为 \(k\),选取的三个数中至少应该有一个数是 \(k\)。
我们不妨设所选的 \(3\) 个正整数为 \(a,b,c\),然后对 \(a,b,c\) 的取值情况进行分类讨论。以下设 \(p\) 为任意不等于 \(k\) 的正整数。
\(a=b=c=k\)。
显然,只有一种情况能够满足这个要求。\(a,b,c\) 中恰好有 \(2\) 个整数为 \(k\)。
显然,从其余的 \(n-1\) 个正整数中选出一个数都能够满足这类条件。然后考虑一般的情况,由于不同的排列有 \((k,k,p)\),\((k,p,k)\) 和 \((p,k,k)\) 三种,因此这类下一共有 \(3(n-1)=3n-3\) 种情况。\(a,b,c\) 中恰好有 \(1\) 个整数为 \(k\)。
另外一个数要么是在 \([1,k-1]\) 中(也就是有 \(k-1\) 种不同的取值情况),要么是在 \([k+1,n]\) 中(也就是有 \(n-k\) 种不同的取值情况)。又由于不同的排列一共有 \((k,p_1,p_2)\),\((k,p_2,p_1)\),\((p_1,k,p_2)\),\((p_2,k,p_1)\),\((p_1,p_2,k)\) 和 \((p_2,p_1,k)\) \(6\) 种,因此这类下一共有 \(6(k-1)(n-k)=6nk-6k^2-6n+6k\) 种情况。
把上面这三类整合在一起,因此一共有 \(6nk-6k^2-6n+6k+3n-3+1=6nk-6k^2-3n+6k-2\) 种情况。又因为所有不同的情况一共有 \(n^3\) 种。因此概率为:
\]
注意在代码实现中,由于允许的误差很小,答案需要用 long double
储存以保证精度。
代码就不贴了。
最新文章
- MongoDB 驱动以及分布式集群读取优先级设置
- iOS中AutoLayer自动布局流程及相关方法
- windows下python3.4安装scikit-learn
- html5 图片转base64预览显示
- 通过Web Deploy方式部署WCF
- objc runtime 动态增加属性
- 在msvc中使用Boost.Spirit.X3
- 关于Two-Pass标记连通域个数
- HDU 5996 dingyeye loves stone [阶梯Nim]
- java DOM
- Redhat Linux 配置Xmanager
- STL 小白学习(5) stack栈
- inode引起的Linux无法创建新文件,磁盘空间不足
- pyobjc-framework-Cocoa 5.1.2
- Intellij IDEA创建Maven Web项目<;转>;
- 【Python】ORM框架SQLAlchemy的使用
- NVMe到底是什么?用它的SSD有啥优势?
- mysql中修改密码的方式
- hdu 1856 More is better (并查集)
- Windows Server 2012 新特性:IPAM的配置