---
title: Tổ hợp cơ bản (tiếp theo)
---

Tổ hợp cơ bản (tiếp theo)
===

-----

###### ✍️ Author: 2School Guideline
###### 📋 Content:

[TOC]

-----

# Những tính chất của tổ hợp
## Tổ hợp
- Phần trước ta đã được biết:

$$
C_n^k = \frac{n!}{(n-k)!\cdot\ k!}
$$

- Nhưng các bạn có biết rằng tổ hợp được xây dựng trên 1 mô hình rất nổi tiếng và đặc biệt - mang tên tam giác Pascal (https://artofproblemsolving.com/wiki/index.php/Pascal%27s_triangle).
- 

- Dòng thứ n và cột thứ k chính là bằng $C_n^k$.

## Các tính chất
- Với tam giác Pascal ở trên, ta có thể đưa ra 1 vài nhận xét:

- $C_n^n$ = $C_n^0$ = 1
- $C_n^k$ = $C_n^{n - k}$ (tính chất đối xứng)
- $C_{‎n}^k$ = $C_{n - 1}^{k - 1}$ + $C_{n - 1}^k$ (hệ thức Pascal)

# Các cách cài đặt tổ hợp
## Cách 1
### Định nghĩa
- Lợi dụng những tính chất của tổ hợp mình đã nêu ở trên, ta dễ dàng nhận ra hoàn toàn có thể sinh được các giá trị của tổ hợp cần tìm từ trước chứ không cần phải áp dụng công thức $C_n^k = \frac{n!}{(n-k)!\cdot\ k!}$
Với cách này thì có 2 tác dụng:
- Tránh tràn số khi tính giai thừa trong công thức (*$n!$*).
- Tăng tốc độ của chương trình khi gọi tổ hợp nhiều lần.

Và cũng có 1 điểm yếu đó là cần độ phức tạp $O(n^2)$.

### Cài đặt

#include<bits/stdc++.h>
using namespace std;

const int N = 30;
long long C[N + 1][N + 1];

int main() {
    for (int n = 0; n <= N; ++n) {
        C[n][n] = C[0][n] = 1; // là những giá trị được định sẵn
        for (int k = 1; k < n; ++k)
            C[k][n] = C[k - 1][n - 1] + C[k][n - 1];
    }
    return 0;
}

**Lưu ý**: Nếu cần mod 1 số thì chỉ cần thêm mod vào các phép tính cộng.

## Cách 2
### Định nghĩa
- Đây là 1 kiến thức nâng cao giúp có thể khởi tạo toàn bộ các tổ hợp (thậm chí có mod số nguyên tố) với độ phức tạp chỉ là $O(n)$ - khắc phục điểm yếu so với cách trên. Và mỗi lần gọi tổ hợp chỉ mất $O(1)$.
- Áp dụng định lý Fermat nhỏ, ta có thể dùng nghịch đảo Modulo dùng thực hiện phép chia khi có mod 1 số nguyên tố.
- Và khi khởi tạo được toàn bộ các *n!* và nghịch đảo của *n!*, ta có thể tính được $C_n^k$ trong $O(1)$.

### Cài đặt

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5;
const ll MOD = 1e9 + 7;

ll fac[N + 1], ifac[N + 1];

ll power(ll a, ll b) {
    ll ans = 1;
    while(b > 0) {
        if(b & 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return ans;
}

ll C(int k, int n) {
    ll ans = fac[n] * ifac[k] % MOD;
    return ans * ifac[n - k] % MOD;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= N; ++i)
        fac[i] = (i * fac[i - 1]) % MOD;
    ifac[N] = power(fac[N], MOD - 2);
    for (int i = N - 1; i >= 0; --i)
        ifac[i] = ((i + 1) * ifac[i + 1]) % MOD;
    return 0;
}

Vì kiến thức này khá nâng cao, nên các bạn có thể đọc thêm về:
- Lũy thừa nhanh: https://vnoi.info/wiki/translate/he/Number-Theory-3.md
- Nghịch đảo Modulo: https://vnoi.info/wiki/algo/math/modular-inverse
- Tổ hợp: https://vnoi.info/wiki/translate/he/Number-Theory-5.md

# Bài tập
## Bài 1: Nhóm múa
- Lớp Tin trường G có $a$ học sinh nam và $b$ học sinh nữ. Sắp tới trường sẽ có một cuộc thi văn nghệ nên giáo viên muốn chọn ra $n$ cặp nam nữ để tham gia.

- **Yêu cầu:** Có bao nhiêu cách chọn $n$ cặp múa đại diện cho lớp Tin?

- **Input:** Số nguyên $a$, $b$, $n$ ($n, m \le 15$); n \le a, b \le 50$).
- **Output:** Số cách chọn cặp múa. Vì kết quả có thể rất lớn nên lấy modulo cho $10^9+7$.

| Input | Output |
| ------ | ------ |
| 10 6 3 | 14400 |

## Bài 2: Nhiều đường đi quá
- Bạn Phương đang chơi một trò chơi bạn mới tìm thấy trên mạng. Nhân vật của bạn đứng ở vị trí (0, 0) trong một mê cung hình chữ nhật và bạn phải điều khiển nhân vật đi đến vị trí ($n, m$) trong mê cung. Với mỗi bước đi, bạn có thể điều khiển nhân vật đi qua phải ($i, j+1$) hoặc xuống dưới ($i+1, j$).
- Bạn Phương phát hiện có nhiều cách di chuyển để đến được đích. Vậy nên, bạn quyết định chơi lại nhiều lần để khám phá nhiều đường đi khác nhau.

- **Yêu cầu:** Bạn Phương sẽ nói số lần bạn đã chơi vòng đó, bạn hãy xác định xem Phương đã thử hết cách di chuyển chưa nhé.

- **Input:** Lần lượt là $n, m$ - kích thước của mê cung ($n, m \le 15$) và $k$ - số lần chơi của Phương (chắc chắn $k$ nhỏ hơn hoặc bằng tổng số cách di chuyển).
- **Output:** Một dòng duy nhất là "*YES*" hoặc "*NO*" tương ứng với việc Phương đã thử hết cách di chuyển hay chưa.

| Input | Output |
| ------ | ------ |
| 2 2 6 | YES |
| 1 2 1 | NO |

## Bài 3: Xổ số kiến thiết
- Tính tổng của các số lớn nhất trong các đoạn con gồm $k$ phần tử trong mảng $a$ có $n$ phần tử.

- **Input:**
- Số nguyên $n$ và $k$ ($n \le 100000$; $1 \le k \le 50$).
- Mảng $a$ gồm $n$ phần tử.
- **Output:** Tổng của các số lớn nhất trong các đoạn con gồm k phần tử modulo cho $10^9+7$

| Input | Output |
| ------ | ------ |
| 4 2 | |
| 6 7 6 5| 39 |