Задача №114886. Кот Гусь и случайная матрица
Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу \(a\) размера \(n \times m\), содержащую числа от \(0\) до \(p-1\).
Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от \(0\) до \(p-1\), независимо от остальных.
Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на \(p\). Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.
Формально, вам необходимо найти такие \(1 \leq i_1 \leq i_2 \leq n\), \(1 \leq j_1 \leq j_2 \leq m\), что сумма \(a_{x, y}\) по всем \(i_1 \leq x \leq i_2, j_1 \leq y \leq j_2\) делится на \(p\), и среди таких имеет максимальную сумму.
В первой строке входного файла расположено три целых числа \(n, m, p\) (\(1 \leq n \cdot m, p \leq 1\,000\,000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих \(n\) строках расположено по \(m\) целых чисел, \(j\)-е число в \(i\)-й строке равно \(a_{i, j}\) (\(0 \leq a_{i, j} \leq p - 1\)).
Гарантируется, что каждое число в \(a\) выбрано независимо случайно равновероятно от \(0\) до \(p-1\).
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на \(p\).
Если таких нет, выведите \(0\).
Эта задача состоит из пяти подзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже.
Подзадача | Количество тестов | Дополнительные ограничения | Необходимые подзадачи |
1 | 5 | \(n \cdot m \leq 3000\) | — |
2 | 5 | \(n, m \leq 300\) | — |
3 | 5 | \(n = 1\) или \(m = 1\) | — |
4 | 5 | \(p \leq 5000\) | — |
5 | 30 | — | 1, 2, 3, 4 |
6 7 5 0 0 3 0 1 0 4 0 2 3 0 2 2 1 2 4 1 4 4 0 3 1 1 0 2 0 3 2 3 0 3 1 0 1 2 1 2 0 0 3 3 1
65