Tổ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 n phần tử phân biệt.

• Hoán vị:
  \[ P(n, k) = \frac{n!}{(n - k)!} \]

  • Số cách chọn và sắp xếp k phần tử từ n phần tử.

2. Tổ hợp (Combination)

• \[ C(n, k) = \frac{n!}{k!(n - k)!} \]

  • Số cách chọn k phần tử từ n phần tử.

• 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 k phần tử từ n loại, cho phép lặp.

4. Đếm phân hoạch số

• \[ P(n) \] — số cách phân tích n thành tổng các số nguyên dương.

5. Nguyên lý Dirichlet (Pigeonhole Principle)

• Nếu có n vật phân vào m hộ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

🧪 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 n ngườ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.