MX731 C

__ryp__ · 2024-07-31 20:15:28 · 个人记录

还是非常有意思的组合题。

我们知道一条路径的长度是不大于 \log n 的，也就是说这条路径上有最多 \log n 个点。

由于这是一个伪二分查找，所以说每个点上的数与要找的 x 的关系是确定的。不妨设 L 表示小于 x 的数的数，也即向右拐，R 是向左拐的数量，以及 E 是相等的数量，显然 E 不大于一（这里直接搬了题解的符号）。

我们考虑确定的 L、R 和 E 对应多少个序列，也就是算一个固定的 y 对答案的贡献。

考虑 y \lt x，因为 y \gt x 的情况是对称的。（越来越像题解了）

首先 y 有 L 种选法，然后剩下的 L - 1 个链上的位置有 x - 2\choose L - 1，并乘上排列；同样的，R 的方案是 n - x\choose R，同样乘排列。剩下的位置任选，乘上排列是 (n - L - R - E)!。最终，一个 y\lt x 对答案的贡献是

对于 y\gt x，贡献是

对于 y = x，贡献是

（好像是吧）。

确定了 x、L、R 和 E，这串东西就可以 O(1) 出。