Задача №115434. Обмен и удаление
Есть классический способ удаления элемента из массива: поменять местами значения удаляемого элемента и последнего элемента массива, после чего удалить последний элемент. К сожалению, оказалось, что такой способ не всегда сохраняет порядок элементов массива. Ваша задача — посчитать количество последовательностей из \(k\) удалений, после которых изначально упорядоченный по возрастанию массив останется упорядоченным.
Дан массив \(a\) длины \(n\), исходно заполненный числами от \(1\) до \(n\) по возрастанию, то есть \(a_i=i\), а также массив \(b\) длины \(k\), элементы которого — попарно различные числа от \(1\) до \(n\).
Выполняется \(k\) шагов, на \(j\)-м шаге происходит следующее: выбирается такое \(i\) от \(1\) до \(n-j+1\), что \(a_i=b_j\), после чего \(a_i\) и \(a_{n-j+1}\) обмениваются местами (если \(i=n-j+1\), то ничего не происходит). Затем последний на данном шаге элемент массива — он имеет номер \(n - j + 1\) — удаляется из массива.
Массив \([b_1,b_2,\ldots,b_k]\) будем называть хорошим , если после выполнения \(k\) шагов массив \([a_1,a_2,\ldots,a_{n-k}]\) является строго возрастающим.
Вам даны числа \(n\) и \(k\), посчитайте количество хороших массивов \([b_1,b_2,\ldots,b_k]\). Ответ может оказаться слишком большим, поэтому выведите остаток от деления ответа на \(10^9+7\).
В первой строке задано целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. В следующих \(t\) строках заданы наборы входных данных.
В первой строке набора входных данных заданы целые числа \(n\) и \(k\) (\(1 \le n \le 5\cdot 10^5\), \(0 \le k \le n\)).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(5\cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — количество хороших массивов \(b\), взятое по модулю \(10^9+7\).
Разберем четвертый тест из примера. В нем \(n=3\) и \(k=1\). Изначально \(a=[1,2,3]\). Посмотрим, как изменится \(a\) после первого шага для всех возможных массивов \(b\).
- \(b=[1]\). Тогда \(a\) меняется следующим образом: \([1, 2, 3]\to[3,2,1]\to[3,2]\). Массив \([3,2]\) не является возрастающим.
- \(b=[2]\). Тогда \(a\) меняется следующим образом: \([1, 2, 3]\to[1,3,2]\to[1,3]\). Массив \([1,3]\) является возрастающим.
- \(b=[3]\). Тогда \(a\) меняется следующим образом: \([1, 2, 3]\to[1,2,3]\to[1,2]\). Массив \([1,2]\) является возрастающим.
Получаем, что существует два хороших массива \(b=[2]\) и \(b=[3]\), поэтому ответ на четвертый тест из примера равен \(2\).
5 1 0 1 1 2 2 3 1 4 2
1 1 2 2 7