Sanjar Bidaibek


Задача №1. 

Задача A. Волшебство на матрицах

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

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую матрицу ее префиксной суммой!
   Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл матрицу очень большого размера, каждый элемент которой равен $1$, и очень много раз применил к ней вышеописанное заклинание.
   В этой задаче вам предстоит показать, что ваши навыки программирования ничем не уступуают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от их деления на 1000000007.
Формат входного файла
Первая строка содержит целое положительное число $Q \; (1 <= Q <= 10^5)$ — количество запросов к вашей программе.
   Каждая из следующих $Q$ строк описывает очередной запрос и содержит три целых положительных числа — номер строки $i$, номер столбца $j$ и количество предварительных применений заклинания $k$ $(1 <= i, j, k <= 10^5)$ соответственно.
Формат выходного файла
Выведите $Q$ целых чисел, по одному в строке — значение в ячейке в $i$-м ряду в $j$-й строке матрицы после $k$ применений заклинания, взятое по модулю 1000000007.
Система оценки
Подзадача 1 (10 баллов) — $1 <= Q <= 10, 1 <= i, j, k <= 100$
Подзадача 2 (10 баллов) — $1 <= i, j, k <= 100$
Подзадача 3 (10 баллов) — $1 <= i, j, k <= 10^3$
Подзадача 4 (10 баллов) — $i = 1$ или $j = 1$
Подзадача 5 (10 баллов) — $k = 1$
Подзадача 6 (50 баллов) — без дополнительных ограничений
Примеры:
Вход 
2
2 3 1
1 1 3
Ответ
6
1
Вход 
3
4 5 7
3 3 3
2 1 10
Ответ
39600
100
11
Замечание

   Напомним, что матрица - это двумерный массив (иначе говоря, таблица) содержащий целочисленные значения. Один из возможных примеров матрицы 3x4 приведен ниже: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline 4 & 7 & 0 & -2\\ \hline 5 & 9 & 2 & 6\\ \hline \end{tabular} \end{center}
   Префиксной суммой называется матрица, где каждый элемент заменен на сумму чисел в соответствующуем ему прямоугольнике с противоположной вершиной в $(1, 1)$. Более формально, определим префиксную сумму матрицы $A$ как матрицу $B$ такую, что для любых $i > 0, \; j > 0$ выполняется \[B_{i, j} = A_{i, j} + B_{i - 1, j} + B_{i, j - 1} - B_{i - 1, j - 1}\]
   В то время как значения в ячейках $B$ с $i = 0$ или $j = 0$ равны нулю.
   Например перфиксной суммой данной матрицы \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline 4 & 1 & 5 & 9\\ \hline 3 & 2 & 6 & 1\\ \hline 0 & 7 & 2 & 4\\ \hline \end{tabular} \end{center}
   Будет следующая матрица: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline 5 & 8 & 13 & 23\\ \hline 8 & 13 & 24 & 35\\ \hline 8 & 20 & 33 & 48\\ \hline \end{tabular} \end{center} ( Sanjar Bidaibek )
комментарий/решение(6) олимпиада
Задача №2. 

Задача A. Кролики

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

У Айбара есть сад, который состоит из $K$ подряд идущих грядок. В саду живут $n$ кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано $q$ запросов, которые надо обработать. Они бывают следующих типов:
Формат входного файла
В первой строке входных данных даны два числа - $n$ и $K$. \\ Далее во второй строке указаны $n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число $q$ и $q$ строк описывающих запросы. Запросы задаются в следующем формате:
Формат выходного файла
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000$ Подзадача 2 (20 баллов) — $1 <= n, K, q <= 5 * 10^5$, отсутствуют запросы сдвига кролика Подзадача 3 (60 баллов) — $1 <= n, K, q <= 5 * 10^5$
Пример:
Вход 
3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7
Ответ
1
3
( Sanjar Bidaibek )
комментарий/решение(12) олимпиада