Đụng hàng bản lật
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
rủ và chơi một trò hơi “khó chịu”: chọn đúng k số có 2 chữ số sao cho không bị “đụng hàng bản lật” (tức là chọn 12 thì cấm 21, còn mấy số kiểu 33 thì tự loại vì lật lại vẫn là nó), đồng thời tổng các số phải đúng bằng S; nghe thì đơn giản nhưng ba người ngồi tính mãi không ra nên quyết định giao lại cho bạn 😅
Yêu cầu: Cho hai số nguyên dương \(k\) và \(S\). Hãy đếm số lượng tập hợp \(A\) thỏa mãn các điều kiện trên, vì số lượng tập hợp có thể sẽ quá lớn nên ta sẽ lấy kết quả \(mod\) \(10^9 + 7\).
Input
- Một dòng duy nhất chứa hai số nguyên \(k\) và \(S\) (\(1 \le k \le 40, 10 \le S \le 3500\)).
Output
- Một số nguyên duy nhất là số lượng tập hợp thỏa mãn.
Example
Test 1
Input
2 35Output
6Note
Các cặp \(\{a_1, a_2\}\) có tổng bằng 35, là số có 2 chữ số và không chứa số đảo ngược của nhau:
- \(\{10, 25\}\) (số đảo ngược là 01 và 52, không nằm trong tập) -> Thỏa mãn.
- \(\{12, 23\}\) (số đảo ngược là 21 và 32, không nằm trong tập) -> Thỏa mãn.
- \(\{15, 20\}\) (số đảo ngược là 51 và 02, không nằm trong tập) -> Thỏa mãn.
- \(\{17, 18\}\) (số đảo ngược là 71 và 81, không nằm trong tập) -> Thỏa mãn.
- \(\{16, 19\}\) (số đảo ngược là 61 và 91, không nằm trong tập) -> Thỏa mãn.
- \(\{14, 21\}\) (số đảo ngược là 41 và 21, không nằm trong tập) -> Thỏa mãn.
Scoring
- Subtask 1 (\(50\%\) điểm): \(k \le 4, S \le 350\).
- Subtask 2 (\(50\%\) điểm): \(k \le 40, S \le 3500\).
Kỳ thi:
- 🏔️Twin Peaks Contest #01 (18 Tháng tư, 2026)
Bình luận (1)