گربه غاز و ماتریس تصادفی
Problem
گربه غاز برای نیک فیوری یک میز مستطیل شکل a به اندازه \(n \cdot m\) آماده کرد که حاوی اعداد از 0< /span> code> به p−1. نیک فیوری بلافاصله متوجه شد که هر عدد در این جدول به طور تصادفی با احتمال مساوی از 0 تا p− 1، صرف نظر از موارد دیگر.
وظیفه شما — زیر ماتریس مستطیلی این جدول را پیدا کنید که در آن مجموع آن بر p بخش پذیر است. >
به طور رسمی، باید \(1 <= i_1 <= i_2 <= n\)، \( 1 <= j_1 <= j_2 <= m\) که مجموع ax,y در همه \(i_1 <= x <= i_2\)، \(j_1 <= y <= j_2\) بر روی p تقسیم می‌شود، و در این میان حداکثر مقدار را دارد.
ورودی
خط اول شامل سه عدد صحیح n، m، p (\(1 < ;= n m، p <= 1,000,000\)) — ابعاد ماتریس و عددی که مجموع زیرماتریس باید بر آن تقسیم شود.
خطوط n زیر حاوی اعداد صحیح m، عدد j-امین در خط i-امین هستند. برابر است با 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 |