- Đầu tiên loại trường hợp không có đáp án.
- Sub1: QHĐ trên lưới là đủ tính rồi.
- Sub2, sub3: Đường đi từ ô (x,y) đến ô (u,v) sẽ phải đi n = (u-x) + (v-y) bước. Vậy số cách đi là chọn ra k (k = u-x) bước đi xuống trong tổng số n bước. Chính là C(k, n) Tổ hợp chập k của n. vấn đề đặt ra là tính tổ hợp này như thế nào.
- Sub2 sẽ tính theo công thức c(k,n) = n!/(k!*(n-k)!) theo nghịch đảo modulo. Chưa biết nghịch đảo modulo thì đọc trên vnoj wiki.
- Sub3 thì do k và n lớn quá nên ta sẽ dùng thêm định lý Lucas. Đọc thêm về định lý Lucas trên VNOJ wiki.
- Tham khảo code: https://ideone.com/jZeTq2
Đúng 0
Bình luận (0)
