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\(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


  • 1
    jumptozero    4:16 p.m. 20 Tháng 6, 2021 đã chỉnh sửa

    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

    • 2 bình luận nữa