Description
Solution
考虑对于每一个人算贡献。
令 \(P(i)\) 表示这个人视野距离为 \(i\) 的概率， \(Q(i)\) 表示视野距离不小于 \(i\) 的概率，令 \(k\) 表示能够阻拦这个人视野的人的个数（当然不包括当前人）。
那么贡献即为：
\[\sum_{i=1}^{n}{i\times P(i)} \]把这个式子转化下为：
\[\sum_{i=1}^{n}{Q(i)} \]所以这时候只需要算出来 \(Q(i)\) 即可，那么：
\[Q(i)=\dfrac{(n-i+1)\cdot A_{n-k-1}^{i-1}\cdot (n-i)!}{n!} \]这个式子中 \((n-i+1)\) 表示当前人有 \(n-i+1\) 个位置可以选。
\(A_{n-k-1}^{i-1}\) 表示当前人前面的 \(i-1\) 个位置只能由不能阻拦当前人视野的人来选，一共有 \(n-k-1\) 个人。
\((n-i)!\) 就表示除了当前人和其前面的 \(i-1\) 人外，其他人全排列的方案数。
然后化简即可：
\[\begin{aligned} ans&=\sum_{i=1}^{n}{\dfrac{(n-i+1)\cdot A_{n-k-1}^{i-1}\cdot (n-i)!}{n!}}\\ &=\sum_{i=1}^{n}{\dfrac{(n-i+1)\cdot\dfrac{(n-k-1)!}{(n-k-i)!}\cdot (n-i)!}{n!}}\\ &=\dfrac{(n-k-1)!}{n!}\cdot\sum_{i=1}^{n}{\dfrac{(n-i+1)!}{(n-k-1)!}}\\ &=\dfrac{(n-k-1)!}{n!}\cdot (k+1)!\cdot\sum_{i=1}^{n}{C_{n-i+1}^{k+1}} \end{aligned} \]然后考虑这样一个式子：
\[\sum_{i=1}^{n}{C_{i}^{k}} \]这个式子的组合意义就是在 \(n+1\) 个不同元素中选取 \(k+1\) 个元素的方案数。这里相当于就是枚举选的元素中编号最大的，假设为 \(s\)，那么方案数就为 \(\sum\limits_{s=1}^{n+1}{C_{s-1}^{k}}=\sum\limits_{i=1}^{n}{C_{i}^{k}}=C_{n+1}^{k+1}\)。
所以 \(\sum\limits_{i=1}^{n}{C_{n-i+1}^{k+1}}=C_{n+1}^{k+2}\).
那么：
\[\begin{aligned} ans=&\dfrac{(n-k-1)!}{n!}\cdot (k+1)!\cdot C_{n+1}^{k+2}\\ =&\dfrac{(n-k-1)!}{(k+1)!}\cdot (k+1)!\cdot \dfrac{(n+1)!}{(k+2)!\cdot (n-k-1)!}\\ =&\dfrac{n+1}{k+2} \end{aligned} \]所以就可以线性求解了。
Code
代码
#include <bits/stdc++.h>
#ifdef ORZXKR
#include <debug.h>
#else
#define debug(...) 114514
#endif
using namespace std;
const int kMaxN = 305, kMaxA = 1005;
int n, x;
int sum[kMaxA];
double ans;
int main() {
cin >> n;
for (int i = 1, x; i <= n; ++i) {
cin >> x;
++sum[x];
}
for (int i = 1; i <= 1000; ++i) {
ans += sum[i] * (n + 1) * 1.0 / (n - sum[i - 1] + 1);
sum[i] += sum[i - 1];
}
cout << fixed << setprecision(2) << ans << endl;
return 0;
}