ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


XOR на прямоугольнике (усложнённая версия)

Задачи раздела

• C++ и Java
• Captcha
• Hello World
• Radar Defence
• World of Warlcraft
• World of Warlcraft
• World of Warlcraft
• XOR на прямоугольнике
• XOR на прямоугольнике (усло...
• You're in the army now
• Автоформатирование
• Анаграмма
• Анаграмма
• Асимптотика
• Асимптотика
• Атбаш
• Багетная мастерская

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

В этой задаче вам понадобится генератор случайных чисел, порождающий случайное число в диапазоне от 1 до X. Воспользуйтесь реализацией, приведённой ниже.

C/C++Pascal
int getRandom(int b, int c, int x) { static int r; r = (b * r + c) & 0xffff; return 1 + r % x; } function getRandom(b, c, x : longint) : longint; var r : longint; begin r := (b * r + c) and $FFFF; getRandom := 1 + r mod x; end;

Дана числовая матрица A размера N × M. Строки матрицы нумеруются от 1 до N сверху вниз, столбцы — от 1 до M слева направо.

Требуется обработать Q запросов. Каждый запрос содержит 4 числа Y1, Y2, X1, X2, обозначающие границы некоторой подматрицы A. Ответом на запрос является результат применения операции XOR (исключающее ИЛИ) ко всем элементам указанной подматрицы.

Входные данные

Первая строка содержит целые числа N, M и Q (1 <= N, M <= 1000, 1 <= Q <= 10^8) — размеры матрицы и количество запросов соответственно.

Вторая строка содержит целые числа B и C (0 <= B, C < 2^31) — параметры генератора случайных чисел.

Чтобы получить элементы матрицы A, используйте следующий фрагмент кода:

C/C++Pascal
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = getRandom(b, c, 1000); for i := 1 to n do for j := 1 to m do a[i][j] := getRandom(b, c, 1000);

Чтобы получить параметры запроса, используйте следующий фрагмент кода:

C/C++Pascal
for (int i = 0; i < q; i++) { y1 = getRandom(b, c, n); y2 = getRandom(b, c, n); x1 = getRandom(b, c, m); x2 = getRandom(b, c, m); // ... } for i := 1 to q do begin y1 := getRandom(b, c, n); y2 := getRandom(b, c, n); x1 := getRandom(b, c, m); x2 := getRandom(b, c, m); { ... } end;
Выходные данные

Выведите единственное целое число — результат применения операции XOR к ответам на все Q запросов.

Примеры
Входные данныеВыходные данные
2 2 1
5 23
20
5 5 3
31 47
392
Примечание

В первом примере порождается матрица с элементами A11 = 24, A12 = 139, A21 = 714, A22 = 589 и запрос с параметрами Y1 = 2, Y2 = 1, X1 = 2, X2 = 1.

 

Для отправки решений необходимо выполнить вход.

www.contester.ru