Областная олимпиада по информатике 2019 год, 9 класс


Задача A. Волшебство на последовательностях

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую последовательность ее префиксной суммой!
   Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл последовательность очень большого размера, каждый элемент которой равен $1$, и очень много раз применил к ней вышеописанное заклинание.
   В этой задаче, вам предстоит показать, что ваши навыки программирования ничем не уступают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в $i$-м ряду после $k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от деления этих чисел на 1000000007.
Формат входного файла
Первая строка ввода содержит целое число $Q$ — количество запросов к вашей программе.
   Каждая из следующих $Q$ строк описывает очередной запрос и содержит два целых положительных числа — номер столбца и количество предварительных применений заклинания соответственно.
Формат выходного файла
Выведите $Q$ целых чисел, по одному в строке — значение в ячейке в $i$-м ряду после $k$ применений заклинания по модулю 1000000007.
Система оценки

Подзадача 1 (10 баллов) — $1 <= Q <= 10^5, 1 <= i, k <= 5$
Подзадача 2 (10 баллов) — $1 <= Q <= 10^5, 1 <= i <= 10^5, k=1$
Подзадача 3 (20 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 100$
Подзадача 4 (20 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 10^3$
Подзадача 5 (40 баллов) — $1 <= Q <= 10^5, 1 <= i,k <= 10^5$
Пример:
Вход
2
2 1
1 3
Ответ
2
1
Замечание

   Напомним, что последовательность - это одномерный массив содержащий целочисленные значения. Один из возможных примеров последовательности размерностью 4 приведен ниже:
1234

   Префиксной суммой называется последовательность, где каждый элемент заменен на сумму чисел в соответствующем ему подпоследовательности, с противоположной вершиной в ячейке $(1, 1)$. Формально, определим префиксную сумму последовательности $A$ как последовательность $B$ такую, что для любых $i > 0$ выполняется \[B_i = A_i + B_{i - 1}\]
   В то время как значения в ячейках $B$ с $i = 0$ равны нулю.
   Например префиксной суммой данной последовательности
1201

   Будет следующая последовательность:
1334
( Aisultan Kali )
посмотреть в олимпиаде

Комментарий/решение:

  0
2019-07-09 12:22:30.0 #

показать/скрыть код