Combinatorics

IĐếm cách chọn và cách xếp

Hai quy tắc nền tảng nhất:

• Quy tắc cộng: một việc làm được bằng một trong hai nhóm cách rời nhau (không cách nào thuộc cả hai nhóm), nhóm đầu có $a$ cách, nhóm sau có $b$ cách, thì có $a + b$ cách. Từ nhà tới trường có 2 đường đi bộ hoặc 3 tuyến xe buýt thì có $2 + 3 = 5$ cách đi.
• Quy tắc nhân: một việc gồm hai bước liên tiếp, bước đầu có $a$ cách và với mỗi cách đó bước sau luôn có $b$ cách, thì có $a \cdot b$ cách. Có 3 áo và 4 quần thì có $3 \cdot 4 = 12$ bộ đồ.

Xếp $n$ người vào một hàng: vị trí đầu có $n$ cách chọn người, vị trí sau còn $n - 1$ cách, và cứ thế. Theo quy tắc nhân, số cách là $n \cdot (n - 1) \cdots 1$, gọi là giai thừa (factorial) và viết $n!$, quy ước $0! = 1$. Mỗi cách xếp $n$ vật khác nhau thành hàng là một hoán vị (permutation).

Chọn ra $k$ trong $n$ người và xếp họ theo thứ tự (ví dụ chọn đội trưởng rồi đội phó) gọi là chỉnh hợp (arrangement). Số chỉnh hợp là $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$; chọn 1 đội trưởng và 1 đội phó trong 5 bạn có $5 \cdot 4 = 20$ cách.

Nếu chỉ chọn một nhóm $k$ người mà không quan tâm thứ tự thì ta có tổ hợp (combination). Mỗi nhóm $k$ người được đếm $k!$ lần trong số chỉnh hợp, vì $k$ người ấy xếp được thành $k!$ thứ tự khác nhau. Vậy số tổ hợp, viết $\binom{n}{k}$ và đọc là “$n$ chọn $k$”, là

Chọn 2 trong 5 bạn đi trực có $\frac{20}{2} = 10$ cách. Từ công thức ta thấy $\binom{n}{k} = \binom{n}{n-k}$ (chọn $k$ người ở lại cũng là chọn $n - k$ người đi) và $\binom{n}{0} = 1$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;

signed main() {
    cin >> n;
    cout << n * (n - 1) << '\n';
}

ChạyInput3

Output6

Còn một bài toán xếp hay gặp nữa. Có bao nhiêu xâu khác nhau tạo được từ các chữ của aab? Nếu coi hai chữ a là khác nhau thì có $3! = 6$ cách xếp, nhưng đổi chỗ hai chữ a cho cùng một xâu, nên mỗi xâu bị đếm $2! = 2$ lần, và đáp án là $3$. Tổng quát, có $n$ vật gồm $c_1$ vật loại 1, $c_2$ vật loại 2, ..., thì số cách xếp thành hàng, gọi là hoán vị lặp, là

Còn hoán vị vòng: xếp $n$ người quanh một bàn tròn, hai cách xếp coi là một nếu xoay bàn cái này thành được cái kia. Ta cố định một người ở một chỗ, $n - 1$ người còn lại xếp tự do vào các chỗ còn lại, nên có $(n-1)!$ cách.

IITính C(n, k)

Khi $n$ nhỏ, ta tính $\binom{n}{k}$ từ chính ý nghĩa của nó. Xét vật cuối cùng trong $n$ vật. Nếu không chọn nó, ta phải chọn $k$ vật trong $n - 1$ vật còn lại: $\binom{n-1}{k}$ cách. Nếu chọn nó, ta còn phải chọn $k - 1$ vật trong $n - 1$ vật: $\binom{n-1}{k-1}$ cách. Vậy

Xếp các giá trị theo từng hàng $n = 0, 1, 2, \dots$ ta được tam giác Pascal, mỗi số là tổng hai số ngay phía trên nó:

Chương trình dưới đây tính cả bảng theo modulo $m$ bất kỳ, chỉ cần cộng và lấy dư:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, m, c[2005][2005];

signed main() {
    cin >> n >> k >> m;
    for (ll i = 0; i <= n; i++) {
        c[i][0] = 1 % m;
        for (ll j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
    }
    cout << c[n][k] << '\n';
}

ChạyInput10 4 12

Output6

Độ phức tạp: $O(n^2)$, với $n = 2000$ cần khoảng $2 \cdot 10^6$ phép tính.

Với $n$ tới $10^6$ thì bảng $n^2$ không còn dùng được, ta dùng công thức $\frac{n!}{k!(n-k)!}$. Khi modulo $p$ là số nguyên tố, phép chia cho $x$ là nhân với nghịch đảo $x^{p-2}$ (bài 0.9). Ta tính bảng giai thừa $fact_i = i! \bmod p$, rồi chỉ một lần lũy thừa nhanh để có nghịch đảo của $n!$; các nghịch đảo còn lại suy ra bằng $\frac{1}{(i-1)!} = i \cdot \frac{1}{i!}$. Sau đó mỗi $\binom{n}{k}$ chỉ cần hai phép nhân.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 1e6 + 5;
ll q, fact[N], ifact[N];

ll pw(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

ll C(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    fact[0] = 1;
    for (ll i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[N - 1] = pw(fact[N - 1], MOD - 2);
    for (ll i = N - 1; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;
    cin >> q;
    while (q--) {
        ll n, k;
        cin >> n >> k;
        cout << C(n, k) << '\n';
    }
}

ChạyInput3
5 2
10 3
1000000 500000

Output10
120
996692777

Độ phức tạp: $O(N + \log MOD + q)$, với $N = 10^6$ cần khoảng $2 \cdot 10^6$ phép nhân để lập bảng, mỗi truy vấn thêm 2 phép nhân.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
ll n, k, fact[20];

signed main() {
    cin >> n >> k;
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    cout << fact[n] / fact[k] / fact[n - k] << '\n';
}

ChạyInput13 6

Output62

Ví dụHoán vị của đa tập ký tự

Đề. Cho xâu $s$ gồm các chữ cái thường, độ dài $n \le 10^6$. Đếm số xâu khác nhau tạo được bằng cách xếp lại toàn bộ các ký tự của $s$, in kết quả modulo $10^9 + 7$.

Lời giải. Đây chính là hoán vị lặp: gọi $c_x$ là số lần chữ cái $x$ xuất hiện, đáp án là $\frac{n!}{c_a!\,c_b!\cdots c_z!}$. Ta tính $n!$ rồi nhân với nghịch đảo giai thừa của $c_x$ của từng chữ cái.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 1e6 + 5;
ll fact[N], ifact[N], cnt[26];
string s;

ll pw(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    ll n = s.size();
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = pw(fact[n], MOD - 2);
    for (ll i = n; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;
    for (char ch : s) cnt[ch - 'a']++;
    ll ans = fact[n];
    for (ll x = 0; x < 26; x++) ans = ans * ifact[cnt[x]] % MOD;
    cout << ans << '\n';
}

ChạyInputaab

Output3

Độ phức tạp: $O(n + \log MOD)$, với $n = 10^6$ cần khoảng $2 \cdot 10^6$ phép nhân.

Cần cẩn thận khi modulo không phải số nguyên tố (chẳng hạn $987654321$): khi đó $k!$ thường không có nghịch đảo, nên không dùng được cách trên. Nếu $n$ đủ nhỏ ta dùng bảng Pascal, vì nó chỉ cần cộng; còn nếu phải chia thì ta chia trước, hoặc rút gọn tử và mẫu, rồi mới lấy dư.

Còn một trường hợp nữa: $n$ rất lớn (tới $10^9$) nhưng $k$ nhỏ. Bảng giai thừa tới $n$ không thể lập, nhưng $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$ chỉ gồm $k$ thừa số ở tử và $k$ thừa số ở mẫu. Ta nhân hết tử, nhân hết mẫu, rồi chia một lần. Ví dụ sau dùng cách đó, và dùng thêm một đẳng thức: số tập con của $n$ phần tử là $2^n$, vì mỗi phần tử có hai lựa chọn là có mặt hoặc không (quy tắc nhân). Chia các tập con theo kích thước thì $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$.

Ví dụBó chọn tránh hai kích thước

Đề. Có $n$ loại hoa, mỗi loại đúng một bông ($2 \le n \le 10^9$). Chọn một tập con khác rỗng làm bó hoa, nhưng bó không được có đúng $a$ bông hoặc đúng $b$ bông ($1 \le a < b \le \min(n, 2 \cdot 10^5)$). Đếm số bó hoa, modulo $10^9 + 7$.

Lời giải. Có $2^n - 1$ tập con khác rỗng. Các bó có đúng $a$ bông là $\binom{n}{a}$, các bó có đúng $b$ bông là $\binom{n}{b}$, hai nhóm này rời nhau vì $a \ne b$. Đáp án là $2^n - 1 - \binom{n}{a} - \binom{n}{b}$. Vì $n < MOD$ nên các thừa số $n - k + i$ không chia hết cho $MOD$, và mẫu $k!$ cũng không. Kết quả có thể âm sau phép trừ, nên cộng thêm $MOD$ trước khi lấy dư lần cuối.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
ll n, a, b;

ll pw(ll x, ll y) {
    ll r = 1;
    while (y) {
        if (y & 1) r = r * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return r;
}

ll C(ll n, ll k) {
    ll up = 1, down = 1;
    for (ll i = 1; i <= k; i++) {
        up = up * ((n - k + i) % MOD) % MOD;
        down = down * i % MOD;
    }
    return up * pw(down, MOD - 2) % MOD;
}

signed main() {
    cin >> n >> a >> b;
    ll ans = (pw(2, n) - 1 - C(n, a) - C(n, b)) % MOD;
    cout << (ans + MOD) % MOD << '\n';
}

ChạyInput4 1 3

Output7

Độ phức tạp: $O(b + \log n + \log MOD)$, với $b = 2 \cdot 10^5$ cần khoảng $8 \cdot 10^5$ phép tính.

IIIChia kẹo: sao và vạch

Bài toán ở đầu trang là đếm nghiệm nguyên không âm $(x_1, \dots, x_k)$ của phương trình $x_1 + x_2 + \cdots + x_k = n$, trong đó $x_i$ là số kẹo của bạn thứ $i$. Hình dưới là $n = 5$, $k = 3$: dãy trên ứng với $(2, 1, 2)$, dãy dưới ứng với $(0, 5, 0)$, và hai vạch đứng cạnh nhau nghĩa là có bạn không nhận được kẹo nào.

Mỗi nghiệm ứng với đúng một dãy $n$ sao và $k - 1$ vạch, và ngược lại, nên số nghiệm bằng số cách chọn $k - 1$ vị trí vạch trong $n + k - 1$ vị trí:

Với $n = 5$, $k = 3$ ta được $\binom{7}{2} = 21$ cách. Nếu mỗi bạn phải nhận ít nhất một kẹo (nghiệm dương), ta phát trước cho mỗi bạn một kẹo, rồi chia $n - k$ kẹo còn lại cho tự do: $\binom{n - 1}{k - 1}$ cách. Tổng quát, khi $x_i \ge l_i$ ta đặt $y_i = x_i - l_i \ge 0$ và chia $n - (l_1 + \cdots + l_k)$ kẹo.

Ví dụChia các vật giống nhau

Đề. Có $n$ trẻ em phân biệt và $m$ quả táo giống hệt nhau ($1 \le n, m \le 10^6$); mỗi em có thể nhận $0$ quả. Đếm số cách phân phối toàn bộ $m$ quả táo, modulo $10^9 + 7$.

Lời giải. Đây đúng là bài sao và vạch với $m$ sao, $n - 1$ vạch: đáp án $\binom{m + n - 1}{n - 1}$. Bảng giai thừa cần tới $m + n - 1$, tức gần $2 \cdot 10^6$ phần tử.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 2e6 + 5;
ll n, m, fact[N], ifact[N];

ll pw(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

signed main() {
    cin >> n >> m;
    ll t = n + m - 1;
    fact[0] = 1;
    for (ll i = 1; i <= t; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[t] = pw(fact[t], MOD - 2);
    for (ll i = t; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;
    cout << fact[t] * ifact[n - 1] % MOD * ifact[m] % MOD << '\n';
}

ChạyInput3 5

Output21

Độ phức tạp: $O(n + m + \log MOD)$, với $n + m = 2 \cdot 10^6$ cần khoảng $4 \cdot 10^6$ phép nhân.

IVSố Catalan: dãy ngoặc đúng

Một xâu gồm các dấu ( và ) là dãy ngoặc đúng nếu số dấu mở bằng số dấu đóng, và trong mọi tiền tố, số dấu đóng không vượt quá số dấu mở. Gọi $\mathrm{Cat}_n$ là số dãy ngoặc đúng có $n$ cặp ngoặc. Với $n = 3$ có $5$ dãy: ((())), (()()), (())(), ()(()), ()()().

Có hai cách tính. Cách thứ nhất là truy hồi: dấu ( đầu tiên được đóng bởi một dấu ) nào đó; bên trong là một dãy đúng có $i$ cặp, phần phía sau là một dãy đúng có $n - 1 - i$ cặp, nên

cho dãy $1, 1, 2, 5, 14, 42, 132, \dots$ nhưng tốn $O(n^2)$. Cách thứ hai là công thức trực tiếp

Số Catalan xuất hiện ở nhiều bài toán khác nhau với cùng đáp án: số cách chia một đa giác lồi $n + 2$ đỉnh thành các tam giác bằng những đường chéo không cắt nhau, hay số cây nhị phân có $n$ nút.

Ví dụĐếm Chuỗi Ngoặc Đúng

Đề. Cho độ dài $n$ ($1 \le n \le 10^6$). Đếm số dãy ngoặc đúng có đúng $n$ ký tự, modulo $10^9 + 7$.

Lời giải. Nếu $n$ lẻ thì số dấu mở không thể bằng số dấu đóng, đáp án $0$. Với $n = 2m$, đáp án là $\binom{2m}{m} - \binom{2m}{m+1}$, chỉ cần bảng giai thừa tới $n$ và không cần nghịch đảo của $m + 1$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 1e6 + 5;
ll n, fact[N], ifact[N];

ll pw(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

ll C(ll n, ll k) {
    if (k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}

signed main() {
    cin >> n;
    if (n % 2) {
        cout << 0 << '\n';
        return 0;
    }
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = pw(fact[n], MOD - 2);
    for (ll i = n; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;
    ll m = n / 2;
    cout << (C(n, m) - C(n, m + 1) + MOD) % MOD << '\n';
}

ChạyInput8

Output14

Độ phức tạp: $O(n + \log MOD)$, với $n = 10^6$ cần khoảng $2 \cdot 10^6$ phép nhân.

VTổng trên mọi tập: đếm theo đóng góp

Khi cần tổng của một đại lượng trên mọi cách chọn, ta không liệt kê từng cách. Thay vào đó, ta hỏi mỗi phần tử góp vào tổng bao nhiêu lần, rồi cộng đóng góp của từng phần tử.

Ví dụTổng khoảng biến thiên

Đề. Cho $N$ số nguyên $A_1, \dots, A_N$ ($1 \le N \le 10^5$, $|A_i| \le 10^9$) và số $K \le N$. Với mỗi cách chọn $K$ chỉ số, tính giá trị lớn nhất trừ giá trị nhỏ nhất của các số được chọn. In tổng đại lượng đó trên mọi cách chọn, modulo $10^9 + 7$ (các phần tử bằng nhau nhưng khác chỉ số vẫn là khác nhau).

Lời giải. Sắp xếp $A$ tăng dần và đánh số từ $0$. Phần tử $A_i$ là lớn nhất của một tập $K$ phần tử khi $K - 1$ phần tử còn lại nằm trong $i$ phần tử đứng trước nó: có $\binom{i}{K-1}$ tập. Tương tự, $A_i$ là nhỏ nhất trong $\binom{N-1-i}{K-1}$ tập, vì $K - 1$ phần tử còn lại nằm trong $N - 1 - i$ phần tử đứng sau. Mỗi tập có đúng một phần tử lớn nhất và một phần tử nhỏ nhất theo thứ tự này (kể cả khi có giá trị bằng nhau), nên

Với $A = (1, 5, 9)$ và $K = 2$, hệ số của ba phần tử lần lượt là $0 - 2$, $1 - 1$, $2 - 0$, đáp án $-2 \cdot 1 + 0 \cdot 5 + 2 \cdot 9 = 16$; cũng bằng $4 + 8 + 4$ của ba cặp. Các $A_i$ có thể âm nên đưa về khoảng $[0, MOD)$ trước khi nhân.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 1e5 + 5;
ll n, k, a[N], fact[N], ifact[N];

ll pw(ll x, ll y) {
    ll r = 1;
    while (y) {
        if (y & 1) r = r * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return r;
}

ll C(ll n, ll k) {
    if (k > n) return 0;
    return fact[n] * ifact[k] % MOD * ifact[n - k] % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    fact[0] = 1;
    for (ll i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = pw(fact[n], MOD - 2);
    for (ll i = n; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll coef = (C(i, k - 1) - C(n - 1 - i, k - 1) + MOD) % MOD;
        ans = (ans + (a[i] % MOD + MOD) % MOD * coef) % MOD;
    }
    cout << ans << '\n';
}

ChạyInput3 2
1 5 9

Output16

Độ phức tạp: $O(n \log n)$ cho bước sắp xếp, phần còn lại $O(n)$; với $n = 10^5$ cần khoảng $2 \cdot 10^6$ phép tính.

VINguyên lý Dirichlet

Nguyên lý Dirichlet (pigeonhole principle) phát biểu: nhốt $n + 1$ con thỏ vào $n$ cái chuồng thì có một chuồng chứa ít nhất hai con. Lý do ngắn gọn: nếu mỗi chuồng chứa nhiều nhất một con thì cả thảy chỉ có nhiều nhất $n$ con.

Bài toán: cho $n$ số nguyên $a_1, \dots, a_n$. Tìm một đoạn liên tiếp có tổng chia hết cho $n$. Đoạn như vậy luôn tồn tại. Gọi $p_i = a_1 + \cdots + a_i$ là tổng tiền tố (bài 0.3), $p_0 = 0$. Có $n + 1$ số $p_0, \dots, p_n$ nhưng chỉ có $n$ phần dư khi chia cho $n$, nên có hai chỉ số $i < j$ mà $p_i$ và $p_j$ cùng phần dư. Khi đó $p_j - p_i = a_{i+1} + \cdots + a_j$ chia hết cho $n$. Để tìm đoạn đó, ta ghi nhớ chỉ số đầu tiên của mỗi phần dư.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, a[N], pos[N];

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) pos[i] = -1;
    pos[0] = 0;
    ll p = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        p = ((p + a[i]) % n + n) % n;
        if (pos[p] != -1) {
            cout << pos[p] + 1 << ' ' << i << '\n';
            return 0;
        }
        pos[p] = i;
    }
}

ChạyInput5
4 7 3 8 2

Output2 3

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

Với ví dụ trên, các tổng tiền tố là $4, 11, 14, 22, 24$ và phần dư khi chia cho $5$ lần lượt là $4, 1, 4, 2, 4$. Phần dư $4$ xuất hiện đầu tiên ở chỉ số $1$ và lại xuất hiện ở chỉ số $3$, nên đoạn cần tìm là $[2, 3]$ với $7 + 3 = 10$.

VIISố Stirling loại hai

Số Stirling loại hai $S(n, k)$ là số cách chia $n$ phần tử khác nhau thành $k$ nhóm không rỗng, mà các nhóm không phân biệt thứ tự. Ví dụ $S(3, 2) = 3$: chia $\{1, 2, 3\}$ thành $\{1, 2\} \{3\}$, $\{1, 3\} \{2\}$, $\{2, 3\} \{1\}$.

Để tính, xét phần tử thứ $n$. Nó có thể đứng một mình trong một nhóm: còn chia $n - 1$ phần tử thành $k - 1$ nhóm, $S(n-1, k-1)$ cách. Hoặc nó nằm cùng nhóm với phần tử khác: chia $n - 1$ phần tử thành $k$ nhóm trước ($S(n-1, k)$ cách), rồi xếp phần tử thứ $n$ vào một trong $k$ nhóm đó. Vậy

Hàng $n = 4$ là $S(4, 1..4) = 1, 7, 6, 1$. Tổng của một hàng, $S(n, 1) + \cdots + S(n, n)$, là số cách chia tập $n$ phần tử thành các nhóm bất kỳ, gọi là số Bell; với $n = 4$ ta được $15$.

s[0][0] = 1;
for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= i; j++) s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % MOD;

Độ phức tạp: $O(n^2)$, với $n = 5000$ cần khoảng $1{,}25 \cdot 10^7$ phép tính.