Elearning CodePath – CTP Online Judge

Rút thăm trúng thưởng

CARDS

🟢 Hard #Dynamic Programming #Number Theory

### 📌 Thông tin chung
Tên File Input: CARDS.INP
Tên File Output: CARDS.OUT

### 📝 Bài toán
Ban tổ chức chuẩn bị k loại thẻ bài có giá trị từ 1 đến k. Các thẻ này được phân bổ vào q chiếc hộp dựa trên quy tắc chia cho q lấy dư:
- Hộp thứ nhất: Chứa các thẻ có giá trị x sao cho x chia cho q dư 0 (với 1 <= x <= k).
- Hộp thứ hai: Chứa các thẻ có giá trị x sao cho x chia cho q dư 1 (với 1 <= x <= k).
- ...
- Hộp thứ q: Chứa các thẻ có giá trị x sao cho x chia cho q dư q-1 (với 1 <= x <= k).

Người chơi thực hiện n lần rút thẻ. Thứ tự rút thẻ bắt đầu từ hộp thứ nhất, sau đó đến hộp thứ hai, cứ thế cho đến hộp thứ q rồi lặp lại vòng tuần hoàn (1 -> 2 -> ... -> q -> 1 -> ...).

Yêu cầu: Tính số cách rút n thẻ sao cho tổng giá trị của n thẻ đó chia hết cho m. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho 123456789.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file CARDS.INP gồm một dòng duy nhất chứa bốn số nguyên dương n, k, m, q.

### 📤 Định dạng Đầu ra
Ghi ra file CARDS.OUT một số nguyên duy nhất là kết quả bài toán sau khi lấy modulo 123456789.

### ✨ Ví dụ
Input:
3 4 7 2

Output:
4

Giải thích:
n=3, k=4, m=7, q=2.
- Hộp 1 (dư 0 khi chia 2): {2, 4}
- Hộp 2 (dư 1 khi chia 2): {1, 3}
Thứ tự rút: Hộp 1 -> Hộp 2 -> Hộp 1.
Các bộ (tổng chia hết cho 7): (2, 3, 2), (2, 1, 4), (4, 1, 2). Lưu ý: Ví dụ trong đề bài của bạn ghi 3 cách nhưng thực tế bộ (4, 1, 2) và (2, 1, 4) là khác nhau về vị trí rút, bài toán đếm số cách chọn thẻ theo thứ tự.

### 🏷 Subtasks
Subtask 1 (20%): q = 1.
Subtask 2 (20%): q = 2.
Subtask 3 (20%): n, k <= 1000.
Subtask 4 (20%): n <= 1000.
Subtask 5 (20%): Không có điều kiện gì thêm.

✅ Đã AC: 0 / 3 submissions