CF1462E2 Close Tuples (hard version)

这是该问题的困难版本。简单版本与困难版本的唯一区别在于 $k$ 和 $m$ 的约束条件。在本题中，你需要输出答案对 $10^9+7$ 取模后的结果。 给定一个长度为 $n$ 的序列 $a$，其中每个元素都是 $1$ 到 $n$ 之间的整数。该序列可能包含重复元素（即某些元素可以相等）。 请你求出有多少个 $m$ 元组，使得元组中的最大值与最小值之差不超过 $k$。形式化地说，你需要统计满足下列条件的 $m$ 个下标 $i_1 < i_2 < \ldots < i_m$ 的元组个数： $$ \max(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) - \min(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) \le k. $$ 例如，如果 $n=4$，$m=3$，$k=2$，$a=[1,2,4,3]$，那么有两个这样的三元组（$i=1, j=2, z=4$ 和 $i=2, j=3, z=4$）。如果 $n=4$，$m=2$，$k=1$，$a=[1,1,1,1]$，那么所有六种可能的二元组都满足条件。 由于结果可能非常大，你需要输出对 $10^9+7$ 取模后的答案。

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^5$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行包含三个整数 $n$、$m$、$k$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 100$，$1 \le k \le n$），分别表示序列 $a$ 的长度、元组中元素的个数以及元组中元素最大值与最小值的最大差值。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 行，每行一个整数，表示每个测试用例中满足条件的 $m$ 元组个数，对 $10^9+7$ 取模后的结果。

由 ChatGPT 4.1 翻译