---
title
Tổ hợp cơ bản - Lời giải
---

Tổ hợp cơ bản - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# [Codeforces - 1828C](https://codeforces.com/contest/1828/problem/C)
## Bài toán
### Đề bài
Cho 2 mảng $a$ và $b$ có $n$ phần tử. Không có phần tử nào của $a$ bằng nhau. Tìm số cách xếp lại thứ tự của mảng $a$ sao cho $a_i > b_i$ ($1 \le i \le n$), modulo $10^9+7$. Hai cách sắp xếp được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà hai phần tử tại vị trí đó của hai cách sắp xếp là khác nhau.

### Input
- Dòng đầu tiên gồm một số nguyên $t$ ($1 \le t \le 10^4$) là số lượng bộ test cần tính toán.
- Dòng đầu tiên của mỗi bộ test gồm một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$).
- Dòng thứ hai của mỗi bộ test gồm $n$ số nguyên $a_i$ ($1 \le a_i \le 10^9$) là các phần tử của mảng $a$
- Dòng thứ ba của mỗi bộ test gồm $n$ số nguyên $b_i$ ($1 \le b_i \le 10^9$) là các phần tử của mảng $b$.

Đảm bảo rằng tổng $n$ của các bộ test không vượt quá $2 \cdot 10^5$.

### Output
- Cho mỗi bộ test, in ra một dòng là kết quả của bộ test đó, modulo $10^9+7$.

### Sample input

5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144

### Sample output

32
0
1
0
13824

## Lời giải
:::spoiler **Ý tưởng**
- Đầu tiên ta sẽ sắp xếp lại mảng $b$ theo thứ tự giá trị giảm dần.
- Gọi $f[i]$ là số lượng phần tử trong mảng $a$ có giá trị lớn hơn $b[i]$. Ta thấy rằng có $f[1]$ vị trí $j$ trong mảng $a$ sao cho $a[j] > b[1]$. Với mỗi vị trí $i$ $(2 \le i \le n)$, có $f[i]$ phần tử trong mảng $a$ có thể đặt tương ứng với $b[i]$, tuy nhiên trong $f[i]$ phần tử này có $i-1$ phần tử đã được đặt tương ứng với $i-1$ phần tử đầu tiên trong mảng $b$, vì thế tại vị trí $i$ sẽ có $f[i]-(i-1)$ phần tử trong mảng $a$ có thể được đặt tương ứng với phần tử $b[i]$.
- Gọi $ans[i]$ là số dãy $a$ khác nhau có thể được sắp xếp để thỏa điều kiện đề bài khi xét đến vị trí $i$, theo quy tắc nhân ta có $ans[i] = ans[i-1]\times (f[i]-(i-1))$. Vì để tính $ans[i]$ ta chỉ cần sử dụng $ans[i-1]$ đã tính trước đó nên ta không cần tạo cả mảng mà chỉ cần lưu một biến cộng dồn là được.
- Vậy làm sao để tính mảng $f$? Đầu tiên ta sắp xếp lại mảng $a$ theo thứ tự tăng dần giá trị. Duyệt $i$ từ $1 \rightarrow n$, với mỗi vị trí $i$ ta sẽ tìm xem có bao nhiêu số trong mảng $a$ lớn hơn $b[i]$, ở đây ta sẽ sử dụng tìm kiếm nhị phân bằng `upper_bound` (các bạn có thể đọc về kĩ thuật này qua [bài viết trước](https://hackmd.io/@2SchoolGuideline/SyCPwI5z6#H%C3%A0m-upper_bound)). Ta dùng `upper_bound` để tìm vị trí đầu tiên trong mảng $a$ lớn hơn $b[i]$, gọi vị trí này là $x$, như vậy số lượng số trong mảng $a$ lớn hơn $b[i]$ là $n-x+1$.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>
 
using namespace std;
 
const int mod = 1e9 + 7;
 
void solve()
{    
    int n;
    cin >> n;
    int a[n+1], b[n+1], f[n+1] = {0};

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1, greater<int>());

    for (int i = 1; i <= n; i++)
    {
        int x = upper_bound(a + 1, a + n + 1, b[i])-a;
        f[i] = n-x+1;
    }

    long long ans = f[1];
    for (int i = 2; i <= n; i++) ans = (ans*(f[i]-(i-1)))%mod;
    cout << ans << '\n';
}
 
int main()
{ 
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

:::

# [Bài 3 HSTP9 2022-2023](http://www.chuyentin.pro/2023/03/e-thi-hoc-sinh-gioi-lop-9-mon-tin-hoc_20.html)
## Bài toán
### Đề bài
Cho một mảng $A$ có $n$ phần tử. Xét tất cả các đoạn con (**không liên tiếp**) có $K$ phần tử của mảng $A$, tính tổng của các số lớn nhất của các đoạn con này và modulo $10^9 + 7$.

### Input
- Dòng đầu tiên gồm hai số nguyên $n, K$ ($1 \le n \le 10^5$, $1 \le K \le 5$).
- Dòng thứ hai gồm $n$ số nguyên $A_i$ ($1 \le A_i \le 10^6$) là các phần tử của mảng $A$.

### Output
- Một dòng duy nhất là kết quả của bài toán, modulo $10^9 + 7$.

### Sample input

4 2
6 7 6 5

### Sample output

39

## Lời giải
:::spoiler **Ý tưởng**
Để giải được bài toán này, ta cần rút ra 2 nhận xét sau:
1. Số đoạn con có $K$ phần tử của một đoạn $n$ phần tử sẽ là $C^k_n$.
2. Phần tử lớn nhất của mảng $A$ sẽ là phần tử lớn nhất trong tất cả các đoạn con có nó, tức là $C^{K - 1}_{n - 1}$ đoạn con, vì ta bắt buộc phải lấy phần tử lớn nhất nên đoạn con cần lấy chỉ còn $K - 1$ phần tử và mảng $a$ chỉ còn $n - 1$ phần tử. Tổng quát hơn, phần tử lớn thứ $m$ của mảng $A$ sẽ là phần tử lớn nhất trong $C^{K - 1}_{n - m}$ ($K - 1 \le n - m$) đoạn con có chứa nó ($m$ phần tử đã bị loại ra khỏi $n$ phần tử chính là $m - 1$ phần tử lớn hơn phần tử lớn thứ $m$ và như đã giải thích ở trên, chính phần tử lớn thứ $m$).

Sau đó, ta chỉ cần sắp xếp lại mảng $A$ theo thứ tự tăng hoặc giảm dần rồi duyệt qua $n - K + 1$ (do $K - 1 = n - m$ $\Leftrightarrow m = n - (K - 1) = n - K + 1$) phần tử lớn nhất, với mỗi phần tử, kết quả được cộng cho tích của phần tử đó với số đoạn con có $K$ phần tử mà trong đó phần tử đó là lớn nhất. Vì bài này cho giới hạn $1 \le K \le 5$ và $1 \le n \le 10^5$ nên ta có thể sử dụng cách tính tổ hợp bằng quy hoạch động.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

long long const mod = 1e9 + 7;

int n, k;
long long dp[55][100005], a[100005], ans;

void calc(int k, int n)
{
    for (int i = 0; i <= k; i++) dp[0][i] = dp[i][i] = 1;
    for (int i = k + 1; i <= n; i++) dp[0][i] = 1;
    for (int i = 1; i <= k; i++)
    {
        for (int j = i; j <= n; j++) dp[i][j] = (dp[i][j - 1] % mod + dp[i - 1][j - 1] % mod) % mod;
    }
}

long long Ckn(int k, int n)
{
    if (k <= n) return dp[k][n];
    else return 0; //với cách duyệt vòng for ở (1) thì trường hợp này sẽ không xảy ra
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, greater <long long>());
    calc(k, n);
    for (int i = 1; i <= n - k + 1; i++) ans = (ans % mod + a[i] * Ckn(k - 1, n - i) % mod) % mod; //(1)
    cout << ans;
    return 0;
}

:::

# [Codeforces - 1462E2](https://codeforces.com/contest/1462/problem/E2)
## Bài toán
### Đề bài
Cho một mảng $a$ có $n$ phần tử là các số nguyên từ $1$ đến $n$. Mảng $a$ có thể chứa các phần tử giống nhau. Cho $m$ và $k$, tìm số lượng bộ $m$ phần tử của mảng $a$ sao cho phần tử lớn nhất lớn hơn phần tử nhỏ nhất không quá $k$ đơn vị. Tức là tìm số lượng bộ $m$ chỉ số $1 \le i_1 < i_2 < ... < i_m \le n$ của mảng $a$ sao cho $max(a_{i_1}, a_{i_2}, ..., a_{i_m}) - min(a_{i_1}, a_{i_2}, ..., a_{i_m}) \le k$. Kết quả được modulo $10^9 + 7$.
Ví dụ:
- Nếu $n = 4$, $m = 3$, $k = 2$ và $a = [1, 2, 4, 3]$ thì có **2** bộ $k$ phần tử của mảng $a$ thoả mãn đề bài ($i = 1, j = 2, z = 4$ và $i = 2, j = 3, z = 4$)
- Nếu $n = 4$, $m = 2$, $k = 1$ và $a = [1, 1, 1, 1]$ thì cả **4** bộ $k$ phần tử của mảng $a$ đều thoả mãn đề bài.

### Input
- Dòng đầu tiên gồm một số nguyên $t$ ($1 \le t \le 2 * 10^5$) là số lượng bộ test cần tính toán.
- Dòng đầu tiên của mỗi bộ test gồm ba số nguyên $n$, $m$, $k$ ($1 \le n \le 2 * 10^5$, $1 \le m \le 100$, $1 \le k \le n$).
- Dòng thứ hai của mỗi bộ test gồm $n$ số nguyên $a_i$ ($1 \le a_i \le n$) là các phần tử của mảng $a$.

Đảm bảo rằng tổng $n$ của các bộ test không vượt quá $2 * 10^5$.

### Output
- Cho mỗi bộ test, in ra một dòng là kết quả của bộ test đó, modulo $10^9 + 7$.

### Sample input

4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4

### Sample output

2
6
1
20

## Lời giải
:::spoiler **Ý tưởng**
Đầu tiên, ta sắp xếp lại mảng $a$ theo thứ tự tăng dần. Ta duy trì một đoạn con liên tiếp dài nhất có thể của mảng $a$ sao cho phần tử đầu tiên của đoạn chỉ bé hơn phần tử cuối cùng của đoạn là tối đa $k$ đơn vị. Tức là ta duy trì một đoạn $a_l, a_{l + 1}, ..., a_r$ ($1 \le l \le r \le n$) dài nhất có thể sao cho $a_r - a_l \le k$. Ta có thể thực hiện điều này bằng cách sử dụng kĩ thuật hai con trỏ. Nếu sắp xếp mảng $a$ theo thứ tự giảm dần thì $a_l - a_r \le k$.

Với mỗi một đoạn con liên tiếp mà ta xét, kết quả được cộng cho $C^{m}_{r - l + 1}$. Tuy nhiên, mọi chuyện không chỉ có thể, vì $C^m_{r - l + 1}$ sẽ bao gồm các cách chọn mà có thể sẽ trùng với một số cách chọn khác của các đoạn con liên tiếp mà ta sẽ xét tiếp theo (các đoạn con liên tiếp này có thể giao với đoạn con liên tiếp ta đang xét) và làm cho kết quả bị dư ra.
- Ví dụ: Với hai đoạn con liên tiếp giao nhau là $[1, 3, 5, 7]$ và $[3, 5, 7, 9]$ của mảng $[1, 3, 5, 7, 9]$. Các cách chọn ra $2$ phần tử:
+ Từ đoạn $[1, 3, 5, 7]$ là: $[1, 3]$, $[1, 5]$, $[1, 7]$, $[3, 5]$, $[3, 7]$, $[5, 7]$.
+ Từ đoạn $[3, 5, 7, 9]$ là: $[3, 5]$, $[3, 7]$, $[3, 9]$, $[5, 7]$, $[5, 9]$, $[7, 9]$.

Ta có thể thấy rằng các cách chọn $[3, 5]$, $[3, 7]$, $[5, 7]$ bị lặp lại.

Giải pháp chính là lấy kết quả hiện tại trừ đi $C^m_x$ với $x$ là độ dài đoạn giao nhau của đoạn con liên tiếp hiện tại và đoạn con liên tiếp vừa xét trước đó.

Vì bài này cho giới hạn $1 \le m \le 100$ và $1 \le k \le n \le 10^5$ nên ta có thể sử dụng cách tính tổ hợp bằng quy hoạch động.

Ngoài ra thì bài này cũng còn một số cách giải khác rất hay (ví dụ như sử dụng mảng đếm, làm gì đó để không cần phải trừ cho đoạn giao nhau,...), các bạn có thể tự suy nghĩ và tìm hiểu ^^.
:::

:::spoiler **Cài đặt**

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

int n, m, k, a[200005], prei;
long long ans, dp[105][200005];

void calc(int k, int n)
{
    for (int i = 0; i <= k; i++) dp[0][i] = dp[i][i] = 1;
    for (int i = k + 1; i <= n; i++) dp[0][i] = 1;
    for (int i = 1; i <= k; i++)
    {
        for (int j = i; j <= n; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
    }
}

long long Ckn(int k, int n)
{
    if (k <= n) return dp[k][n];
    else return 0;
}

void Solve()
{
    ans = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int j = 1;
    prei = 0;
    for (int i = 1; i <= n; i++)
    {
        while (a[i] - a[j] > k && j < n && j < i) j++;
        if (i == n || a[i + 1] - a[j] > k) //dài nhất có thể
        {
            ans = (ans + Ckn(m, i - j + 1)) % mod;
            ans = (ans - Ckn(m, max(0, prei - j + 1)) + mod) % mod; //đoạn [j, prei] chính là đoạn giao nhau giữa đoạn con liên tiếp đang xét và đoạn con liên tiếp trước đó
            prei = i;
        }
    }
    cout << ans << "\n";
}

int main()
{
    calc(100, 200000);
    int t; cin >> t;
    while (t--) Solve();
    return 0;
}

:::

# [CSES - Distributing Apples](https://cses.fi/problemset/task/1716)
## Bài toán
### Đề bài
Có $n$ bạn nhỏ và $m$ quả táo. Đếm số lượng cách chia táo cho các bạn nhỏ. Lưu ý rằng trong một cách chia, không nhất thiết bạn nào cũng có táo nhưng phải có ít nhất một bạn có táo. Kết quả được modulo $10^9 + 7$.

### Input
- Một dòng duy nhất gồm hai số nguyên $n$, $m$ ($1 \le n, m \le 10^6$)

### Output
- Một dòng duy nhất là kết quả của bài toán, modulo $10^9 + 7$.

### Input mẫu

3 2

### Output mẫu

6

## Lời giải
:::spoiler **Ý tưởng**
Bài toán này là ví dụ kinh điển của bài toán chia kẹo Euler (mặc dù nó không liên quan lắm đến nhà toán học Leonhard Euler) (còn được gọi là bài toán stars and bars).

Trong bài này ta sẽ sử dụng tổ hợp chứ không phải chỉnh hợp vì hai cách chia táo chỉ khác nhau khi số táo của ít nhất một bạn khác nhau giữa hai cách chọn. Ví dụ: Nếu có $n = 3$ bạn nhỏ và $m = 5$ quả táo thì $[1, 1, 2]$, $[2, 1, 1]$ và $[1, 2, 1]$ là cùng một cách chia táo (lưu ý rằng trong cách chia này thì có $1$ quả táo không được chia).

Ta tưởng tượng rằng:
1. $m$ quả táo được trải dài thành 1 hàng ngang từ trái sang phải và có $n - 1$ thanh chặn tương ứng với mỗi bạn nhỏ (bạn nhỏ cuối cùng sẽ không có thanh chặn, sẽ giải thích sau).
2. Các thanh chặn được đặt ngẫu nhiên vào các khoảng trống giữa các quả táo, bao gồm cả vị trí bên phải quả táo cuối cùng, tức là có $m$ vị trí có thể đặt các thanh chặn vào.
3. Mỗi bạn nhỏ sẽ được lấy những quả táo nằm trong khoảng từ sau thanh chặn gần nhất bên trái đến trước thanh chặn của bản thân (nếu đó là thanh chặn đầu tiên thì lấy những quả táo từ đầu hàng đến trước thanh chặn đó, bạn nhỏ cuối cùng sẽ lấy những quả táo từ sau thanh chặn cuối cùng đến hết hàng).
4. Thoạt nhìn qua thì ta dễ nhầm rằng cách làm này sẽ cho ta kết quả là $C^n_m$. Tuy nhiên, cần lưu ý rằng có thể có tối đa $n - 1$ bạn nhỏ không có táo, nghĩa là ta có thể đặt thêm các thanh chặn vào $n - 1$ vị trí đứng trước (bên trái) quả táo đầu tiên.

Vậy kết quả bài toán sẽ là $C^{n - 1}_{m + n - 1}$. Vì bài này có $1 \le n, m \le 10^6$ ta phải sử dụng cách tính tổ hợp bằng công thức.

Ngoài ra thì bài này cũng còn một số ý tưởng/cách hiểu khác để giải nhưng tất cả đều quy về dạng bài toán chia kẹo Euler (còn được gọi là bài toán stars and bars.
:::

:::spoiler **Cài đặt**
- **Lưu ý:** Mảng tính giai thừa `f` sẽ có tới tận $2\times 10^6$ phần tử (nhưng ta khai báo dư ra là `f[2000005]`) vì ta phải sử dụng đến giai thừa của $m + n - 1$ mà con số này có thể lên tới $2 \times 10^6 - 1$ vì $1 \le n, m \le 10^6$.

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

long long f[2000005];
int n, m;

void factorial(int n)
{
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % mod;
}

long long binpow(long long a, long long b)
{
    if(b == 0) return 1;
    long long temp = binpow(a, b / 2);
    if(b % 2 == 1) return temp * temp % mod * a % mod;
    return temp * temp % mod;
}

long long Ckn(int k, int n)
{
    return f[n] * binpow(f[k] * f[n - k] % mod, mod - 2) % mod;
}

int main()
{
    cin >> n >> m;
    factorial(m + n - 1);
    cout << Ckn(n - 1, m + n - 1);
    return 0;
}

:::