[AtCoderSoundHound18C] Ordinary Beauty(概率, 期望)

链接:https://soundhound2018-summer-qual.contest.atcoder.jp/tasks/soundhound2018_summer_qual_c

给你1~n这n个数,现在允许你随机在m个位置上方这n个数,问你放好后的数组中,相邻两个数字的差为d的数对的概率。

m个位置存在m-1对数,由于期望的线性可加性,我们知道答案为$(m-1)

×在m个数字中挑选出一对差为d的概率$。

d=0时,相邻两个数字相同的时候才会有贡献,则有一对数字相同的概率为nn2

d0时,我们有(1,d+1),,(nd,n)(d+1,1),,(n,nd)这些可能,共有2×(ndd1+1)=2(nd)种,因此一对数字相同的概率是2(nd)n2

求期望的话,乘上m1就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

double n, m, d;

signed main() {
// freopen("in", "r", stdin);
while(cin >> n >> m >> d) {
if(d == 0) printf("%.15f\n", (m-1)/n);
else printf("%.15f\n", 2.0*(n-d)*(m-1)/n/n);
}
return 0;
}
Code 401: 未经授权的操作,请检查你的AppId和AppKey.
Powered By Valine
v1.5.2