CF1462E2 Close Tuples (hard version) 题解

· · 题解

困难版题解。

这里需要注意到一个关键性质，序列的顺序是无关的。题目的本质就变成选 m 个数，极差小于等于 k。

排序之后就好做了，钦定一个点为最小值，向后面找满足条件的数的个数记为 x。则答案相当于是 \dbinom{x}{m-1} （除去钦定的这一个）。

找的过程可以采用二分或者数据结构，因为数字比较大，最好算一下逆元。

示例代码。