Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

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

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

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

   Префиксной суммой называется последовательность, где каждый элемент заменен на сумму чисел в соответствующем ему подпоследовательности, с противоположной вершиной в ячейке (1,1). Формально, определим префиксную сумму последовательности A как последовательность B такую, что для любых i>0 выполняется Bi=Ai+Bi1
   В то время как значения в ячейках B с i=0 равны нулю.
   Например префиксной суммой данной последовательности
1201

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

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

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

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

C++

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

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

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

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

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

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

C++