Hệ số nhị thức
Xem PDF
Điểm:
2000 (p)
Thời gian:
0.1s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho hai số nguyên \(n\) và \(k\). Hãy tính \(\displaystyle \binom{n}{k}\).
Input
- Một dòng duy nhất chứa hai số nguyên \(n\) và \(k\).
Output
- Một dòng duy nhất chứa một số nguyên là phần dư của đáp án khi chia cho \(10 ^ 9 + 7\).
Constraints
- \(0 \leq k \leq n \leq 10^{18}\).
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
- Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^3\).
- Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^6\).
- Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^9\).
- Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
5 2Output
10
Bình luận
Sau 1 năm trời cuối cùng cũng giải được :D
Bắt thời gian chặt quá, định lí Lucas + xử lí \(10^9\) mà vẫn TLE T-T (phải ăn gian cái
#pragmamới đc)edit: 6 likes = solution sub cuối ;)
(chuẩn AC)
14 bình luận nữa