更新历史

更新历史

2025-02-25

发布博客

洛谷传送门

题意

给定常数 kk。对于一个长度为 nn 的排列 aa，定义序列 f(a)={max⁡1≤i≤k{ai},max⁡2≤i≤k+1{ai},…,max⁡n−k+1≤i≤n{ai}}f(a)=\{\max_{1 \le i \le k} \{a_i\},\max_{2 \le i \le k+1} \{a_i\},\ldots,\max_{n-k+1 \le i \le n} \{a_i\}\}。

求出对于所有长度为 nn 的排列 pp，f(p)f(p) 中不同的数的个数之和。

思路

显然 ff 数组是由若干个互不相同的连续段构成的，于是我们只需要对连续段进行计数即可。

因为连续段的数量等于「相邻两个数不同的对数」再加 11，所以对于每一个 ii，考虑 f(p)i≠f(p)i+1f(p)_i \not= f(p)_{i+1} 的排列 pp 的数量。

注意到 f(p)if(p)_i 和 f(p)i+1f(p)_{i+1} 是两个相邻的长度为 kk 的区间的最大值，那么他们不相同等价于：这两个区间的并（一个长度为 k+1k+1 的区间）的最大值位于这个大区间的头或尾。而在一共 n!n! 个排列中，这个长度为 k+1k+1 的区间的最大值位于区间首尾的概率为 2k+1\dfrac{2}{k+1}，故共有 n!×2k+1n!\times \dfrac{2}{k+1} 个排列满足：对于某个固定的 ii，有 f(p)i≠f(p)i+1f(p)_i \not= f(p)_{i+1}。

这个式子与 ii 无关，所以直接将其乘上 ii 的数量（即 n−kn-k）即为答案。

故答案为 n!×2k+1×(n−k)+n!n!\times \dfrac{2}{k+1}\times (n-k)+n!（最后加的 n!n! 是因为每个排列有额外的 11 的贡献）。