DHBB 2024 - CBH - 11 - Những viên bi
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Trên hệ trục tọa độ ~Oxy~, Bờm lần lượt đặt ~N~ viên bi, viên bi thứ ~i~ có tọa độ ~(0, i)~. Ở mỗi lượt chơi sau đây, Bờm có ba lựa chọn:
Không làm gì cả.
Chọn một viên bi, di chuyển lên trên ~1~ đơn vị, nếu viên bi ở vị trí ~(i, j)~, ta có thể đưa viên bi về vị trí ~(i + 1, j)~.
Chọn một viên bi, di chuyển xuống dưới ~1~ đơn vị, nếu viên bi ở vị trí ~(i, j)~, ta có thể đưa viên bi về vị trí ~(i - 1, j)~.
Sau ~K~ lượt chơi, ~N~ viên bi lần lượt kết thúc ở các tọa độ ~(x_1, 1), (x_2, 2), (x_3, 3), \dots, (x_N, N)~.
Yêu cầu: Đếm số cách đi khác nhau của Bờm modulo ~10^9 + 7~ để từ trạng thái ban đầu, sau ~K~ lượt đi, các viên bi ở trạng thái đích. Hai cách chơi được gọi là khác nhau nếu như tồn tại một lượt chơi mà thao tác ở cách chơi này khác thao tác ở cách chơi kia.
Input
Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 100, 1 \le K \le 1000)~, lần lượt là số lượng viên bi và số lượt mà Bờm đã chơi.
Dòng tiếp theo gồm ~N~ số nguyên ~x_i~ ~(-1000 \le x_i \le 1000)~, số nguyên thứ ~i~ biểu diễn viên bi thứ ~i~ kết thúc ở tọa độ ~(x_i, i)~.
Output
In ra một số nguyên duy nhất là số cách di chuyển những viên bi MOD ~10^9 + 7~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~25\%~ | ~\sum_{i=1}^{N} \lvert x_i \rvert = K~ |
| 2 | ~25\%~ | ~N = 1~ |
| 3 | ~50\%~ | Không có giới hạn gì thêm |
Sample Input 1
2 2
1 -1
Sample Output 1
2
Sample Input 2
5 20
1 2 3 4 5
Sample Output 2
182783854
Notes
Ở ví dụ 1: chúng ta có thể di chuyển viên bi ~1~ lên trên trên trước và di chuyển viên bi ~2~ xuống dưới sau, hoặc là di chuyển viên bi ~2~ xuống dưới trước và di chuyển viên bi ~1~ lên trên sau. Vì thế có hai cách để di chuyển viên bi về đúng vị trí.
Bình luận