[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$时，相邻两个数字相同的时候才会有贡献，则有一对数字相同的概率为$\frac{n}{n^2}$。

当$d≠0$时，我们有$(1,d+1),…,(n-d,n)$和$(d+1,1),…,(n,n-d)$这些可能，共有$2×(n-d-d-1+1)=2(n-d)$种，因此一对数字相同的概率是$\frac{2(n-d)}{n^2}$。

求期望的话，乘上$m-1$就行了。

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;
}