Hướng dẫn cho TLEoj Contest #05 - Phần thưởng


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: __Khac_Trung__

Ta giả sử coi người được nhận trứng là 1 nhóm gồm 2 người là người được nhận và người sau đó. Khi đó ta có thể coi nhóm bao gồm người được nhận - người sau đó và người không được nhận bình đẳng với nhau, tức là ta có thể đổi chỗ cho nhau mà không có vấn đề gì. Tuy vậy, ta cần xét 2 trường hợp:

  • Người n là người được nhận trứng, ta bỏ qua người thứ n và chỉ quan tâm n-1 người còn lại. Khi đó có n-k\choose k-1 cách chia khác nhau
  • Người n không là người được nhận trứng. Khi đó có n-k\choose k cách chia khác nhau

Kết quả của bài toán là tổng số cách trong 2 trường hợp trên. Vì m chưa chắc là số nguyên tố nên ta không thể sử dụng nghịch đảo modulo mà phân tích giai thừa thành thừa số nguyên tố sau đó nhân lên.



Bình luận

Không có bình luận nào.