Two pointers и подсчёт допустимых наборов — задача «Close Tuples» РАЗБОР

Что дано

Дан массив целых чисел $a_1, a_2, \ldots, a_n$ и два числа $m$ и $k$. Нужно найти количество наборов из $m$ индексов $i_1 < i_2 < \cdots < i_m$ таких, что среди значений $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ разница максимального и минимального не превышает $k$:

$\max(a_{i_1}, \ldots, a_{i_m}) - \min(a_{i_1}, \ldots, a_{i_m}) \le k.$

Ответ нужно вернуть по модулю $10^9 + 7$.

Ограничения

• $1 \le n \le 2 \cdot 10^5$
• $1 \le m \le 100$
• $0 \le k \le 10^9$
• $1 \le a_i \le 10^9$
• Сумма $n$ по всем тестам в одном входе — до $2 \cdot 10^5$.
• Время: 3 сек, память: 256 МБ.

Формат ввода

В первой строке — число тестов $T$. Для каждого теста: в первой строке $n$, $m$, $k$; во второй — $n$ чисел $a_1, \ldots, a_n$.

Формат вывода

Для каждого теста — одно число: количество наборов по модулю $10^9 + 7$.

Пример 1

Вход:

4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 0
1 3 1 2 2 3 4 4 1 2

Вывод:

2
6
1
0

Разберём первый пример руками

Массив 1 2 4 3, $m = 3$, $k = 2$. Отсортируем: 1 2 3 4. Нужно выбрать 3 элемента, у которых разница макс и мин $\le 2$.

Прямой перебор $\binom{4}{3} = 4$ варианта:

• {1, 2, 3} → 3 - 1 = 2 ✓
• {1, 2, 4} → 4 - 1 = 3 ✗
• {1, 3, 4} → 4 - 1 = 3 ✗
• {2, 3, 4} → 4 - 2 = 2 ✓

Ответ: 2.

Заметим важное: сортировка не меняет ответ, потому что набор — это набор значений, а не порядок. Мы считаем количество троек значений (с учётом возможных совпадений). Удобно работать с отсортированным массивом.

---

Идея решения

После сортировки набор индексов превращается в отрезок отсортированного массива (с подмножеством элементов внутри). Зафиксируем минимум: это какой-то элемент $a_i$ (после сортировки). Чтобы все элементы набора попадали в окно $[a_i, a_i + k]$, нужно знать до какого индекса $r$ значение массива ещё $\le a_i + k$.

После сортировки массив неубывающий, поэтому для растущего $i$ граница $r$ тоже не уменьшается. Это монотонность, на которой работает шаблон two pointers: поддерживаем правый указатель $r$, сдвигаем его, пока $a_r \le a_i + k$, и переходим к следующему $i$ — суммарная работа $O(n)$.

Зафиксировав $a_i$ как минимум, остальные $m - 1$ элементов набора берём из «правого окна» $[i + 1, r]$. Длина окна — $r - i$ элементов. Количество способов выбрать $m - 1$ из $r - i$ — биномиальный коэффициент $\binom{r - i}{m - 1}$ (если $r - i \ge m - 1$, иначе 0).

Суммарный ответ:

$\sum_{i=1}^{n} \binom{r(i) - i}{m - 1}.$

Биномиальные коэффициенты считаются по модулю простого $p = 10^9 + 7$ через предвычисленные факториалы и обратные к ним. Поскольку $r - i \le n - 1 \le 2 \cdot 10^5$, достаточно факториалов до $n$.

Почему фиксация минимума корректна

Каждый набор $\{a_{i_1}, \ldots, a_{i_m}\}$ имеет ровно один минимум (по индексу — самый левый среди равных). Когда мы перебираем $i$ от $1$ до $n$ и принимаем $a_i$ за минимум, мы пересчитываем каждый набор ровно один раз — в тот момент, когда $i$ совпадает с минимальным индексом набора.

Тонкий момент: если несколько элементов массива равны, какой считать «минимумом»? После сортировки одинаковые элементы стоят рядом, и в качестве минимума мы берём самый левый среди них — индекс по отсортированному массиву. Остальные равные значения уходят в «правое окно» и учитываются как обычные кандидаты.

---

Решение: псевдокод

отсортировать a по неубыванию
предвычислить fact[0..n], inv_fact[0..n] по модулю p

r ← 0
ans ← 0
для i от 0 до n - 1:
    пока r < n и a[r] - a[i] ≤ k:
        r ← r + 1
    # окно — индексы [i, r), длина r - i
    # фиксируем a[i] как минимум, ещё m - 1 выбираем из r - i - 1 правых соседей
    window ← r - i - 1
    если window ≥ m - 1:
        ans ← (ans + C(window, m - 1)) mod p
вернуть ans

Сложность: $O(n \log n)$ на сортировку, $O(n)$ на проход двумя указателями, $O(n)$ на предвычисление факториалов. Итого $O(n \log n)$ на тест.

---

Код решения

Биномиальные коэффициенты по модулю — через факториалы и обратные. Обратное к $x$ по модулю простого $p$ ищется как $x^{p - 2}$ (малая теорема Ферма): pow(x, p - 2, p) в Python и power(x, p - 2) в C++. Считаем массив fact итеративно, inv_fact[n] — один раз через возведение в степень, остальные inv_fact[i] = inv_fact[i + 1] * (i + 1) mod p обратным проходом — это даёт $O(n)$ на всю таблицу.

Комментарии по реализации.

• Сдвиг правого указателя. Условие r < i + 1 нужно, чтобы при переходе к новому $i$ окно не «отставало»: $r$ должен быть как минимум $i + 1$ (минимум $a_i$ занят, остальные кандидаты — справа от него).
• Тип под $a_r - a_i$. Значения $a_i$ до $10^9$, $k$ до $10^9$, разница умещается в int32, но для совместимости с возможным расширением условий безопаснее long long в C++.
• Размер таблицы факториалов. Берём $n \le 2 \cdot 10^5$ — максимум по условию. Считать заранее, до цикла по тестам: иначе на $T = 10^5$ тестах потеряем время на переинициализацию.
• binom(window, m - 1) при window < m - 1 возвращает 0 — это корректно: значит, в окне меньше элементов, чем нужно для набора.

---

Проверим на всех примерах из условия

Пример 1: n=4, m=3, k=2, массив 1 2 4 3

После сортировки: 1 2 3 4 (индексы 0..3).

• $i = 0$, $a_i = 1$. Двигаем $r$, пока $a_r - 1 \le 2$: $r = 0 \to 1 \to 2 \to 3$ (при $r = 3$, $a_3 = 4$, $4 - 1 = 3 > 2$, стоп). Конечный $r = 3$. Window = $3 - 0 - 1 = 2$. $\binom{2}{2} = 1$.
• $i = 1$, $a_i = 2$. $r = 3$, $a_3 = 4$, $4 - 2 = 2 \le 2$, $r \to 4$. Window = $4 - 1 - 1 = 2$. $\binom{2}{2} = 1$.
• $i = 2$, $a_i = 3$. $r = 4$. Window = $4 - 2 - 1 = 1$. $\binom{1}{2} = 0$.
• $i = 3$, $a_i = 4$. $r = 4$. Window = $4 - 3 - 1 = 0$. $\binom{0}{2} = 0$.

Сумма: $1 + 1 + 0 + 0 = 2$. Ответ: 2 ✓

Пример 2: n=4, m=2, k=1, массив 1 1 1 1

После сортировки: 1 1 1 1.

• $i = 0$: $r$ растёт до 4 (все элементы $\le 1 + 1$). Window = $4 - 0 - 1 = 3$. $\binom{3}{1} = 3$.
• $i = 1$: Window = $4 - 1 - 1 = 2$. $\binom{2}{1} = 2$.
• $i = 2$: Window = $4 - 2 - 1 = 1$. $\binom{1}{1} = 1$.
• $i = 3$: Window = $0$. $\binom{0}{1} = 0$.

Сумма: $3 + 2 + 1 + 0 = 6$. Ответ: 6 ✓

Пример 3: n=1, m=1, k=1, массив 1

• $i = 0$: $r = 1$. Window = $0$. $\binom{0}{0} = 1$.

Ответ: 1 ✓

Пример 4: n=10, m=4, k=0, массив 1 3 1 2 2 3 4 4 1 2

После сортировки: 1 1 1 2 2 2 3 3 4 4. $k = 0$ означает, что все элементы набора должны быть равны.

Группы одинаковых: три 1 (индексы 0..2), три 2 (3..5), две 3 (6..7), две 4 (8..9).

• Для каждой 1: правое окно — только индексы с тем же значением 1.
  • $i = 0$: окно длиной 2 (индексы 1, 2). $\binom{2}{3} = 0$.
  • $i = 1$: окно 1. $\binom{1}{3} = 0$.
  • $i = 2$: окно 0. $\binom{0}{3} = 0$.
• Аналогично для 2, 3, 4.

Никакая группа из четырёх одинаковых элементов в массиве не существует → ответ 0. Ответ: 0 ✓

---

Крайние случаи, на которых можно споткнуться

1. $m = 1$

Любой одиночный элемент — допустимый набор. Окно длиной 0, и $\binom{0}{0} = 1$ для каждого $i$. Ответ $= n$. Проверяется на примере 3.

2. $k = 0$ и нет повторов

Ответ 0 при $m \ge 2$. Алгоритм автоматически выдаст 0: $r$ остановится сразу после $i$, окно будет 0.

3. Все элементы равны

Тогда $r = n$ для каждого $i$, окно = $n - i - 1$. Сумма $\binom{n - i - 1}{m - 1}$ по $i = 0, \ldots, n - 1$ по формуле хоккейной клюшки даёт $\binom{n}{m}$ — что и ожидаемо: любой набор из $m$ индексов подходит.

4. $m > n$

Тогда $m - 1 > n - 1 \ge$ окна. $\binom{\text{window}}{m - 1} = 0$ всегда. Ответ 0.

5. Большие $k$, в окне весь массив

Если $k \ge \max a - \min a$, то $r = n$ всегда. Ответ $= \sum_{i = 0}^{n - 1} \binom{n - i - 1}{m - 1} = \binom{n}{m}$.

---

Типичные ошибки

1. Двигают $r$ заново для каждого $i$. Получается $O(n^2)$ вместо $O(n)$. Лекарство — указатель $r$ хранится между итерациями внешнего цикла, монотонность массива гарантирует, что он только растёт.
2. Считают $\binom{r - i}{m}$ вместо $\binom{r - i - 1}{m - 1}$. Путают: «всего элементов в окне $r - i$» против «остальных, кроме фиксированного минимума, $r - i - 1$, и из них выбираем $m - 1$».
3. Забывают по модулю в power. Если $a$ или промежуточное произведение превысят $2^{63}$ в C++ — переполнение. Каждое умножение должно сопровождаться % MOD.
4. Не предвычислили факториалы. Считать $\binom{n}{k}$ через формулу с делениями на каждом шаге — медленно и небезопасно по модулю (деление нужно как умножение на обратное). Таблица факториалов и обратных — линейная.
5. Сортировка стабильная не нужна. В Python sorted стабильная, в C++ sort нет, но это не влияет на результат: мы оперируем значениями, а не парами (значение, исходный индекс).
6. Off-by-one в условии цикла while. a[r] - a[i] <= k — нестрогое неравенство, потому что разница ровно $k$ ещё допустима. Сильное неравенство < уберёт допустимые наборы и даст WA на тестах с граничными $k$.

---

Анализ сложности

• Время: $O((n + \text{MAX\_N}) + n \log n)$ на тест, где предвычисление таблиц — общее для всего входа. На сумму $\sum n \le 2 \cdot 10^5$ — суммарно укладываемся в 3 сек.
• Память: $O(\text{MAX\_N}) = O(2 \cdot 10^5)$ под факториалы + $O(n)$ под массив.

---

Что ещё полезно потренировать

• Codeforces 1029C «Maximal Intersection» (~1500) — two pointers по отсортированным концам отрезков, классическое введение в шаблон.
• Codeforces 279B «Books» (~1400) — окно, в котором сумма не превосходит ограничения. Хороший разогрев на двух указателях.
• Codeforces 1234B2 «Social Network (hard version)» (~1400) — другой способ работы со «скользящим окном» через структуру данных.
• acmp.ru задача 358 «Сумма цифр» — не на two pointers, но классическая отработка предвычислений.

---

Итого

• Идея: сортируем массив, двумя указателями находим для каждого минимума максимальный конец «окна разницы», считаем $\binom{r - i - 1}{m - 1}$.
• Сложность: $O(n \log n)$ на сортировку + $O(n)$ на проход указателями + $O(\text{MAX\_N})$ на предвычисление.
• Ловушки: сброс $r$ между итерациями (потеря $O(n)$ → $O(n^2)$), путаница «$\binom{n}{k}$ vs $\binom{n - 1}{k - 1}$» при фиксации минимума, забытое % MOD в умножениях.