Tutorial — Số Lượng Dãy Đẹp

Một Dãy Ngoặc Cấu Trúc luôn bao gồm một số lượng ngoặc mở bằng với số lượng ngoặc đóng. Thay vì đếm độ dài của từng chuỗi con một cách trực tiếp, bạn hãy thử cố định một ký tự đặc biệt làm mốc để chia chuỗi con ra làm hai phần độc lập.

Gọi vị trí của dấu ngoặc mở cuối cùng được chọn trong chuỗi con là vị trí chốt. Nếu có $l$ dấu ngoặc mở tính đến vị trí này và $r$ dấu ngoặc đóng ở bên phải nó, bạn cần chọn $k-1$ dấu ngoặc mở từ $l-1$ vị trí trước đó và $k$ dấu ngoặc đóng từ $r$ vị trí phía sau.

Tổng số cách chọn cho mọi giá trị độ dài $k$ là $\sum \binom{l-1}{k-1} \binom{r}{k}$ và biểu thức này có thể tính nhanh bằng đẳng thức Vandermonde. Đẳng thức này cho phép rút gọn toàn bộ vòng lặp đếm thành công thức duy nhất $\binom{l+r-1}{r-1}$, giúp bạn tính được kết quả kết hợp cùng mảng giai thừa nghịch đảo.