Ada and Teams

Nguồn: SPOJ ADATEAMS (đề viết lại trên CLUE OJ) Độ khó: Trung bình Tổ hợp Nghịch đảo modulo Lũy thừa nhanh

Đề bài

Ada sắp đại diện trường mình tham dự một kỳ thi Olympic Toán. Có $N$ trường, trong đó đúng $A$ trường được tham dự. Mỗi trường có $B$ học sinh, trong đó đúng $D$ học sinh được tham dự. Hỏi có bao nhiêu cách chọn tập hợp các học sinh tham dự? Các trường và các học sinh đều phân biệt, thứ tự không quan trọng.

Input: gồm nhiều dòng (đọc tới hết dữ liệu), mỗi dòng chứa bốn số nguyên $N, A, B, D$ $(1 \le A \le N \le 10^6,\ 1 \le D \le B \le 10^6)$. Có không quá $10^4$ dòng.

Output: với mỗi dòng, in ra số cách chọn, lấy phần dư khi chia cho $10^9 + 7$.

Subtask: Subtask 1 ($30\%$ số điểm): $N, B \le 1000$. Subtask 2 ($70\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ – input

2 1 2 2
2 2 2 1
2 1 2 1
4 3 3 2
4 2 1 1
10 4 12 7
50 30 44 20

Ví dụ – output

2
4
4
108
6
625817778
154746653

Giải thích: với dòng 4 3 3 2: có $\binom{4}{3} = 4$ cách chọn $3$ trường, mỗi trường có $\binom{3}{2} = 3$ cách chọn $2$ học sinh, nên đáp án là $4 \cdot 3^3 = 108$.

Lời mở đầu

Công thức đếm rất gọn: chọn $A$ trường trong $N$ trường, rồi mỗi trường được chọn chọn độc lập $D$ học sinh trong $B$ học sinh:

Đáp án

$$\binom{N}{A} \cdot \binom{B}{D}^{A} \bmod (10^9 + 7)$$

Cái khó nằm ở chỗ tính nhanh: tới $10^4$ truy vấn, mỗi số tới $10^6$. Ta cần ba công cụ của chương đồng dư: giai thừa lấy dư, nghịch đảo modulo (để "chia" cho $k!$) và lũy thừa nhanh (mũ $A$ tới $10^6$).

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test8 test, 2 mứcÝ tưởnggiai thừa + nghịch đảoCách 1tính từng truy vấnCách 2tiền xử lý giai thừaTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Test	Số dòng	$N$ lớn nhất	$B$ lớn nhất	Ghi chú
1	7	50	44	đúng ví dụ đề
2, 3	10 000	1 000	1 000	subtask 1
4	5 000	30	30	số nhỏ
5	10 000	$\approx 10^6$	$10^6$	subtask 2
6	10 000	$10^6$	$10^6$	653 dòng có $N = A = 10^6$
7	3 000	$10^6$	$10^6$	192 dòng có $N = A = 10^6$
8	10 000	100 000	99 978	subtask 2

Subtask	Điều kiện	Các test	Cách ăn được
1 (30%)	$N, B \le 1000$	1 – 4	Cách 1, 2
2 (70%)	$N, B \le 10^6$	5 – 8	Cách 2

Ý tưởngTổ hợp modulo = giai thừa × nghịch đảo

$\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$. Trong đồng dư ta không chia được, nhưng $p = 10^9+7$ là số nguyên tố nên mọi số $x$ không chia hết cho $p$ đều có nghịch đảo $x^{-1} \equiv x^{p-2} \pmod p$ (định lý Fermat nhỏ). Vì vậy:

Tổ hợp modulo

$$\binom{n}{k} \equiv n! \cdot (k!)^{-1} \cdot \big((n-k)!\big)^{-1} \pmod p$$

Nếu tính sẵn $fact[i] = i! \bmod p$ và $inv\_fact[i] = (i!)^{-1} \bmod p$ cho mọi $i \le 10^6$ thì mỗi tổ hợp chỉ còn 2 phép nhân. Mẹo tính $inv\_fact$ nhanh: chỉ cần một lần lũy thừa cho $inv\_fact[10^6]$, rồi đi lùi $inv\_fact[i-1] = inv\_fact[i] \cdot i$ (vì $\frac{1}{(i-1)!} = \frac{i}{i!}$).

Lũy thừa $x^A$ dùng lũy thừa nhanh: bình phương liên tục theo các bit của $A$. Em nhập 4 số rồi bấm Tiếp:

N A B D =

Ví dụ nhanh:

Cách 1Tính tổ hợp và lũy thừa trực tiếp cho từng dòng

Với mỗi dòng: tính $\binom{n}{k}$ bằng tích $n(n-1)\cdots(n-k+1)$ chia cho $k!$ (chia = nhân nghịch đảo Fermat), rồi nhân $\binom{B}{D}$ thêm $A$ lần. Mỗi dòng tốn $O(A + D + A)$ phép tính.

C++▶ Chạy tay từng dòng codeCách 1: C(n, k) = n(n-1)…(n-k+1) · (k!)^(p-2); rồi nhân C(B, D) thêm A lần.

Dữ liệu vào (stdin) – sửa thoải mái4 3 3 2 2 1 2 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi dòng cần khoảng $2D + 2A$ phép nhân cộng thêm một lần lũy thừa: với $N, B \le 1000$ và $10^4$ dòng là khoảng $3 \cdot 10^7$ phép – vẫn kịp.
• Khi $A, D$ cỡ $10^6$ thì mỗi dòng tốn vài triệu phép, nhân với $10^4$ dòng là $10^{10}$ – quá chậm.
• Lưu ý (n - i) % MOD và (i + 1) % MOD – ở đây các số đã nhỏ hơn $p$, nhưng thói quen lấy dư trước khi nhân giúp tránh tràn số.

Không gian$O(1)$

Thời gian$O\big(Q \cdot (A + D + \log p)\big)$

Kết quả chạy thật: bản C++ đúng 4/8 test (Subtask 1: 4/4, Subtask 2: 0/4). Bản Python đúng 2/8 (Subtask 1: 2/4, Subtask 2: 0/4).

Cách 2Tiền xử lý giai thừa + nghịch đảo giai thừa – O(MAX + Q log A)

Tính sẵn $fact$ và $inv\_fact$ tới $10^6$ một lần duy nhất ($2 \cdot 10^6$ phép nhân + 1 lần lũy thừa). Sau đó mỗi dòng chỉ còn 2 tổ hợp $O(1)$ và một lũy thừa nhanh $O(\log A)$.

C++▶ Chạy tay từng dòng codeCách 2 (khung minh hoạ dùng MAXV = 12 thay cho 10^6): tính fact, inv_fact rồi trả lời mỗi dòng O(log A).

Dữ liệu vào (stdin) – sửa thoải mái4 3 3 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Phần tiền xử lý chạy một lần: khoảng $2 \cdot 10^6$ phép nhân lấy dư – vài mili giây.
• Mỗi dòng: 4 phép nhân cho 2 tổ hợp và khoảng 20 vòng lặp lũy thừa nhanh (vì $A \le 10^6 < 2^{20}$).
• Bản Python chỉ tính giai thừa tới số lớn nhất xuất hiện trong dữ liệu, và dùng pow(x, e, MOD) có sẵn.

Không gian$O(MAX)$

Thời gian$O(MAX + Q \log A)$

Kết quả chạy thật: bản C++ đúng 8/8 test, lâu nhất 0,038s; bản Python đúng 8/8, lâu nhất 0,421s.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 2 cách (C++ và Python) trên toàn bộ 8 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–4	Subtask 2 test 5–8	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	4/4	0/4	4/8	0,075s
Cách 1 – Python	2/4	0/4	2/8	0,085s
Cách 2 – C++	4/4	4/4	8/8	0,038s
Cách 2 – Python	4/4	4/4	8/8	0,421s

Ghi chú của mình: bộ ba "giai thừa – nghịch đảo giai thừa – lũy thừa nhanh" là mẫu chuẩn cho mọi bài tổ hợp modulo số nguyên tố. Nhớ mẹo tính inv_fact đi lùi chỉ với một lần lũy thừa, thay vì lũy thừa cho từng số.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇