Düzbucaqlıların sayı#11258

Düzbucaqlıların sayı (Həll təhlili)

Gəlin $a \times b$ a \times b ölçüsündə bir düzbucağını şəbəkədə təsvir edək. Gəlin $a$ dəyərini neçə yolla seçə biləcəyimizə baxaq. Şəbəkədə $n$ sıra kvadrat vardır, buna görə şəbəkədə $n + 1$ n+1 horizontal xətt var. Onları $1$ -dən $n + 1$ n+1-ə qədər nömrələyək. İki xətti $i$ və $j (i < j)$ j~(i < j) seçək. Bu xətlər arasında bir seqment çəkək - bu vertikal tərəf $a$ olacaq. Xətləri $i$ və $j (i < j)$ j~(i < j) seçməyin üsul sayı ${1, 2, ..., n + 1}$ \{1, 2, ..., n+1\} dəstindən $C_{n + 1}^{2}$ C_{n+1}^2-yə bərabərdir. Məsələn, $n = 2$ n = 2 üçün vertikal tərəfi seçməyin $3$ variantı var:

Oxşar, şəbəkədə $m + 1$ m+1 vertikal xətt var. Horizontal tərəfi seçməyin üsul sayı $C_{m + 1}^{2}$ C_{m+1}^2-yə bərabərdir.

Beləliklə, şəbəkədə müxtəlif düzbucaqların sayı

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}

Misal

$2 \times 3$ 2 \times 3 ölçüsündə bir düzbucağ üçün mövcuddur:

$6$ ədəd vahid düzbucaqlı;

$4$ ədəd $1 \cdot 2$ 1 \cdot 2 ölçülü düzbucaqlı;

$2$ ədəd horizontal $1 \cdot 3$ 1 \cdot 3 düzbucaqlı;
$3$ ədəd vertikal $2 \cdot 1$ 2 \cdot 1 düzbucaqlı;

$2$ ədəd $2 \cdot 2$ 2 \cdot 2 düzbucaqlı;
$1$ ədəd $2 \cdot 3$ 2 \cdot 3 düzbucaqlı;

Nəticədə $C_{3}^{2} \cdot C_{4}^{2} = 3 \cdot 6 = 18$ C_3^2 \cdot C_4^2 = 3 \cdot 6 = 18 düzbucaqlı əldə olunur.

Alqoritmin həyata keçirilməsi

Çünki $n, m \leq 1 0^{5}$ n, m \le 10^5 olduğundan, düzbucaqların ümumi sayı $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} qədər ola bilər. Bu nəticə $64$ bit tam ədədini aşır. Ona görə də, həlli Python dilində həyata keçirərik.

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