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
Bài này khó thế
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)
SPOILER:
Chúng ta có thể sử dụng phương pháp quy hoạch độngđể giải bài toán này.
Ta sẽ sử dụng một mảng 2 chiều dp[k+1][h+1] để lưu số cách chia kẹo sao cho mỗi người nhận được ít nhất l viên và nhiều nhất h viên. Ban đầu, ta sẽ khởi tạo dp[0][0] = 1, tức là có 1 cách chia khi không có người nào nhận kẹo.
Sau đó, ta sẽ duyệt qua từng người (i từ 1 đến k) và từng số lượng kẹo (j từ 1 đến h). Ở mỗi bước, ta sẽ duyệt qua số lượng kẹo mà người trước đó đã nhận (x từ l đến min(j, n)). Với mỗi cách chia trước đó của (i-1) người và số kẹo j-x, ta sẽ cộng thêm vào dp[i][j] để tính toán số cách chia mới.
Cuối cùng, kết quả sẽ là tổng của dp[k] % (10^9 + 7), với k là số người nhận kẹo.