猫鹅和随机矩阵
Problem
<分区>
Cat Goose 为 Nick Fury 准备了一张长方形桌子 a，大小为 \(n \cdot m\)，其中包含来自 0< 的数字/span> code> 到 p−1。 Nick Fury 立即意识到这张表中的每个数字都是以相同的概率从 0 到 p− 中随机选择的。 1，不管其他的。
你的任务 —找到这个表的一个矩形子矩阵，其中的和可以被 p 整除。 在所有这样的子矩阵中，你需要找到一个元素和最大的子矩阵。
形式上，你需要找到
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) ax,y 的总和 over all
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\)在
p 上拆分，其中数量最大。
输入
第一行包含三个整数n, m, p (\(1 < ;= n m, p <= 1,000,000\)) —矩阵的维数以及子矩阵之和应除以的数。
后面的n行包含m个整数，即第i行中的第j个数等于 ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
保证a中的每个数字都是随机独立选择的，从0到p−1的概率均等。
输出
打印单个整数 —矩形子矩阵的最大总和，其中总和可被 p 整除。如果没有，打印0。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
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 |