Processing math: 26%

Областная олимпиада по информатике 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
5 года 9 месяца назад #

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

C++

  0
5 года 3 месяца назад #

Докажите пожалуйста это решения

  0
5 года 3 месяца назад #

докажите решение

  0
5 года назад #

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

C++