DPDIVI - Chia nhóm
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Lớp ~10~ Tin có ~N~ học sinh, trong giờ thể dục, thầy giáo yêu câu chia thành ~K~ nhóm, mỗi nhóm có tối thiểu một bạn, rất nhanh chóng bạn lớp trưởng đã cho lớp chia thành ~K~ nhóm theo yêu cầu của thầy. Nhưng Tí lại nẩy sinh một câu hỏi: Có bao nhiêu cách chia thỏa yêu cầu của thầy Thể dục? (Các hoán vị của các nhóm được xem là ~1~ cách)
Input
- Dòng đầu chứa số nguyên ~T~ là số bộ test;
- ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dược ~N~ và ~K~
Giới hạn:
- ~1 ≤ K ≤ N ≤ 25~
Output
- Ứng với mỗi test, ghi ra trên một dòng đáp số tương ứng.
Sample
Input #1
2
4 2
3 3
Output #1
7
1
Hint
- Test case #1: Giả sử ~4~ bạn là ~A,B,C,D~ cần chia thành ~2~ nhóm ta có các cách sau: ~(1): ABC, D; (2) ABD, C; (3) ACD, B; (4) BCD, A; (5) AB, CD; (6) AC, BD; (7) AD, BC~;
- Test case #2: Giả sử ~3~ bạn là ~A, B, C~ ta chỉ có duy nhất một cách chia thành ~3~ nhóm là: ~A; B; C~
Problem source: Chuyên Sơn La Online Judge
Bình luận
long long SoCach(int n,int k){ if(k==1||k==n)return 1;//khi k=1 hay k=n (nhóm) thì chỉ có 1 cách chia duy nhât else return k*SoCach(n-1,k)+SoCach(n-1,k-1); } //sẽ có 2 phương án để người thứ n vào nhóm : 1.cho vào cùng 1 trong các nhóm cũ , tổng số người của các nhóm cũ là n-1 ,được chia làm k nhóm nên số cách chọn 1 nhóm bất kì để thêm người thứ n vào là k(số nhóm) nhân với số cách chia nếu có n-1 người chia làm k nhóm 2.tạo riêng 1 nhóm mới cho ngươid thứ n thì số người trước khi thêm sẽ là n-1 và số nhóm là k-1 .Vậy số cách chia của k-1 nhóm cho n-1 người cũng chính là số cách tạo 1 nhóm mới cho người thứ n...