Tính tổ hợp với modulo cho trước

[Tan_Kiem (NKTan)]

cho em hỏi cách lấy dư của tổ hợp ví dụ 100C50 cho 1e9+7.

[rogp10]

Phân tích thừa số nguyên tố của tử & mẫu

Với modulo nguyên tố thì dùng công thức tứ nC(k-1) lên nCk.

[tntxtnt]

Vì p=10^9 +7 nguyên tố nên áp dụng định lý Fermat nhỏ ta có a^p = a (mod p) vậy a^(p-2) = a^-1 (mod p). Vậy 100C50 mod p tính là (100*99*98*…*51)*(50!)^(p-2) mod p :V

[Tan_Kiem (NKTan)]

nhờ mấy bạn cùng trường họ bảo tính bằng quy hoạch động rồi mod được r:v

[rogp10]

Công thức Pascal à chi cho tốn mem

[tntxtnt]

đúng là ko nghĩ ra cái tam giác Pascal