Задача №113460. Преобразование таблицы
Ваня занимается работой с большими данными. Его проект занимается обработкой гигантских таблиц статистических данных. Ваня отвечает за разработку модуля преобразования таблиц, который выполняет перестановку строк, столбцов и ячеек таблицы.
Модуль занимается обработкой таблицы, состоящей из \(h\) строк и \(w\) столбцов, строки пронумерованы сверху вниз от \(0\) до \(h−1\), столбцы пронумерованы слева направо от \(0\) до \(w −1\). Ячейка в \(i\)-й строке, \(j\)-м столбце таблицы обозначается как \([i, j]\). Исходно ячейка \([i, j]\) содержит число \(i \times w + j\). На рис. 1. приведен пример исходного заполнения таблицы для \(h = 3,\ w = 5\).
Помогите Ване выполнить все операции и вычислить контрольную сумму таблицы, которая получится в итоге.
Поскольку входные данные для этой задачи слишком велики, чтобы задавать их непосредственно, для ввода вам потребуется процедура расширения массива. Эта процедура не имеет специфических особенностей, которые надо использовать в решении задачи, предполагаемое жюри решение этой задачи в явном виде генерирует все массивы и далее работает с ними так же, как если бы оно считало их из входных данных.
Опишем процедуру генерации массива длины \(n\) по массиву длины \(2 \le k \le n\). Пусть задан массив целых неотрицательных чисел \(A\) = (\(a[1]\), \(a[2]\), \(\dots\), \(a[k]\)).
Массив целых чисел \(Ax \ = \ (ax[1], \ ax[2], \dots, \ ax[n])\) будем называть расширением массива \(A\) по модулю \(r\) до размера \(n\), если его элементы вычисляются по следующим формулам.
- Если \(1 \le i \le k\), то \(ax[i] \ = \ a[i]\).
- Если \(k + 1 \le i \le n\), то \(ax[i] \ = \ (10007 \times ax[i − 2] + 10009 \times ax[i − 1] + 87277) \ mod \ r\).
Например, выполним расширение массива \(A\) = (1, 4, 3) до 5 элементов по модулю 13
\(ax[1] \ = \ a[1] \ = \ 1\).
\(ax[2] \ = \ a[2] \ = \ 4.\)
\(ax[3] \ = \ a[3] \ = \ 3.\)
\(ax[4] \ = \ (10007 \times ax[2] + 10009 \times ax[3] + 87277) \ mod \ 13 = 157332 \ mod \ 13 = 6.\)
\(ax[5] \ = \ (10007 \times ax[3] + 10009 \times ax[4] + 87277) \ mod \ 13 = 177352 \ mod \ 13 = 6.\)
Таким образом, \(Ax \ = \ (1, 4, 3, 6, 6)\).
Первая строка ввода содержит числа \(h\), \(w\), \(n\) — размеры таблицы и число преобразований, которые необходимо выполнить (\(1 \le h, w \le 5 000,\) \(2 \le n \le 10^6\) ).
Вторая строка содержит строку \(s\) длины \(n\) — последовательность типов преобразований, \(s[i]\) = «c» задает операцию обмена столбцов, \(s[i]\) = «r» — операцию обмена строк, \(s[i]\) = «f» — операцию обмена ячеек.
Следующие четыре строки задают массивы \(A\), \(B\), \(C\), \(D\), соответственно. Каждый массив задается числом \(k, 2 \le k \le n, k \le 1000\), после чего следует \(k\) чисел — элементы массива. Элементы массивов \(A\) и \(C\) удовлетворяют ограничению \(0 \le a[i], c[i] \le h − 1\), элементы массивов \(B\) и \(D\) удовлетворяют ограничению \(0 \le b[i], d[i] \le w − 1\).
Пусть \(Ax\) является расширением массива \(A\) по модулю \(h\) до размера \(n\), массив \(Bx\) является расширением массива \(B\) по модулю \(w\) до размера \(n\), массив \(Cx\) является расширением массива \(C\) по модулю \(h\) до размера \(n\) и массив \(Dx\) является расширением массива \(D\) по модулю \(w\) до размера n.
Операции, которые требуется выполнить с таблицей, определяются следующим образом: тип \(i\)-й операции задается символом \(s[i]\), а параметры получаются из массивов \(Ax\), \(Bx\), \(C\)x, \(Dx\).
- Если \(s[i]\) = «c», то \(i\)-я операция «c Bx[i] Dx[i]»;
- Если \(s[i]\) = «r», то \(i\)-я операция «r Ax[i] Cx[i]»;
- Если \(s[i]\) = «f», то \(i\)-я операция «f Ax[i] Bx[i] Cx[i] Dx[i]»;
Выведите одно число — контрольную сумму таблицы после выполнения всех преобразований.
3 5 3 crf 3 0 0 0 3 0 0 1 3 0 1 1 3 1 0 2
564830737