Сортування бульбашкою#1094

Сортування бульбашкою

1 секунда

64 мегабайти

Середня

Сортування бульбашкою (bubble sort) — простий алгоритм сортування. Для розуміння і реалізації цей алгоритм є одним із найпростіших, але ефективний лише для невеликих масивів. Зазвичай використовується з навчальною метою і рідко застосовується поза навчанням; на практиці частіше використовують сортування вставками. Алгоритм полягає у неодноразовому проходженні масиву. Під час кожного проходу відбувається попарне порівняння сусідніх елементів і, якщо їхній порядок помилковий, відбувається обмін. Проходи повторюються, поки не буде жодного обміну — це означає, що масив відсортовано. У процесі сортування елементи, які стоять не на своєму місці, «спливають» нагору, звідки й походить назва.

Вікіпедія

Бульбашкове сортування — дуже простий алгоритм із часом виконання $O (n^{2})$ O(n^2). Кожного разу проходимо масив спочатку, порівнюємо сусідні елементи й, якщо треба, міняємо їх місцями. Процес повторюємо, поки під час обходу немає жодної заміни. Припустимо, після $T$ проходів масив уже відсортовано у зростаючому порядку. Кажемо, що $T$ — це кількість проходів бульбашкового сортування цього масиву. Нижче подано приклад. Початковий масив: $51428$ . Відсортуємо його цим алгоритмом так:

Перший прохід:

$(51428) \to (15428)$ (5\ 1\ 4\ 2\ 8) \to (1\ 5\ 4\ 2\ 8), порівняли перші два елементи і поміняли їх місцями. $(15428) \to (14528)$ (1\ 5\ 4\ 2\ 8) \to (1\ 4\ 5\ 2\ 8), обмін, бо $5 > 4$ 5 > 4. $(14528) \to (14258)$ (1\ 4\ 5\ 2\ 8) \to (1\ 4\ 2\ 5\ 8), обмін, бо $5 > 2$ 5 > 2. $(14258) \to (14258)$ (1\ 4\ 2\ 5\ 8) \to (1\ 4\ 2\ 5\ 8), останні два елементи вже впорядковані ( $8 > 5$ 8 > 5), обміну немає.

Другий прохід:

$(14258) \to (14258)$ (1\ 4\ 2\ 5\ 8) \to (1\ 4\ 2\ 5\ 8). $(14258) \to (12458)$ (1\ 4\ 2\ 5\ 8) \to (1\ 2\ 4\ 5\ 8), обмін, бо $4 > 2$ 4 > 2. $(12458) \to (12458)$ (1\ 2\ 4\ 5\ 8) \to (1\ 2\ 4\ 5\ 8). $(12458) \to (12458)$ (1\ 2\ 4\ 5\ 8) \to (1\ 2\ 4\ 5\ 8).

Після $T = 2$ T = 2 проходів масив уже відсортовано, тому кількість проходів для цього масиву — $2$ .

Дано відсортований масив $A$ , що містить $N$ різних цілих чисел. Стверджується, що його отримано рівно після $K$ проходів бульбашкового сортування. Завдання: скільки існує початкових масивів $A$ , з яких рівно через $K$ проходів бульбашкового сортування отримаємо заданий масив? Відповідь може бути дуже великою, тож виведіть її за модулем $20100713$ .

Вхідні дані

Вхід складається з кількох тестів.

Перший рядок містить натуральне число $T$ ( $T \leq 100000$ T \leq 100\ 000) — кількість тестів.

Далі йдуть $T$ рядків, у кожному рядку два цілі числа $N$ і $K$ ( $1 \leq N \leq 1000000$ 1 \leq N \leq 1\ 000\ 000, $0 \leq K \leq N - 1$ 0 \leq K \leq N - 1), де $N$ — розмір масиву, $K$ — кількість проходів.

Вихідні дані

Для кожного тесту виведіть відповідь за модулем $20100713$ у окремому рядку.

Приклади

Приклад 1

Примітка

Нехай задано масив ${a, b, c}$ \{a, b, c\} ( $a < b < c$ a < b < c). Можливі $6$ початкових перестановок:

${a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}$ \{a, b, c\},\ \{a, c, b\},\ \{b, a, c\},\ \{b, c, a\},\ \{c, a, b\},\ \{c, b, a\},

та отримати відсортований масив можна так:

${a, b, c}$ \{a, b, c\}: уже відсортовано, нічого не робимо.

${a, c, b}, {b, a, c}, {c, a, b}$ \{a, c, b\},\ \{b, a, c\},\ \{c, a, b\}: після $1$ проходу бульбашкового сортування.

${b, c, a}, {c, b, a}$ \{b, c, a\},\ \{c, b, a\}: після $2$ проходів.