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

Вход

Ответ

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$ запросов, которые надо обработать. Они бывают следующих типов:

Кролик номер $x\; (1 <= x <= n)$ перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
Посчитать количество кроликов на отрезке от грядки $l$ до грядки $r$ $(1 <= l <= r <= K)$ включительно.

Формат входного файла

В первой строке входных данных даны два числа -

$n$ и

$K$ . \\ Далее во второй строке указаны

$n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число

$q$ и

$q$ строк описывающих запросы. Запросы задаются в следующем формате:

$\texttt{L } x$ - сдвинуть кролика номер $x$ на одну грядку налево
$\texttt{R } x$ - сдвинуть кролика номер $x$ на одну грядку направо
$\texttt{G } l\; r$ - Посчитать и вывести количество кроликов на отрезке от грядки $l$ до грядки $r$ включительно.

Формат выходного файла

В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.

Система оценки

Подзадача 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$

Пример:

Вход

Ответ

1
3

( Sanjar Bidaibek )
комментарий/решение(12) олимпиада