# Hue ICTC 23 Warm-up
## C. Nén dãy
#### Cày trâu

### Full
Tính theo lượng đóng góp của mỗi số lúc đầu vào tổng cuối cùng.
Ví dụ với số $2$, ta sẽ xem thử nó đã đóng góp bao nhiêu lần để tạo nên số ở hàng $i$, cột $j$?
Đây là bài toán QHĐ, số lần đóng góp của mỗi ô bằng hai ô ở trên nó. $F(i,j) = F(i-1,j) + F(i-1,j+1)$. Đây cũng chính là công thức tổ hợp chọn $j$ phần tử trong $i$ số, công thức đếm số đường đi.
Ta có đáp án $A=\sum_{i=0}^{n-1}\binom{n-1}{i} \times (i+1)$
#### Minh họa công thức
Theo test ví dụ, ta có $20 = A = 1\cdot 1 + 3\cdot 2 + 3\cdot 3 + 1\cdot 4$
Các dòng của tam giác Pascal là:
$1 \\ 1 \enspace 1 \\ 1 \enspace 2 \enspace 1 \\ 1 \enspace 3 \enspace 3 \enspace 1 \\ 1 \enspace 4 \enspace 6 \enspace 4 \enspace 1$

### Chứng minh
Xét kết quả $A_1$ của $a_1 = \{1,2,3,..,n\}$ và $A_2$ của $a_2 = \{n,n-1,..,2,1\}$ sau biến đổi.
Ta thấy $A_1 = A_2$, do tính đối xứng của tổ hợp: $\binom{n}{i} = \binom{n}{n-i}$
Xét dãy $b = a_1 + a_2 = \{n+1,n+1,..,n+1\}$.
Sau biến đổi, dễ thấy kết quả của nó $B = (n+1) \times C$, với $C$ là kết quả của dãy $\{1,1,..,1\} (n\enspace \text{số})$ sau biến đổi.
Hay: $C = \sum_{i=0}^{n-1}\binom{n-1}{i} = 2^{n-1}$
Ngoài ra, còn có $B = A_1 + A_2$
Vậy $A_1 = \frac{B}{2} = (n+1)2^{n-2}$

### Code Python