Tổ hợp
đã đăng 10 giờ trước 0Tổng hợp công thức tổ hợp dùng trong lập trình thi đấu
1. Giai thừa và Hoán vị
Giai thừa:
\[n! = n \times (n - 1) \times \dots \times 1 \]- Số cách sắp xếp
nphần tử phân biệt.
- Số cách sắp xếp
Hoán vị:
\[ P(n, k) = \frac{n!}{(n - k)!} \]- Số cách chọn và sắp xếp
kphần tử từnphần tử.
- Số cách chọn và sắp xếp
2. Tổ hợp (Combination)
\[ C(n, k) = \frac{n!}{k!(n - k)!} \]
- Số cách chọn
kphần tử từnphần tử.
- Số cách chọn
Tính nhanh C(n, k) mod p:
\[ C(n, k) \equiv \frac{fac[n]}{fac[k] \cdot fac[n-k]} \mod p \]
3. Tổ hợp lặp (Combination with repetition)
- \[ H(n, k) = C(n + k - 1, k) \]
- Số cách chọn
kphần tử từnloại, cho phép lặp.
- Số cách chọn
4. Đếm phân hoạch số
- \[ P(n) \] — số cách phân tích
nthành tổng các số nguyên dương.
5. Nguyên lý Dirichlet (Pigeonhole Principle)
- Nếu có
nvật phân vàomhộp vàn > m, thì ít nhất một hộp có ≥ 2 vật.
🐦 Định nghĩa cơ bản
Nếu bạn đặt n + 1 vật vào n hộp, thì ít nhất một hộp sẽ chứa ≥ 2 vật.
🔧 Phiên bản mở rộng
1. Phiên bản tổng quát:
Nếu có \(kn + 1\) vật và \(n\) hộp, thì ít nhất một hộp có ≥ \(k + 1\) vật.
2. Phiên bản tồn tại:
Nếu số phần tử vượt quá số nhóm phân biệt được, thì tồn tại ít nhất 2 phần tử có cùng nhóm.
📌 Ứng dụng trong các bài toán
1. Số dư chia (mod)
- Trong dãy gồm \(n + 1\) số, tồn tại hai số có cùng số dư khi chia cho \(n\).
2. Tổng đoạn con chia hết
- Cho dãy \(A[1..n]\), tồn tại đoạn con có tổng chia hết cho \(n\).
- Ý tưởng: Dùng prefix sum và số dư mod n → áp dụng Dirichlet.
3. Tổng chữ số giống nhau
- Trong \(n + 1\) số từ \(1\) đến \(2n\), tồn tại hai số có tổng chữ số giống nhau.
4. Sinh nhật trùng nhau
- Có 367 người → tồn tại ít nhất 2 người cùng ngày sinh (năm có 366 ngày).
5. Ứng dụng trong màu sắc, bàn cờ
- Số lượng vật nhiều hơn số cách phân biệt → có ít nhất hai vật giống nhau về thuộc tính.
🧠 Mẹo áp dụng trong lập trình thi đấu
| Tình huống | Có thể áp dụng Dirichlet? |
|---|---|
| Số phần tử > số nhóm | ✅ |
| Cần chứng minh tồn tại | ✅ |
| Phản chứng rằng không thể phân đủ | ✅ |
🧪 Bài toán mẫu
Bài 1: Tổng đoạn con chia hết cho n
- Cho mảng \(A[1..n]\), tìm đoạn con có tổng chia hết cho \(n\).
- Giải: Dùng prefix sum, tìm hai chỉ số có cùng số dư \(\mod n\).
Bài 2: Tất cùng màu
- Có 10 đôi tất. Rút tối thiểu bao nhiêu chiếc để chắc chắn có 1 đôi cùng màu?
- Giải: 11 chiếc → chắc chắn có ít nhất 1 đôi (áp dụng Dirichlet).
Bài 3: Sinh nhật trùng
- Có 367 người → tồn tại ít nhất 2 người sinh cùng ngày.
📌 Tổng kết
- Dirichlet rất mạnh để chứng minh tồn tại.
- Thường áp dụng trong bài toán chứng minh ngược, chia nhóm, hoặc đếm dư.
6. Nghịch đảo Fermat
- \[ a^{-1} \equiv a^{p-2} \mod p \]
7. Công thức Lucas (khi n rất lớn, mod nguyên tố nhỏ)
- \[ C(n, k) \mod p = C(n/p, k/p) \cdot C(n \bmod p, k \bmod p) \mod p \]
8. Số Catalan
- \[ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!(n+1)!} \]
9. Tam giác Pascal
- \[ C(n, k) = C(n - 1, k - 1) + C(n - 1, k) \]
10. Derangement – Hoán vị không cố định
Derangement là số lượng hoán vị của n phần tử sao cho không phần tử nào ở đúng vị trí ban đầu.
Ví dụ với n = 3:
[1,2,3]❌[2,1,3]❌[3,1,2]✅[2,3,1]✅
Suy ra: !3 = 2.
1. Công thức tính
Đệ quy:
\[ !n = (n - 1)(!(n - 1) + !(n - 2)),\quad !0 = 1,\\ !1 = 0 \]
Công thức đóng:
\[ !n = n! \cdot \left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} \right) \]
Gần đúng:
\[ !n \approx \frac{n!}{e} \]
🎩 Bài toán n chiếc mũ (Hat Check Problem)
- Xác suất không ai nhận đúng mũ:
\[ P = \frac{!n}{n!} \]
🔁 Ghép cặp sai hoàn toàn
- Đếm số cách
nngười tặng quà mà không ai nhận từ chính người mình tặng.
🔐 Mã hóa và mật mã học
- Tạo ánh xạ không tự trỏ (self-mapping), tăng tính an toàn.
🎲 Xáo trộn an toàn
- Dùng trong test case, shuffle ngẫu nhiên nhưng tránh vị trí ban đầu.
Mã C++ tính Derangement
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
long long der[MAXN];
void calc_derangement(int n) {
der[0] = 1;
der[1] = 0;
for (int i = 2; i <= n; ++i) {
der[i] = (i - 1) * (der[i - 1] + der[i - 2]) % MOD;
}
}
Tổ hợp giải phương trình x₁ + x₂ + ... + xₘ = n
1. Nghiệm nguyên không âm:
- \[ C(n + m - 1, m - 1) \]
2. Nghiệm nguyên dương:
- \[ C(n - 1, m - 1) \]
Dưới đây là hàm tính tổ hợp \(C(n,k) \mod p\) bằng cách tiền xử lý giai thừa và nghịch đảo modular, rất chuẩn cho lập trình thi đấu:
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
long long fac[MAXN], inv[MAXN];
// Hàm mũ nhanh
long long powmod(long long a, long long b) {
long long res = 1;
a %= MOD;
while (b > 0) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
// Tiền xử lý giai thừa và nghịch đảo
void prepare() {
fac[0] = inv[0] = 1;
for (int i = 1; i < MAXN; ++i) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = powmod(fac[i], MOD - 2); // nghịch đảo theo Fermat vì MOD là số nguyên tố
}
}
// Tính C(n, k) mod MOD
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
}
Các bài toán tương tự và biến thể
1. Nghiệm có giới hạn trên: 0 ≤ xᵢ ≤ bᵢ
- Dùng bao hàm hoặc DP.
2. Chia kẹo cho trẻ:
- Không ràng buộc: \(C(n + m - 1, m - 1)\)
- Mỗi đứa \( \ge 1\) viên: \(C(n - 1, m - 1)\)
3. Đếm số dãy có tổng = n với các phần tử thuộc tập cho trước
- Dùng DP kiểu coin change.
4. Đếm số phân tích n thành tổng các số dương
- Không phân biệt thứ tự: dùng DP.
- Phân biệt thứ tự: như coin change.
5. Ràng buộc \(x_i \ge a_i\)
- Đặt \(x_i = y_i + a_i \Rightarrow \sum y_i = n - \sum a_i\)
6. Chia n phần tử vào m nhóm (không rỗng)
- Dùng Stirling số loại 2: \(S(n, m)\)
7. Sắp xếp n phần tử vào m hộp không rỗng (phân biệt)
- \(m! \cdot S(n, m)\)
8. Phân phối có giới hạn trên
- Dùng bao lơn hoặc DP nâng cao.