题目传送门(Codeforces GYM 103119L) 题目大意：一个长度为 n n n的随机生成的整数序列 { a i } \{a_i\} {ai}，序列中每个元素为 1 1 1~ n n n之间之间的整数，且为某个数字的概率均为 1 n \frac1n n1。现在要求你计算对于排列 { p i } \{p_i\} {pi}，在满足 p i ≤ a i p_i \leq a_i pi≤ai的情况下的期望值。
思路分析：首先可以知道 { a i } \{a_i\} {ai}序列一共有 n n n^n nn种， { p i } \{p_i\} {pi}序列由于要求从 1 1 1~ n n n数字组合，因此共有 n ! n! n!种排列方式。然后对于每个排列而言，满足条件的 { a i } \{a_i\} {ai}序列也有 n ! n! n!种。所以总共的排列有 n ! × n ! n! \times n! n!×n!种。
根据数学期望的定义：“实验中每次可能结果的概率乘以其结果的总和”，不难发现它实际上是算术平均的一种推广，类似于加权平均数，是总体的算数平均。对于本题目就是"平均数=排列数量
÷
\div
÷总数量"，即为：
E
(
n
)
=
n
u
m
_
o
f
_
p
e
r
m
u
t
a
t
i
o
n
t
o
t
a
l
_
n
u
m
=
n
!
×
n
!
n
n
E(n) = \frac{num\_of\_permutation}{total\_num} = \frac{n! \times n!}{n^n}
E(n)=total_numnum_of_permutation=nnn!×n! 从样例中可以发现数据范围十分毒瘤，但是只有前
9
9
9位的精度约束。因此可以直接Python直接搞。
from math import factorial
n = int(input())
print((factorial(n) ** 2) / (n ** n))
由于只约束了前
9
9
9位的精度，因此C++也可以直接搞：
#include
using namespace std;
signed main(){
int n = 0; cin >> n;
long double ans = 1.0;
for(int i = 2; i
关注
打赏
![]()
1662600635
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
