Кількість прямокутників#11258

Кількість прямокутників (Розбір)

Розглянемо розмір прямокутника $a \times b$ a \times b, зображеного на сітці. Розглянемо, скількома способами можна вибрати значення $a$ . Сітка містить $n$ рядків квадратів, отже в сітці є $n + 1$ n + 1 горизонтальна лінія. Пронумеруємо їх числами від $1$ до $n + 1$ n + 1. Виберемо дві лінії $i$ і $j (i < j)$ j~(i < j). Проведемо між ними відрізок — це і буде вертикальна сторона прямокутника $a$ . Кількість способів вибрати два числа $i$ і $j (i < j)$ j~(i < j) з множини ${1, 2, ..., n + 1}$ \{1, 2, ..., n + 1\} рівна $C_{n + 1}^{2}$ C_{n+1}^2. Наприклад, для $n = 2$ n = 2 є $3$ варіанти вибрати вертикальну сторону прямокутника:

Аналогічно, в сітці є $m + 1$ m + 1 вертикальна лінія. Кількість способів вибрати горизонтальну сторону прямокутника рівна $C_{m + 1}^{2}$ C_{m+1}^2.

Отже, кількість різних прямокутників на сітці рівна

C_{n + 1}^{2} \cdot C_{m + 1}^{2} = \frac{( n + 1 ) \cdot n}{2} \cdot \frac{( m + 1 ) \cdot m}{2}

C_{n+1}^2 \cdot C_{m+1}^2 = {(n + 1) \cdot n \over 2} \cdot {(m + 1) \cdot m \over 2}

Приклад

Для прямокутника $2 \times 3$ 2 \times 3 є:

$6$ одиничних прямокутників;

$4$ прямокутника розміром $1 \cdot 2$ 1 \cdot 2;

$2$ горизонтальних прямокутника $1 \cdot 3$ 1 \cdot 3;
$3$ вертикальних прямокутника $2 \cdot 1$ 2 \cdot 1;

$2$ прямокутника $2 \cdot 2$ 2 \cdot 2;
$1$ прямокутник $2 \cdot 3$ 2 \cdot 3;

Загалом отримали $C_{3}^{2} \cdot C_{4}^{2} = 3 \cdot 6 = 18$ C_3^2 \cdot C_4^2 = 3 \cdot 6 = 18 прямокутників.

Реалізація алгоритму

Оскільки $n, m \leq 1 0^{5}$ n, m \le 10^5, то кількість прямокутників може досягати $C_{n + 1}^{2} \cdot C_{m + 1}^{2} \leq (1 0^{5})^{2} \cdot (1 0^{5})^{2} = 1 0^{20}$ C_{n+1}^2 \cdot C_{m+1}^2 \le (10^5)^2 \cdot (10^5)^2 = 10^{20}. Цей результат виходить за межі $64$ бітового цілого числа. Тому реалізуємо рішення на мові Пітон.

n, m = map(int, input().split())
a = (n + 1) * n // 2
b = (m + 1) * m // 2
res = a * b
print(res)