Chia kẹo 2
Xem PDF
Điểm:
2100 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho bốn số nguyên \(n\), \(k\), \(l\) và \(h\).
Yêu cầu: Bạn hãy tính số cách chia \(n\) viên kẹo giống nhau cho \(k\) người khác nhau sao cho mỗi người nhận được ít nhất \(l\) viên kẹo và nhiều nhất \(h\) viên kẹo.
Hai cách được xem là khác nhau khi một người bất kỳ có số kẹo trong cách này khác với trong cách kia.
Input
- Chứa số bốn số nguyên \(n\), \(k\), \(l\) và \(h\) \((1 \le n, k \le 10^7, 0 \leq l \leq h \leq n)\).
Output
- Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).
Scoring
- Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10\).
- Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^3\).
- Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^6\).
- Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
6 2 2 6Output
3
Bình luận
MOD = 10**9 + 7
n, k, l, h = map(int,input().split())
n -= k * l
if n < 0:
print(0)
else:
m = h - l
o = lambda a, p: pow(a, p - 2, p)
def comb(n, k, p):
if k > n or k < 0:
return 0
num = den = 1
for i in range(k):
num = num * (n - i) % p
den = den * (i + 1) % p
return num * o(den, p) % p
result = 0
sign = 1
for i in range(k + 1):
if n - i * (m + 1) + k - 1 >= 0:
term = (comb(k, i, MOD) * comb(n - i * (m + 1) + k - 1, k - 1, MOD)) % MOD
result = (result + sign * term) % MOD
sign = -sign
print(result)
2 bình luận nữa