题解：P1943 Local Maxima

· · 题解

P1943 Local Maxima

Problem

求一个排列的期望的前缀最值个数。

Sol

法一：

我们分段计算贡献。

对于第 p 位，贡献的期望为：

\sum_{i = p}^{n} \frac{A_{i-1}^{p-1}(n-p)!}{n!} =\sum_{i = p}^{n} \frac{(i-1)!(n-p)!}{n!(i-p)!}

先提出 n, p：

=\frac{(n-p)!}{n!}\sum_{i = p}^{n} \frac{(i-1)!}{(i-p)!}

发现是两个与 n，i 相关的排列数，且差为 p, p-1。可以考虑化为组合数。

=\frac{(n-p)!(p-1)!}{n!}\sum_{i = p}^{n} \binom{i-1}{i-p}

然后 \sum_{i\ge0}\binom{i+k}{i}=\sum_{i\ge0}\binom{i+k}{k}=\binom{n+k+1}{k+1}

=\frac{(n-p)!(p-1)!}{n!}\binom{n}{p} =\frac{1}p

因此答案为 \sum_{i} \frac1i。

法二：

DP。令 f_i 表示长为 i 的排列的答案。考虑插入第 i+1 个数。

如果插入位置在最后，局部最大值应 +1。如果插入的位置不在最后，前面的部分可以看成一个排列，然后最后一个数没有贡献。因此有转移：f_{i+1}=\frac1{i+1}(f_i+1+if_{i})=f_i+\frac1{i+1}。通项即为 \sum_i \frac 1i。

分段打表即可。

Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld table[] = { 0, 17.38845852, 18.08160569, 18.48707079, 18.77475286, 18.99789641, 19.18021797, 19.33436865, 19.46790004, 19.58568308, 19.69104359, 19.78635377, 19.87336515, 19.95340786, 20.02751583, 20.09650870, 20.16104722, 20.22167184, 20.27883026, 20.33289748, 20.38419077, 20.43298094, 20.47950095, 20.52395271, 20.56651233, 20.60733432, 20.64655504, 20.68429536, 20.72066301, 20.75575433, 20.78965588, 20.82244570, 20.85419440, 20.88496606, 20.91481902, 20.94380656, 20.97197744, 20.99937641, 21.02604466, 21.05202014, 21.07733795, 21.10203056, 21.12612812, 21.14965861, 21.17264813, 21.19512099, 21.21709989, 21.23860610, 21.25965951, 21.28027880, 21.30048150, 21.32028413, 21.33970222, 21.35875041, 21.37744254, 21.39579168, 21.41381019, 21.43150976, 21.44890151, 21.46599594, 21.48280306, 21.49933236, 21.51559288, 21.53159322, 21.54734158, 21.56284577, 21.57811324, 21.59315112, 21.60796620, 21.62256500, 21.63695374, 21.65113837, 21.66512462, 21.67891794, 21.69252359, 21.70594661, 21.71919184, 21.73226392, 21.74516732, 21.75790635, 21.77048513, 21.78290765, 21.79517774, 21.80729910, 21.81927530, 21.83110975, 21.84280579, 21.85436662, 21.86579531, 21.87709487, 21.88826817, 21.89931800, 21.91024707, 21.92105799, 21.93175328, 21.94233539, 21.95280669, 21.96316948, 21.97342598, 21.98357835, 21.99362868, 22.00357901, 22.01343131, 22.02318748, 22.03284940, 22.04241885, 22.05189759, 22.06128733 };
int n;
int main() {
    scanf("%d", &n);
    int B = 20000000;
    ld ans = table[n / B];
    for (int i = n / B * B + 1; i <= n; i++) ans += (ld)1 / i;
    printf("%.8Lf\n", ans);
    return 0;
}