Atcoder Educational DP Contest M - Candies
View as PDF
Có ~N~ đứa trẻ được đánh số từ ~1~ tới ~N~.
Bọn trẻ quyết định chia nhau ~K~ viên kẹo. Với mỗi đứa trẻ, đứa thứ ~i (1 \leq i \leq N)~ phải nhận được số viên kẹo trong phạm vi từ ~0~ tới ~a_i~. ~K~ viên kẹo phải được dùng hết.
Hãy đếm số cách bọn trẻ có thể chia nhau những viên kẹo chia lấy dư cho ~10^9 +7~.
Hai cách chia được gọi là khác nhau nếu tồn tại một đứa trẻ nhận số viên kẹo khác nhau giữa hai cách.
Input
Dòng đầu tiên là hai số nguyên ~N(1 \leq N \leq 100)~ và ~K(0 \leq K \leq 10^5)~.
Dòng thứ hai có ~N~ số nguyên ~a_1,a_2,a_3,...,a_n (0 \leq a_i \leq K).~
Output
Số cách chia kẹo cho bọn trẻ chia lấy dư cho ~10^9 + 7~.
Sample 1
Input
3 4
1 2 3
Output
5
Có ~5~ cách để bọn trẻ chia nhau những viên kẹo như sau:
- ~(0,1,3)~
- ~(0,2,2)~
- ~(1,0,3)~
- ~(1,1,2)~
- ~(1,2,1)~
Ở mỗi dòng số thứ ~i~ là số lượng kẹo mà đứa trẻ thứ ~i~ nhận được.
Sample 2
Input
1 10
9
Output
0
Không có cách chia kẹo thỏa mãn.
Sample 3
Input
2 0
0 0
Output
1
Chỉ có ~1~ cách chia thõa mãn như sau:
- ~(0,0)~
Sample 4
Input
4 100000
100000 100000 100000 100000
Output
665683269
Hãy nhớ chia lấy dư kết quả cho ~10^9 + 7~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
code dành cho bạn nào vẫn muốn quy hoạch động 2 chiều