Bài tập | NEU OJ

Hệ số tổ hợp $\binom{n}{k}\bmod p$

Nhiều giao thức mật mã dùng hệ số tổ hợp modulo một số nguyên tố. Vì phép chia không tồn tại trực tiếp trong số học modular, ta dùng nghịch đảo Fermat cho mẫu số:

$\binom{n}{k} = \frac{n!}{k!\,(n-k)!} \bmod p$

Cho $n$ , $k$ , $p$ (với $p$ nguyên tố, $n<p$ ). In $\binom{n}{k}\bmod p$ . Nếu $k<0$ hoặc $k>n$ thì kết quả là $0$ .

Ví dụ

$\binom{5}{2}=10$ , và $10\bmod 1000000007 = 10$ .

Định dạng đầu vào:
Một dòng gồm ba số nguyên $n$ , $k$ , $p$ .
Ràng buộc đầu vào:
$0 \le k \le n < p < 10^{9}$ , $p$ nguyên tố.
Định dạng đầu ra:
Một số nguyên là $\binom{n}{k}\bmod p$ .

solution

Đề bài: [An toàn thông tin] Tổ hợp modulo số nguyên tố

Hệ số tổ hợp $\binom{n}{k}\bmod p$

Ví dụ

solution

Đề bài: [An toàn thông tin] Tổ hợp modulo số nguyên tố

Hệ số tổ hợp (nk) mod p\binom{n}{k}\bmod p(kn​)modp

Ví dụ

Hệ số tổ hợp $\binom{n}{k}\bmod p$