链接: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。
当d≠0时,我们有(1,d+1),…,(n−d,n)和(d+1,1),…,(n,n−d)这些可能,共有2×(n−d−d−1+1)=2(n−d)种,因此一对数字相同的概率是2(n−d)n2。
求期望的话,乘上m−1就行了。
1 |
|
v1.5.2