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
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.
nhìn đề thấy làm theo bài toán chia kẹo euler có lẽ được =)
Ví dụ tham khảo=>https://viblo.asia/p/bai-toan-chia-keo-euler-L4x5xqvqKBM
Mình không nghĩ đây là cách giải bài toán này :)), nếu chạy đủ nhanh thì chỉ được 2 subtask đầu thôi.
Mik chỉ nói chung chung thôi nếu cần chúng ta có thể sử dụng phường pháp khác như sử dụng phương pháp tham lam (greedy algorithm) để tìm ra số cách chia kẹo thỏa mãn yêu cầu.
Một cách tiếp cận tham lam có thể là duyệt qua tất cả các cách chia kẹo có thể, kiểm tra xem cách chia đó có thỏa mãn điều kiện hay không, và đếm số cách chia hợp lệ. Bằng cách này, bạn có thể tìm ra số cách chia kẹo mà không cần phải sử dụng quy hoạch động.
Theo cách này nếu biết code và dùng pypy mik nghĩ có thể AC dc 50% trở lên.
Nói thật bài này dùng PY3 cx khó vì time ít quá mà về sau toàn test khủng à
Mình đã gấp đôi thời gian cho các ngôn ngữ Python và PyPy rồi nhé, bạn có thể thử lại :))
sao invalid dc ta
invalid là do quá kiểu dữ liệu ak, chắc bạn đếm xong cuối mới mod cho 10^9+7 nên bị quá dữ liêu ( chắc đếm lớn hơn 10^18)