本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 对答案的贡献是

$$ yL {x - 2\choose L - 1} \bigg(L-1\bigg)! {n - x\choose R} R!\bigg(n - L - R - E\bigg)! $$

对于 $y\gt x$，贡献是

$$ yR {n-x-1\choose R-1}\bigg(R-1\bigg)!{x-1\choose L}L!\bigg(n - L - R - E\bigg)! $$

对于 $y = x$，贡献是

$$ xn{x-1\choose L}L!{n-x\choose R}R!(n-L-R-E-1)! $$

（好像是吧）。

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

$x$ 是询问给出的，我们现在的目的就是怎么快速得出后三者。