Поле величезне (m \le 10^9), тому перебирати всі квадрати неможливо. Але чорних клітинок лише n \le 10^5, а k \le 4 — і саме це рятує.
Ключове спостереження: чорна клітинка потрапляє лише в ті квадрати, чий лівий верхній кут задовольняє
Таких кутів щонайбільше k^2 \le 16.
Отже, переберемо всі чорні клітинки і для кожної — усі її \le k^2 можливих квадратів, збільшуючи лічильник у хеш-таблиці, ключем якої є координати кута. Загалом у таблиці буде не більше n k^2 \le 1.6 \cdot 10^6 записів.
Після цього таблиця містить рівно ті квадрати, у яких є хоча б одна чорна клітинка, разом із точною кількістю чорних. Будуємо гістограму: для кожного значення лічильника t \ge 1 рахуємо, скільки квадратів його мають.
Залишається t = 0. Усього квадратів k \times k на полі рівно (m - k + 1)^2, тому
Не забудьте окремий випадок m < k: тоді жодного квадрата не існує і всі відповіді нульові.
Складність — \mathcal{O}(n k^2) у середньому. Величина (m-k+1)^2 сягає 10^{18}, тому обов'язково 64-бітний тип; ключ хеш-таблиці теж зручно пакувати у 64-бітне число як i \cdot (m+1) + j.