Kẹo đây
Xem PDF
Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
KHÔI có \(n\) viên kẹo khác nhau.
KHÔI muốn cho LONG ít nhất một viên kẹo.
Hỏi có bao nhiêu cách để KHÔI cho LONG kẹo.
Input
- Số nguyên dương \(t (t \leq 1000)\) - số test.
- Mỗi test chứa \(1\) số nguyên dương \(n(n \leq 10^4)\)
Output
- Số cách cho kẹo % \(10^5\).
Example
Test 1
Input
2
1
2 Output
1
3
Bình luận
Mình xin chia sẻ lời giải bài này như sau: Giả sử ta đánh số các viên kẹo đã cho từ \(1\) đến \(n\).
Khi đó:
Số cách Khôi cho Long \(i\) viên kẹo là: \(\binom{n}{i}\) với \(0\le i\le n\). Trong đó: \(\binom{n}{i}=\frac{n!}{i!(n-i)!}\)
Khi đó số cách chia kẹo thoả mãn yêu cầu bài toán là : \(S=\sum\limits_{i=1}^{n}\binom{n}{i}\)
Mặt khác ta lại có: \(2^{n}=\sum\limits_{i=0}^{n}\binom{n}{i}(*)\) nên từ đây ta suy ra được: \(S=\sum\limits_{i=1}^{n}\binom{n}{i}=2^n-1\)
Đến đây, sử dụng luỹ thừa nhị phân để tính toán, như vậy là bài toán đã được giải quyết !
Ps:
Biểu thức \((*)\) thực chất là phép triển khai nhị thức Newton của biểu thức: \((x+1)^n\) với \(x=1\)
Các bạn có thể tham khảo code tại đây: Link
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
@_@
không để ý là có mod \(10^5\)