当前位置：首页 > news >正文

【概率论，算法】排列的峰值期望

news 来源：原创 2025/8/3 4:21:09

Surtr1 的珂学难题

题目链接:https://ac.nowcoder.com/acm/contest/107965/E

给定一个长度为 $n$ 的排列 $p$ ，排列中任一位置如果满足以下条件，则称该位置为峰值：

位置 1：若存在元素，满足 $p [1] > p [2]$ ，则 $p [1]$ 为峰值。
位置 n：若存在元素， $p [n] > p [n - 1]$ ，则 $p [n]$ 为峰值。
位置 2 至 n-1：若 $p [i] > p [i - 1]$ 且 $p [i] > p [i + 1]$ ，则 $p [i]$ 为峰值。

Surtr1定义一个排列的价值为所有峰值位置的和，具体来说，对于排列 ${1,2,3\}$ 位置3为峰值位置，而位置1和2不是，所以该排列的价值为 3 ，对于排列 ${ 3,1,2\}$ ，位置1和3为峰值位置，而位置2不是，所以该排列的价值为 $1 + 3 = 4$ 。

现在有一个长度为 $n$ 的随机排列，求该随机排列价值的期望。
但是Surtr1的数学非常差，所以他想将这个问题交给你，你能帮他解决吗？

长度为 n 的排列是由 1 到 n 这 n 个整数，按任意顺序组成的数组，其中每个整数恰好出现一次。例如： ${2, 3, 1, 5, 4\}$ 是一个长度为 5 的排列。

而以下则不是有效的排列： ${1, 2, 2\}$ ，因为存在重复元素。 ${1, 3, 4\}$ ，因为包含了超出范围的数。

输入格式

输入一个正整数 $n$ $(2 \leq n \leq 10)$ ，代表随机排列的长度。

输出格式

输出一个字符串，表示期望值的不可约分数（形如 $A / B$ ）。即使结果为整数，也需要输出成分数形式（例如，1 应输出为 $1/1$ ）。

样例输入与输出

样例 1

输入：
3

输出：
8/3

对于 $n = 3$ ，有三个位置：

位置 1 的峰值概率为 $1/2$ ；
位置 2 的峰值概率为 $1/3$ ；
位置 3 的峰值概率为 $1/2$ 。

因此，期望值为：
$1 * (1/2) + 2 * (1/3) + 3 * (1/2) = (1 * 3 + 2 * 2 + 3 * 3) /6 = 16/6 = 8/3$
$设每个排列的价值为V_i$
$对于 n = 3 ，有以下 6 种情况：$
$\{1,2,3\}: 峰值位置为 3, \quad V_1 = 3;$
$\{1,3,2\}: 峰值位置为 2,\quad V_2 = 2;$
$\{2,1,3\}: 峰值位置为 1 和 3, \quad V_3 = 1+3 = 4;$
$\{2,3,1\}: 峰值位置为 2,\quad V_4 = 2;$
$\{3,1,2\}:峰值位置为 1 和 3,\quad V_5 = 1+3 = 4;$
$\{3,2,1\}: 峰值位置为 1,\quad V_6 = 1.$
$\frac{1}{6} \sum_{i=1}^{6} V_i = \frac{3+2+4+2+4+1}{6} = \frac{16}{6} = \frac{8}{3}.$

题解：
这道题正解是 $O (1)$ 的，但这里放成了 $O (N)$ 可做
设 $X$ 为随机排列的价值， $E (X)$ 为随机排列价值的期望，我们发现直接求无从下手，但是根据期望的线性性，我们可以把复杂事件（或复杂随机变量）拆成若干个“子事件”，通过求子事件的期望即可求出 $X$ 的期望
设 $0 - 1$ 随机变量 $X_i$ 表示第 $i$ 个位置是否为峰值( 当 $i>=2\&\&i<=n-1$ 时)
$X_i = \begin{cases} 1, & \text{} P[i] > P[i-1] \text{ \&\& } P[i] > P[i+1], \\ 0, & \text{else}. \end{cases}$
那么 $X_1+\sum_{i=2}^{n-1} X_i+X_n$
$E(X_1)+E\left[\sum_{i=2}^{n-1} X_i \right] + E(X_n) = E(X_1)+\sum_{i=2}^{n-1} E[X_i]+E(X_n).$
那么第 $i$ 个位置的期望 $E(X_i)$ 怎么求呢？很简单，我们只需要考虑 $i$ 这个位置 $p [i] > p [i - 1]$ 且 $p [i] > p [i + 1]$ 的概率即可。
在一个 $1 - n$ 的排列中，随机选 $k$ 个数，求第一个数比其他几个数小的概率
$\frac{(k-1)!}{k!} = \frac{1}{k}.$
那么对应到这题， $P(X_i)= \frac{1}{3}$ ，那么 $E(X_i)=\frac{i}{3}$ ，特别的 $E(X_1)=\frac{1}{2}$ ， $E(X_n)=\frac{n}{2}$
结果就是：
$\begin{aligned} \sum_{i=1}^{n} E(X_i) &= E(X_1) + \sum_{i=2}^{n-1} \frac{i}{3} + E(X_n) \\[1mm] &= \frac{1}{2} + \frac{1}{3}\left(\sum_{i=2}^{n-1} i\right) + \frac{n}{2} \\[1mm] &= \frac{1}{2} + \frac{1}{3}\left(\frac{n(n-1)}{2} - 1\right) + \frac{n}{2} \\[1mm] &= \frac{3(n+1)}{6} + \frac{n(n-1)-2}{6} \\[1mm] &= \frac{3n + 3 + n^2 - n - 2}{6} \\[1mm] &= \frac{n^2 + 2n + 1}{6} \\[1mm] &= \frac{(n+1)^2}{6}\,. \end{aligned}$
最后的结果通分一下即可
代码：

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}void solve(){ll n;cin>>n;ll zi=0,mu=0;zi = (n+1)*(n+1);mu = 6;//约分ll gd = gcd(zi,mu);zi/=gd,mu/=gd;cout<<zi<<'/'<<mu<<'\n';
}int main(){ios::sync_with_stdio(0),cin.tie(0);int _ = 1;while(_--)solve();
}

Surtr1 的珂学难题

输入格式

输出格式

样例输入与输出

样例 1

相关文章：