📚 Cẩm Nang Thuật Toán Khổng Lồ

📝 Template Cơ Bản Dễ

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    return 0;
}

⚡ Fast I/O Dễ

// Cách 1: Tắt đồng bộ
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

// Cách 2: Dùng scanf/printf
scanf("%d", &x);
printf("%d\n", x);

// Cách 3: Tự viết getchar (nhanh nhất)
inline int readInt() {
    int x = 0, sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * sign;
}

📐 Kiểu Dữ Liệu Dễ

🚨 Lỗi Thường Gặp Kinh nghiệm

• Tràn số int: Nhân 2 số ~10^5 có thể vượt 10^9 → dùng long long.
• Chia nguyên: 5 / 2 = 2. Muốn chính xác dùng double.
• Modulo số âm: -5 % 3 = -2 trong C++. Dùng (x % m + m) % m.
• Off-by-one: Vòng lặp for (i = 0; i < n; i++) không phải <= n.
• Quên khởi tạo: Mảng toàn cục mặc định 0, mảng cục bộ thì rác.
• So sánh số thực: Dùng abs(a - b) < eps với eps = 1e-9.
• Đệ quy sâu: Stack overflow khi depth > 10^5. Chuyển sang vòng lặp.

🔢 Big Integer — Cộng Trung bình

string congxau(string u, string v) {
    string s = ""; int tmp = 0;
    int i = u.size() - 1, j = v.size() - 1;
    while (i >= 0 || j >= 0 || tmp > 0) {
        int sum = tmp;
        if (i >= 0) sum += (u[i--] - '0');
        if (j >= 0) sum += (v[j--] - '0');
        tmp = sum / 10;
        s.push_back((sum % 10) + '0');
    }
    reverse(s.begin(), s.end());
    return s;
}

✖️ Nhân Hai Số Lớn Khó

string nhanxau(string a, string b) {
    int n = a.size(), m = b.size();
    vector<int> res(n + m, 0);
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    string s = "";
    for (int x : res) if (!(s.empty() && x == 0)) s += to_string(x);
    return s.empty() ? "0" : s;
}

➖ Trừ Hai Số Lớn Trung bình

// Giả sử u >= v
string truxau(string u, string v) {
    string s = ""; int tmp = 0;
    int i = u.size() - 1, j = v.size() - 1;
    while (i >= 0) {
        int sub = (u[i--] - '0') - tmp;
        if (j >= 0) sub -= (v[j--] - '0');
        if (sub < 0) { sub += 10; tmp = 1; }
        else tmp = 0;
        s.push_back(sub + '0');
    }
    while (s.size() > 1 && s.back() == '0') s.pop_back();
    reverse(s.begin(), s.end());
    return s;
}

➗ Chia Số Lớn Cho Số Nhỏ Trung bình

// Chia số lớn u cho số nhỏ k, trả về (thương, dư)
pair<string,int> chiaxau(string u, int k) {
    string thuong = ""; int du = 0;
    for (char c : u) {
        int cur = du * 10 + (c - '0');
        thuong += (cur / k) + '0';
        du = cur % k;
    }
    // Xóa số 0 đầu
    int i = 0;
    while (i < thuong.size() - 1 && thuong[i] == '0') i++;
    return {thuong.substr(i), du};
}

➗ Tổng Phân Số Dễ

$$\frac{x_1}{y_1} + \frac{x_2}{y_2} = \frac{x_1 y_2 + x_2 y_1}{y_1 y_2}$$

int64_t tu = x1 * y2 + x2 * y1;
int64_t mau = y1 * y2;
int64_t g = gcd(abs(tu), mau);
cout << tu/g << " " << mau/g;

🔗 GCD / LCM Dễ

// Đệ quy
int64_t gcd(int64_t a, int64_t b) {
    return b ? gcd(b, a % b) : a;
}
// Vòng lặp
int64_t gcd2(int64_t a, int64_t b) {
    while (b) { int64_t t = a % b; a = b; b = t; }
    return a;
}
// LCM (tránh tràn)
int64_t lcm(int64_t a, int64_t b) {
    return a / gcd(a, b) * b;
}

Độ phức tạp: $O(\log \min(a,b))$

↩️ Extended Euclid Trung bình

Giải $ax + by = \gcd(a, b)$.

int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int64_t x1, y1;
    int64_t g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

🎯 Số Nguyên Tố Dễ

bool isPrime(int64_t n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int64_t i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

Độ phức tạp: $O(\sqrt{n})$

🌾 Sàng Eratosthenes Dễ

const int N = 1e7 + 5;
vector<bool> isPrime(N, true);
void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < N; i++)
        if (isPrime[i])
            for (int j = i * i; j < N; j += i)
                isPrime[j] = false;
}

Độ phức tạp: $O(n \log \log n)$

🌾 Sàng Đoạn (Segmented Sieve) Khó

Đếm số nguyên tố trong đoạn $[L, R]$ với $R$ rất lớn nhưng $R - L$ nhỏ.

vector<int> segSieve(int64_t L, int64_t R) {
    int64_t lim = sqrt(R);
    vector<bool> mark(lim + 1, false);
    vector<int> primes;
    for (int64_t i = 2; i <= lim; i++) {
        if (!mark[i]) {
            primes.push_back(i);
            for (int64_t j = i * i; j <= lim; j += i) mark[j] = true;
        }
    }
    vector<bool> isPrime(R - L + 1, true);
    for (int p : primes)
        for (int64_t j = max((int64_t)p*p, (L + p - 1) / p * p); j <= R; j += p)
            isPrime[j - L] = false;
    if (L == 1) isPrime[0] = false;
    vector<int> res;
    for (int64_t i = L; i <= R; i++) if (isPrime[i - L]) res.push_back(i);
    return res;
}

🔬 Miller-Rabin Khó

Kiểm tra số nguyên tố xác suất cho số cực lớn (10^18).

int64_t mulmod(int64_t a, int64_t b, int64_t m) {
    return (__int128)a * b % m;
}
int64_t powmod(int64_t a, int64_t b, int64_t m) {
    int64_t r = 1; a %= m;
    while (b) { if (b&1) r = mulmod(r,a,m); a = mulmod(a,a,m); b >>= 1; }
    return r;
}
bool miller(int64_t n) {
    if (n < 2) return false;
    for (int64_t p : {2,3,5,7,11,13,17,19,23,29,31,37}) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    int64_t d = n - 1, s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    for (int64_t a : {2,3,5,7,11,13,17,19,23,29,31,37}) {
        int64_t x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool ok = false;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { ok = true; break; }
        }
        if (!ok) return false;
    }
    return true;
}

💥 Pollard's Rho Khó

Phân tích số lớn (~10^18) thành thừa số nguyên tố.

int64_t f(int64_t x, int64_t c, int64_t m) {
    return (mulmod(x, x, m) + c) % m;
}
int64_t pollard(int64_t n) {
    if (n % 2 == 0) return 2;
    int64_t x = rand() % (n - 2) + 2, y = x, c = rand() % (n-1) + 1, d = 1;
    while (d == 1) {
        x = f(x, c, n);
        y = f(f(y, c, n), c, n);
        d = gcd(abs(x - y), n);
    }
    return d;
}

⚡ Lũy Thừa Nhanh Trung bình

// a^n
int64_t power(int64_t a, int64_t n) {
    int64_t r = 1;
    while (n) { if (n&1) r *= a; a *= a; n >>= 1; }
    return r;
}
// a^n mod m
int64_t powerMod(int64_t a, int64_t n, int64_t m) {
    int64_t r = 1; a %= m;
    while (n) {
        if (n & 1) r = (__int128)r * a % m;
        a = (__int128)a * a % m;
        n >>= 1;
    }
    return r;
}

🧮 Số Học Modulo Dễ

(a + b) % m = ((a % m) + (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m
(a * b) % m = ((a % m) * (b % m)) % m

↩️ Nghịch Đảo Modulo Trung bình

Fermat (m nguyên tố)

int64_t inv(int64_t a, int64_t m) {
    return powerMod(a, m - 2, m);
}

Euclid mở rộng

int64_t inv2(int64_t a, int64_t m) {
    int64_t x, y;
    extgcd(a, m, x, y);
    return (x % m + m) % m;
}

Tính nghịch đảo 1..n trong O(n)

vector<int64_t> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (m - m/i) * inv[m % i] % m;

φ Hàm Phi Euler Trung bình

φ(n) = số nguyên tố cùng nhau với n trong [1, n].

// Tính 1 số
int64_t phi(int64_t n) {
    int64_t r = n;
    for (int64_t i = 2; i * i <= n; i++)
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            r -= r / i;
        }
    if (n > 1) r -= r / n;
    return r;
}
// Sàng phi 1..n
vector<int> phiSieve(int n) {
    vector<int> phi(n + 1);
    for (int i = 0; i <= n; i++) phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (phi[i] == i)
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
    return phi;
}

μ Hàm Mobius Khó

μ(n) = 0 nếu n có thừa số chính phương, ngược lại là (-1)^(số thừa số).

vector<int> mobiusSieve(int n) {
    vector<int> mu(n + 1, 1), isPrime(n + 1, 1);
    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if (i * p > n) break;
            isPrime[i * p] = 0;
            if (i % p == 0) { mu[i * p] = 0; break; }
            else mu[i * p] = -mu[i];
        }
    }
    return mu;
}

🇨🇳 Định Lý CRT Khó

Giải hệ $x \equiv a_i \pmod{m_i}$ với $m_i$ đôi một nguyên tố cùng nhau.

int64_t crt(vector<int64_t>& a, vector<int64_t>& m) {
    int64_t M = 1;
    for (int64_t x : m) M *= x;
    int64_t res = 0;
    for (int i = 0; i < a.size(); i++) {
        int64_t Mi = M / m[i];
        int64_t x, y;
        extgcd(Mi, m[i], x, y);
        res = (res + a[i] * Mi % M * x) % M;
    }
    return (res % M + M) % M;
}

📐 Phương Trình Diophantus Khó

Giải $ax + by = c$ với $x, y$ nguyên.

bool diophantine(int64_t a, int64_t b, int64_t c, int64_t &x, int64_t &y) {
    int64_t g = extgcd(a, b, x, y);
    if (c % g != 0) return false;
    x *= c / g; y *= c / g;
    return true;
}

📈 Cấp Số Cộng Dễ

$$a_n = a_1 + (n-1)d$$

$$S_n = \frac{n(a_1 + a_n)}{2} = \frac{n(2a_1 + (n-1)d)}{2}$$

📉 Cấp Số Nhân Dễ

$$a_n = a_1 q^{n-1}$$

$$S_n = a_1 \frac{q^n - 1}{q - 1} \quad (q \neq 1)$$

$$S_\infty = \frac{a_1}{1 - q} \quad (|q| < 1)$$

🌀 Fibonacci Trung bình

$$F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2}$$

O(n)

int64_t fib(int n) {
    if (n <= 1) return n;
    int64_t a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int64_t c = a + b; a = b; b = c; }
    return b;
}

Ma trận O(log n)

struct Mat {
    int64_t a[2][2];
    Mat operator*(Mat b) {
        Mat c;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++) {
                c.a[i][j] = 0;
                for (int k = 0; k < 2; k++)
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
            }
        return c;
    }
};
int64_t fibFast(int64_t n) {
    Mat res = {{{1,0},{0,1}}}, base = {{{1,1},{1,0}}};
    while (n) {
        if (n & 1) res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res.a[0][1];
}

Binet

$$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

🔄 Tổ Hợp - Chỉnh Hợp Trung bình

• $P(n) = n!$
• $A(n,k) = n!/(n-k)!$
• $C(n,k) = n!/(k!(n-k)!)$
• Pascal: $C(n,k) = C(n-1,k-1) + C(n-1,k)$

Tổ hợp mod p (p nguyên tố)

const int MOD = 1e9 + 7, N = 1e6 + 5;
int64_t fact[N], inv_fact[N];
int64_t pm(int64_t a, int64_t b) {
    int64_t r = 1; a %= MOD;
    while (b) { if (b&1) r = r*a%MOD; a = a*a%MOD; b >>= 1; }
    return r;
}
void prepare() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i-1]*i%MOD;
    inv_fact[N-1] = pm(fact[N-1], MOD-2);
    for (int i = N-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1]*(i+1)%MOD;
}
int64_t C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;
}

Lucas cho p nhỏ

int64_t lucas(int64_t n, int64_t k, int64_t p) {
    if (k == 0) return 1;
    return C(n % p, k % p, p) * lucas(n / p, k / p, p) % p;
}

🐱 Số Catalan Trung bình

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

int64_t catalan(int n) {
    return C(2*n, n) * pm(n+1, MOD-2) % MOD;
}

⭐ Số Stirling Khó

Loại 2: S(n,k) = số cách chia n phần tử vào k tập khác rỗng

$$S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$$

vector<vector<int64_t>> S(n+1, vector<int64_t>(k+1, 0));
S[0][0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= min(i, k); j++)
        S[i][j] = (S[i-1][j-1] + j * S[i-1][j]) % MOD;

🎩 Số Bernoulli Khó

Dùng để tính tổng $1^k + 2^k + ... + n^k$.

$$\sum_{i=1}^{n} i^k = \frac{1}{k+1} \sum_{j=0}^{k} \binom{k+1}{j} B_j n^{k+1-j}$$

🎮 Lý Thuyết Trò Chơi Khó

• Thắng (N): Tồn tại nước đi tới P.
• Thua (P): Mọi nước đi đều tới N.

Ví dụ: Subtration game

// Lấy 1..k viên đá, ai lấy cuối thắng
// Thua khi n % (k+1) == 0
bool win(int n, int k) {
    return n % (k + 1) != 0;
}

🎯 Nim Game Trung bình

Nim 1 đống: Thua khi n = 0.

Nim nhiều đống: XOR tất cả → khác 0 thì người đi trước thắng.

int xorSum = 0;
for (int x : piles) xorSum ^= x;
if (xorSum != 0) cout << "First"; else cout << "Second";

🌳 Sprague-Grundy Khó

Grundy(x) = mex của {Grundy(y) : y là trạng thái chuyển từ x}.

int grundy(int x, vector<int>& moves) {
    set<int> s;
    for (int m : moves) if (x >= m) s.insert(grundy(x - m, moves));
    int g = 0;
    while (s.count(g)) g++;
    return g;
}

Trò chơi tổng = XOR của Grundy các thành phần.

📐 Diện Tích Tam Giác Dễ

$$S = |(x_2-x_1)(y_3-y_1) - (x_3-x_1)(y_2-y_1)|$$

struct pt { int64_t x, y; };
int64_t cross(pt O, pt A, pt B) {
    return (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x);
}
int64_t area(pt A, pt B, pt C) {
    return abs(cross(A, B, C));
}
bool inTriangle(pt A, pt B, pt C, pt M) {
    return area(A,B,M) + area(A,M,C) + area(M,B,C) == area(A,B,C);
}

🔺 Định Lý Pythagoras Dễ

$$a^2 + b^2 = c^2$$

Bộ 3 Pythagoras: $(3,4,5), (5,12,13), (8,15,17), (7,24,25)$...

📏 Định Lý Sin / Cosin Trung bình

Cosin: $c^2 = a^2 + b^2 - 2ab\cos C$

Sin: $\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2R$

Heron: $S = \sqrt{p(p-a)(p-b)(p-c)}$

📏 Đường Thẳng Trung bình

$Ax + By + C = 0$ với $A = y_2-y_1$, $B = x_1-x_2$, $C = -Ax_1-By_1$.

Khoảng cách điểm $(x_0,y_0)$:

$$d = \frac{|Ax_0 + By_0 + C|}{\sqrt{A^2 + B^2}}$$

Giao 2 đường thẳng

double D  = A1*B2 - A2*B1;
double Dx = C1*B2 - C2*B1;
double Dy = A1*C2 - A2*C1;
if (fabs(D) > 1e-9) { x = Dx/D; y = Dy/D; }

⭕ Đường Tròn Trung bình

Phương trình

$(x-a)^2 + (y-b)^2 = R^2$

Tương giao 2 đường tròn

double d = hypot(a2-a1, b2-b1);
if (d > r1 + r2 || d < fabs(r1 - r2)) return {}; // Không cắt
double a = (r1*r1 - r2*r2 + d*d) / (2*d);
double h = sqrt(r1*r1 - a*a);
double xm = a1 + a*(a2-a1)/d, ym = b1 + a*(b2-b1)/d;
// 2 giao điểm
double x1 = xm + h*(b2-b1)/d, y1 = ym - h*(a2-a1)/d;
double x2 = xm - h*(b2-b1)/d, y2 = ym + h*(a2-a1)/d;

🔷 Điểm Trong Đa Giác Khó

Thuật toán Ray Casting — đếm số lần tia ngang cắt cạnh.

bool inPolygon(vector<pt>& poly, pt p) {
    int n = poly.size(), cnt = 0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        if ((poly[i].y > p.y) != (poly[j].y > p.y)) {
            double xInt = (poly[j].x - poly[i].x) * (p.y - poly[i].y)
                        / (poly[j].y - poly[i].y) + poly[i].x;
            if (p.x < xInt) cnt++;
        }
    }
    return cnt % 2 == 1;
}

📐 Diện Tích Đa Giác Trung bình

Công thức Shoelace:

$$S = \frac{1}{2}\left|\sum_{i=1}^{n}(x_i y_{i+1} - x_{i+1} y_i)\right|$$

int64_t polygonArea(vector<pt>& p) {
    int64_t s = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        s += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return abs(s);
}

🏔️ Convex Hull (Andrew) Khó

vector<pt> convexHull(vector<pt> p) {
    sort(p.begin(), p.end(), [](pt a, pt b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    vector<pt> h;
    for (auto &q : p) {
        while (h.size() >= 2 && cross(h[h.size()-2], h.back(), q) <= 0)
            h.pop_back();
        h.push_back(q);
    }
    int sz = h.size();
    for (int i = p.size() - 2; i >= 0; i--) {
        while (h.size() > sz && cross(h[h.size()-2], h.back(), p[i]) <= 0)
            h.pop_back();
        h.push_back(p[i]);
    }
    h.pop_back();
    return h;
}

📏 Rotating Calipers Khó

Đường kính bao lồi (2 điểm xa nhất).

int64_t diameter(vector<pt>& h) {
    int n = h.size();
    int j = 1;
    int64_t best = 0;
    for (int i = 0; i < n; i++) {
        while (abs(cross(h[i], h[(i+1)%n], h[(j+1)%n])) >
               abs(cross(h[i], h[(i+1)%n], h[j])))
            j = (j + 1) % n;
        best = max(best, max(dist(h[i], h[j]),
                             dist(h[(i+1)%n], h[j])));
    }
    return best;
}

👥 Cặp Điểm Gần Nhất Khó

Chia để trị O(n log n).

double closest(vector<pt>& p) {
    sort(p.begin(), p.end(), [](pt a, pt b) { return a.x < b.x; });
    set<pair<double,double>> s;
    double best = 1e18;
    int j = 0;
    for (auto &q : p) {
        while (j < p.size() && q.x - p[j].x > best)
            s.erase({p[j].y, p[j].x}), j++;
        auto lo = s.lower_bound({q.y - best, -1e18});
        auto hi = s.upper_bound({q.y + best, 1e18});
        for (auto it = lo; it != hi; it++)
            best = min(best, hypot(q.x - it->second, q.y - it->first));
        s.insert({q.y, q.x});
    }
    return best;
}

✂️ Giao Hai Đoạn Thẳng Khó

int sign(int64_t x) { return (x > 0) - (x < 0); }
bool intersect(pt a, pt b, pt c, pt d) {
    int64_t d1 = cross(a, b, c), d2 = cross(a, b, d);
    int64_t d3 = cross(c, d, a), d4 = cross(c, d, b);
    if (sign(d1) * sign(d2) < 0 && sign(d3) * sign(d4) < 0) return true;
    // Xử lý collinear nếu cần
    return false;
}

🔀 Sắp Xếp Trung bình

Bubble — O(n²)

for (int i = 0; i < n-1; i++)
    for (int j = 0; j < n-i-1; j++)
        if (a[j] > a[j+1]) swap(a[j], a[j+1]);

Insertion — O(n²)

for (int i = 1; i < n; i++) {
    int k = a[i], j = i-1;
    while (j >= 0 && a[j] > k) { a[j+1] = a[j]; j--; }
    a[j+1] = k;
}

Quick Sort — O(n log n)

int part(vector<int>& a, int lo, int hi) {
    int p = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] <= p) swap(a[++i], a[j]);
    swap(a[i+1], a[hi]);
    return i+1;
}
void quickSort(vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int p = part(a, lo, hi);
        quickSort(a, lo, p-1);
        quickSort(a, p+1, hi);
    }
}

Merge Sort — O(n log n)

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> L(a.begin()+l, a.begin()+m+1);
    vector<int> R(a.begin()+m+1, a.begin()+r+1);
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size())
        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < L.size()) a[k++] = L[i++];
    while (j < R.size()) a[k++] = R[j++];
}
void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m+1, r);
    merge(a, l, m, r);
}

🔢 Counting Sort Dễ

O(n + k) với k = giá trị max. Chỉ dùng khi giá trị nhỏ.

void countingSort(vector<int>& a) {
    int mx = *max_element(a.begin(), a.end());
    vector<int> cnt(mx + 1, 0);
    for (int x : a) cnt[x]++;
    int idx = 0;
    for (int i = 0; i <= mx; i++)
        while (cnt[i]--) a[idx++] = i;
}

🔢 Radix Sort Khó

O(d × (n + b)) với d = số chữ số, b = base.

void countingSortDigit(vector<int>& a, int exp) {
    int n = a.size();
    vector<int> out(n), cnt(10, 0);
    for (int x : a) cnt[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) cnt[i] += cnt[i-1];
    for (int i = n-1; i >= 0; i--) {
        int d = (a[i] / exp) % 10;
        out[--cnt[d]] = a[i];
    }
    a = out;
}
void radixSort(vector<int>& a) {
    int mx = *max_element(a.begin(), a.end());
    for (int exp = 1; mx / exp > 0; exp *= 10)
        countingSortDigit(a, exp);
}

🏔️ Heap Sort Trung bình

void heapify(vector<int>& a, int n, int i) {
    int mx = i, l = 2*i+1, r = 2*i+2;
    if (l < n && a[l] > a[mx]) mx = l;
    if (r < n && a[r] > a[mx]) mx = r;
    if (mx != i) { swap(a[i], a[mx]); heapify(a, n, mx); }
}
void heapSort(vector<int>& a) {
    int n = a.size();
    for (int i = n/2-1; i >= 0; i--) heapify(a, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

🐚 Shell Sort Trung bình

void shellSort(vector<int>& a) {
    int n = a.size();
    for (int g = n/2; g > 0; g /= 2)
        for (int i = g; i < n; i++) {
            int t = a[i], j;
            for (j = i; j >= g && a[j-g] > t; j -= g)
                a[j] = a[j-g];
            a[j] = t;
        }
}

🎯 Selection Sort Dễ

for (int i = 0; i < n-1; i++) {
    int mn = i;
    for (int j = i+1; j < n; j++)
        if (a[j] < a[mn]) mn = j;
    swap(a[i], a[mn]);
}

🎯 Binary Search Trung bình

int bs(vector<int>& a, int x) {
    int lo = 0, hi = a.size()-1;
    while (lo <= hi) {
        int mid = lo + (hi-lo)/2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid+1;
        else hi = mid-1;
    }
    return -1;
}
// Dùng STL
lower_bound(a.begin(), a.end(), x);   // >= x
upper_bound(a.begin(), a.end(), x);   // > x

🎯 Binary Search on Answer Khó

int64_t lo = 1, hi = 1e18, ans = -1;
while (lo <= hi) {
    int64_t mid = lo + (hi - lo) / 2;
    if (check(mid)) { ans = mid; hi = mid - 1; } // Min
    else lo = mid + 1;
}
// Max: ans = mid; lo = mid + 1;

🔺 Ternary Search Khó

double ts(double l, double r) {
    for (int i = 0; i < 200; i++) {
        double m1 = l + (r-l)/3, m2 = r - (r-l)/3;
        if (f(m1) < f(m2)) l = m1; else r = m2;
    }
    return f(l);
}
// Số nguyên
int64_t tsInt(int64_t l, int64_t r) {
    while (r - l > 2) {
        int64_t m1 = l + (r-l)/3, m2 = r - (r-l)/3;
        if (f(m1) < f(m2)) l = m1; else r = m2;
    }
    int64_t res = LLONG_MIN;
    for (int64_t i = l; i <= r; i++) res = max(res, f(i));
    return res;
}

👥 Two Pointers Trung bình

// Đếm cặp có tổng = S (mảng sort)
int l = 0, r = n-1, cnt = 0;
while (l < r) {
    int s = a[l] + a[r];
    if (s == S) { cnt++; l++; r--; }
    else if (s < S) l++;
    else r--;
}

➕ Prefix Sum Dễ

vector<int64_t> pre(n+1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];
int64_t s = pre[r] - pre[l-1];

2D

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
int64_t s = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];

🪟 Sliding Window Trung bình

int64_t sum = 0, best;
for (int i = 0; i < k; i++) sum += a[i];
best = sum;
for (int i = k; i < n; i++) {
    sum += a[i] - a[i-k];
    best = max(best, sum);
}

📦 Nén Tọa Độ Trung bình

vector<int> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (int &x : a)
    x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;

📊 Mảng Hiệu (Difference Array) Trung bình

Cập nhật đoạn [l, r] += v trong O(1).

vector<int64_t> d(n + 2, 0);
// Cập nhật
d[l] += v; d[r+1] -= v;
// Truy vấn giá trị tại i
int64_t cur = 0;
for (int i = 1; i <= n; i++) {
    cur += d[i];
    a[i] = cur;
}

🎪 Mo's Algorithm Khó

Trả lời Q truy vấn đoạn ngoại tuyến trong $O((n+q)\sqrt{n})$.

int block;
struct Query {
    int l, r, idx;
    bool operator<(Query o) {
        if (l / block != o.l / block) return l / block < o.l / block;
        return ((l / block) & 1) ? r > o.r : r < o.r;
    }
};
// main
block = sqrt(n);
vector<Query> qs(q);
// ...
sort(qs.begin(), qs.end());
int cl = 0, cr = -1, curAns = 0;
for (auto &q : qs) {
    while (cl > q.l) add(--cl);
    while (cr < q.r) add(++cr);
    while (cl < q.l) remove(cl++);
    while (cr > q.r) remove(cr--);
    res[q.idx] = curAns;
}

📚 Stack / Queue / Deque Dễ

stack<int> st;
queue<int> q;
deque<int> dq;

st.push(1); st.top(); st.pop();
q.push(1); q.front(); q.pop();
dq.push_front(1); dq.push_back(2); dq.pop_front(); dq.pop_back();

📉 Monotonic Stack Khó

Phần tử lớn hơn kế tiếp (Next Greater Element).

vector<int> nge(n, -1);
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] < a[i]) {
        nge[st.top()] = a[i];
        st.pop();
    }
    st.push(i);
}

🏔️ Heap / Priority Queue Trung bình

priority_queue<int> maxpq;
priority_queue<int, vector<int>, greater<int>> minpq;

// Custom
struct cmp {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return a.first > b.first; // Min by first
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;

🔗 DSU (Union-Find) Trung bình

vector<int> par, sz;
void init(int n) {
    par.resize(n + 1); sz.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}
bool unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u; sz[u] += sz[v];
    return true;
}

🔄 DSU Rollback Khó

stack<pair<int,int>> hist;
vector<int> par, sz;
void init(int n) {
    par.resize(n+1); sz.assign(n+1, 1);
    for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int u) {  // Không nén đường
    while (par[u] != u) u = par[u];
    return u;
}
void unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) { hist.push({-1, -1}); return; }
    if (sz[u] < sz[v]) swap(u, v);
    hist.push({u, v});
    par[v] = u; sz[u] += sz[v];
}
void rollback() {
    auto [u, v] = hist.top(); hist.pop();
    if (u == -1) return;
    par[v] = v; sz[u] -= sz[v];
}

🌲 Segment Tree Khó

const int N = 1e5 + 5;
int64_t tree[4*N], a[N];

void build(int node, int l, int r) {
    if (l == r) { tree[node] = a[l]; return; }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = tree[2*node] + tree[2*node+1];
}
void update(int node, int l, int r, int i, int64_t v) {
    if (l == r) { tree[node] = v; return; }
    int mid = (l+r)/2;
    if (i <= mid) update(2*node, l, mid, i, v);
    else update(2*node+1, mid+1, r, i, v);
    tree[node] = tree[2*node] + tree[2*node+1];
}
int64_t query(int node, int l, int r, int u, int v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[node];
    int mid = (l+r)/2;
    return query(2*node, l, mid, u, v) + query(2*node+1, mid+1, r, u, v);
}

💤 Lazy Propagation Khó

int64_t tree[4*N], lazy[4*N];

void push(int node, int l, int r) {
    if (lazy[node]) {
        tree[node] += lazy[node] * (r - l + 1);
        if (l != r) {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
void update(int node, int l, int r, int u, int v, int64_t val) {
    push(node, l, r);
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        tree[node] += val * (r - l + 1);
        if (l != r) {
            lazy[2*node] += val;
            lazy[2*node+1] += val;
        }
        return;
    }
    int mid = (l+r)/2;
    update(2*node, l, mid, u, v, val);
    update(2*node+1, mid+1, r, u, v, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}
int64_t query(int node, int l, int r, int u, int v) {
    push(node, l, r);
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[node];
    int mid = (l+r)/2;
    return query(2*node, l, mid, u, v) + query(2*node+1, mid+1, r, u, v);
}

📚 Persistent Segment Tree Khó

struct Node {
    int64_t val;
    int left, right;
};
vector<Node> tree;
vector<int> roots;

int build(int l, int r) {
    int id = tree.size();
    tree.push_back({0, 0, 0});
    if (l == r) return id;
    int mid = (l+r)/2;
    tree[id].left = build(l, mid);
    tree[id].right = build(mid+1, r);
    return id;
}
int update(int prev, int l, int r, int pos, int64_t val) {
    int id = tree.size();
    tree.push_back(tree[prev]);
    if (l == r) { tree[id].val += val; return id; }
    int mid = (l+r)/2;
    if (pos <= mid) tree[id].left = update(tree[prev].left, l, mid, pos, val);
    else tree[id].right = update(tree[prev].right, mid+1, r, pos, val);
    tree[id].val = tree[tree[id].left].val + tree[tree[id].right].val;
    return id;
}

🔢 Fenwick Tree (BIT) Khó

int64_t bit[N];
int n;
void update(int i, int64_t v) {
    for (; i <= n; i += i & -i) bit[i] += v;
}
int64_t query(int i) {
    int64_t s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}
int64_t range(int l, int r) { return query(r) - query(l-1); }

🔢 BIT 2 Chiều Khó

int64_t bit[N][N];
int n, m;
void update(int x, int y, int64_t v) {
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= m; j += j & -j)
            bit[i][j] += v;
}
int64_t query(int x, int y) {
    int64_t s = 0;
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            s += bit[i][j];
    return s;
}

📊 Sparse Table Khó

const int LOG = 17, N = 1e5 + 5;
int64_t st[LOG][N];
int lg[N];
void build(vector<int64_t>& a, int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int i = 0; i < n; i++) st[0][i] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}
int64_t query(int l, int r) {
    int j = lg[r - l + 1];
    return min(st[j][l], st[j][r - (1 << j) + 1]);
}

🌳 Trie Khó

struct Trie {
    struct Node {
        int child[26], cnt, end;
        Node() { fill(child, child+26, -1); cnt = end = 0; }
    };
    vector<Node> t;
    Trie() { t.push_back(Node()); }
    void insert(string s) {
        int cur = 0;
        for (char c : s) {
            int i = c - 'a';
            if (t[cur].child[i] == -1) {
                t[cur].child[i] = t.size();
                t.push_back(Node());
            }
            cur = t[cur].child[i];
            t[cur].cnt++;
        }
        t[cur].end++;
    }
    bool search(string s) {
        int cur = 0;
        for (char c : s) {
            int i = c - 'a';
            if (t[cur].child[i] == -1) return false;
            cur = t[cur].child[i];
        }
        return t[cur].end > 0;
    }
    int countPrefix(string s) {
        int cur = 0;
        for (char c : s) {
            int i = c - 'a';
            if (t[cur].child[i] == -1) return 0;
            cur = t[cur].child[i];
        }
        return t[cur].cnt;
    }
};

🌲 Treap Khó

struct Treap {
    struct Node {
        int val, prio, sz;
        Node *l, *r;
        Node(int v) : val(v), prio(rand()), sz(1), l(0), r(0) {}
    };
    Node* root = 0;
    int sz(Node* t) { return t ? t->sz : 0; }
    void upd(Node* t) { if (t) t->sz = 1 + sz(t->l) + sz(t->r); }
    void split(Node* t, int key, Node*& a, Node*& b) {
        if (!t) return void(a = b = 0);
        if (t->val <= key) { split(t->r, key, t->r, b); a = t; }
        else { split(t->l, key, a, t->l); b = t; }
        upd(t);
    }
    void merge(Node*& t, Node* a, Node* b) {
        if (!a || !b) return void(t = a ? a : b);
        if (a->prio > b->prio) { merge(a->r, a->r, b); t = a; }
        else { merge(b->l, a, b->l); t = b; }
        upd(t);
    }
};

📦 Sqrt Decomposition Khó

int n, B;
vector<int64_t> a, block;
void build() {
    B = sqrt(n) + 1;
    block.assign(B, 0);
    for (int i = 0; i < n; i++) block[i/B] += a[i];
}
void update(int i, int64_t v) {
    block[i/B] += v - a[i];
    a[i] = v;
}
int64_t query(int l, int r) {
    int64_t s = 0;
    for (int i = l; i <= r; ) {
        if (i % B == 0 && i + B - 1 <= r) {
            s += block[i/B];
            i += B;
        } else {
            s += a[i++];
        }
    }
    return s;
}

🌊 Wavelet Tree Khó

Truy vấn phần tử nhỏ thứ k trong đoạn [l, r] trong O(log n).

struct Wavelet {
    struct Node {
        vector<int> pre;
        Node *l = 0, *r = 0;
    };
    Node* root;
    int lo, hi;
    Wavelet(vector<int>& a, int lo, int hi) : lo(lo), hi(hi) {
        root = build(a, lo, hi);
    }
    Node* build(vector<int>& a, int lo, int hi) {
        Node* t = new Node();
        t->pre.resize(a.size() + 1, 0);
        if (lo == hi) return t;
        int mid = (lo + hi) / 2;
        vector<int> L, R;
        for (int i = 0; i < a.size(); i++) {
            t->pre[i+1] = t->pre[i] + (a[i] <= mid);
            if (a[i] <= mid) L.push_back(a[i]); else R.push_back(a[i]);
        }
        if (!L.empty()) t->l = build(L, lo, mid);
        if (!R.empty()) t->r = build(R, mid+1, hi);
        return t;
    }
    int kth(Node* t, int l, int r, int k, int lo, int hi) {
        if (lo == hi) return lo;
        int mid = (lo + hi) / 2;
        int cntL = t->pre[r] - t->pre[l-1];
        if (k <= cntL) return kth(t->l, t->pre[l-1]+1, t->pre[r], k, lo, mid);
        return kth(t->r, l - t->pre[l-1], r - t->pre[r], k - cntL, mid+1, hi);
    }
};

📊 Ordered Set (PBDS) Khó

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
                         tree_order_statistics_node_update>;

ordered_set<int> s;
s.insert(5);
*s.find_by_order(0);     // Phần tử nhỏ thứ 0
s.order_of_key(5);       // Số phần tử < 5

📝 Xử Lý Xâu Dễ

// Đảo
reverse(s.begin(), s.end());
// Đếm ký tự
int cnt[256] = {0};
for (char c : s) cnt[c]++;
// Tách từ
stringstream ss(s); string t;
while (ss >> t) { /* ... */ }
// Chuyển string <-> số
int x = stoi(s);
int64_t y = stoll(s);
string z = to_string(x);
// Kiểm tra palindrome
bool pal = s == string(s.rbegin(), s.rend());

🔎 KMP Khó

vector<int> prefix(string p) {
    vector<int> pi(p.size(), 0);
    for (int i = 1; i < p.size(); i++) {
        int j = pi[i-1];
        while (j > 0 && p[i] != p[j]) j = pi[j-1];
        if (p[i] == p[j]) j++;
        pi[i] = j;
    }
    return pi;
}
vector<int> kmp(string s, string p) {
    auto pi = prefix(p);
    vector<int> res;
    int j = 0;
    for (int i = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != p[j]) j = pi[j-1];
        if (s[i] == p[j]) j++;
        if (j == p.size()) {
            res.push_back(i - j + 1);
            j = pi[j-1];
        }
    }
    return res;
}

⚡ Z-Algorithm Khó

vector<int> zFunc(string s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

#️⃣ Hash Xâu Trung bình

const int64_t BASE = 311, MOD = 1e9 + 7;
vector<int64_t> pw(N), hs(N);
void prepare(string s) {
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i-1] * BASE % MOD;
    hs[0] = 0;
    for (int i = 0; i < s.size(); i++)
        hs[i+1] = (hs[i] * BASE + s[i]) % MOD;
}
int64_t getHash(int l, int r) {
    return (hs[r] - hs[l-1] * pw[r-l+1] % MOD + MOD) % MOD;
}

#️⃣ Double Hash Khó

const int64_t B1 = 311, M1 = 1e9+7, B2 = 313, M2 = 1e9+9;
vector<int64_t> pw1, pw2, h1, h2;
pair<int64_t,int64_t> getHash(int l, int r) {
    int64_t x = (h1[r] - h1[l-1] * pw1[r-l+1] % M1 + M1) % M1;
    int64_t y = (h2[r] - h2[l-1] * pw2[r-l+1] % M2 + M2) % M2;
    return {x, y};
}

🪞 Manacher Khó

vector<int> manacher(string s) {
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();
    vector<int> p(n, 0);
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        p[i] = (i < r) ? min(r - i, p[l + r - i]) : 0;
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; }
    }
    return p;
}
// Độ dài palindrome dài nhất = max(p)

🎯 Aho-Corasick Khó

Tìm nhiều xâu mẫu trong text cùng lúc.

struct Aho {
    struct Node {
        int child[26], fail, out;
        Node() { fill(child, child+26, -1); fail = out = 0; }
    };
    vector<Node> t;
    Aho() { t.push_back(Node()); }
    void insert(string s) {
        int cur = 0;
        for (char c : s) {
            int i = c - 'a';
            if (t[cur].child[i] == -1) {
                t[cur].child[i] = t.size();
                t.push_back(Node());
            }
            cur = t[cur].child[i];
        }
        t[cur].out++;
    }
    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++)
            if (t[0].child[i] != -1) q.push(t[0].child[i]);
            else t[0].child[i] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            t[u].out += t[t[u].fail].out;
            for (int i = 0; i < 26; i++) {
                if (t[u].child[i] != -1) {
                    int v = t[u].child[i];
                    t[v].fail = t[t[u].fail].child[i];
                    q.push(v);
                } else {
                    t[u].child[i] = t[t[u].fail].child[i];
                }
            }
        }
    }
    int query(string s) {
        int cur = 0, res = 0;
        for (char c : s) {
            cur = t[cur].child[c - 'a'];
            res += t[cur].out;
        }
        return res;
    }
};

📚 Suffix Array Khó

vector<int> suffixArray(string s) {
    s += '$';
    int n = s.size();
    vector<int> sa(n), c(n);
    // Initial sort by first char
    vector<int> cnt(max(256, n), 0);
    for (char ch : s) cnt[(int)ch]++;
    for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++) sa[--cnt[(int)s[i]]] = i;
    c[sa[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[sa[i]] != s[sa[i-1]]) classes++;
        c[sa[i]] = classes - 1;
    }
    // Iterate
    vector<int> sa2(n), c2(n);
    for (int k = 0; (1 << k) < n; k++) {
        for (int i = 0; i < n; i++) {
            sa2[i] = sa[i] - (1 << k);
            if (sa2[i] < 0) sa2[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int x : sa2) cnt[c[x]]++;
        for (int i = 1; i < classes; i++) cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--) sa[--cnt[c[sa2[i]]]] = sa2[i];
        c2[sa[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int,int> cur = {c[sa[i]], c[(sa[i] + (1 << k)) % n]};
            pair<int,int> prv = {c[sa[i-1]], c[(sa[i-1] + (1 << k)) % n]};
            if (cur != prv) classes++;
            c2[sa[i]] = classes - 1;
        }
        c = c2;
    }
    sa.erase(sa.begin());
    return sa;
}

📏 LCP Array Khó

Longest Common Prefix giữa các suffix liền kề trong Suffix Array.

vector<int> kasai(string s, vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n), lcp(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == n-1) { k = 0; continue; }
        int j = sa[rank[i]+1];
        while (i+k < n && j+k < n && s[i+k] == s[j+k]) k++;
        lcp[rank[i]] = k;
        if (k) k--;
    }
    return lcp;
}

📊 Biểu Diễn Đồ Thị Dễ

// Danh sách kề
vector<vector<int>> adj(n + 1);
adj[u].push_back(v);

// Có trọng số
vector<vector<pair<int,int>>> adj(n + 1);
adj[u].push_back({v, w});

// Ma trận kề
int g[N][N];

🌊 BFS / DFS Trung bình

void bfs(int s, int n) {
    vector<int> dist(n+1, -1);
    queue<int> q;
    q.push(s); dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
    }
}
void dfs(int u, vector<bool>& vis) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v, vis);
}

🌊 Multi-source BFS Trung bình

vector<int> dist(n+1, -1);
queue<int> q;
for (int s : sources) {
    dist[s] = 0;
    q.push(s);
}
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u])
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
}

🔢 0-1 BFS Khó

Cạnh có trọng số 0 hoặc 1 — dùng deque.

vector<int> dist(n+1, INT_MAX);
deque<int> dq;
dist[s] = 0;
dq.push_front(s);
while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (w == 0) dq.push_front(v);
            else dq.push_back(v);
        }
    }
}

📋 Topological Sort Trung bình

// Kahn's algorithm (BFS)
vector<int> indeg(n+1, 0);
for (int u = 1; u <= n; u++)
    for (int v : adj[u]) indeg[v]++;
queue<int> q;
for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);
vector<int> topo;
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : adj[u])
        if (--indeg[v] == 0) q.push(v);
}
// Nếu topo.size() < n → có chu trình

🛣️ Dijkstra Khó

typedef pair<int64_t,int> pli;
vector<int64_t> dijkstra(int s, int n) {
    vector<int64_t> dist(n+1, LLONG_MAX);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

Độ phức tạp: $O((V+E)\log V)$

🔁 Bellman-Ford Khó

struct Edge { int u, v, w; };
vector<int64_t> bellman(int s, int n, vector<Edge>& e) {
    vector<int64_t> d(n+1, LLONG_MAX);
    d[s] = 0;
    for (int i = 1; i < n; i++)
        for (auto &x : e)
            if (d[x.u] != LLONG_MAX && d[x.u] + x.w < d[x.v])
                d[x.v] = d[x.u] + x.w;
    // Kiểm tra chu trình âm
    for (auto &x : e)
        if (d[x.u] != LLONG_MAX && d[x.u] + x.w < d[x.v])
            cout << "Negative cycle!";
    return d;
}

🌐 Floyd-Warshall Khó

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];

Độ phức tạp: $O(V^3)$

🌲 Minimum Spanning Tree Khó

Kruskal

struct Edge { int u, v, w; };
sort(edges.begin(), edges.end(),
     [](Edge a, Edge b) { return a.w < b.w; });
int64_t mst = 0;
for (auto &e : edges)
    if (unite(e.u, e.v)) mst += e.w;

Prim

int64_t prim(int s, int n) {
    vector<int> dist(n+1, INT_MAX);
    vector<bool> vis(n+1, false);
    dist[s] = 0;
    int64_t mst = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int v = 1; v <= n; v++)
            if (!vis[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (dist[u] == INT_MAX) break;
        vis[u] = true;
        mst += dist[u];
        for (auto [v, w] : adj[u]) dist[v] = min(dist[v], w);
    }
    return mst;
}

🔗 Thành Phần Liên Thông Mạnh Khó

Tarjan

int timer = 0, sccCnt = 0;
vector<int> num(n+1, 0), low(n+1, 0), id(n+1, -1);
stack<int> st;
vector<bool> onSt(n+1, false);

void dfs(int u) {
    num[u] = low[u] = ++timer;
    st.push(u); onSt[u] = true;
    for (int v : adj[u]) {
        if (!num[v]) { dfs(v); low[u] = min(low[u], low[v]); }
        else if (onSt[v]) low[u] = min(low[u], num[v]);
    }
    if (low[u] == num[u]) {
        int v;
        do {
            v = st.top(); st.pop();
            onSt[v] = false;
            id[v] = sccCnt;
        } while (v != u);
        sccCnt++;
    }
}

🌉 Cầu & Khớp Khó

int timer = 0;
vector<int> num(n+1, 0), low(n+1, 0);
vector<pair<int,int>> bridges;
vector<int> articulation;

void dfs(int u, int p) {
    num[u] = low[u] = ++timer;
    int children = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (!num[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            children++;
            if (low[v] > num[u]) bridges.push_back({u, v});
            if (p != -1 && low[v] >= num[u]) articulation.push_back(u);
        } else {
            low[u] = min(low[u], num[v]);
        }
    }
    if (p == -1 && children > 1) articulation.push_back(u);
}

🔵 Kiểm Tra Đồ Thị 2 Phía Trung bình

vector<int> color(n+1, -1);
bool ok = true;
function<void(int,int)> dfs = [&](int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) dfs(v, 1 - c);
        else if (color[v] == c) ok = false;
    }
};
for (int i = 1; i <= n; i++)
    if (color[i] == -1) dfs(i, 0);

👨‍👦 LCA — Binary Lifting Khó

const int LOG = 17;
int up[LOG][N], depth[N];
void dfs(int u, int p) {
    up[0][u] = p;
    for (int j = 1; j < LOG; j++)
        up[j][u] = up[j-1][up[j-1][u]];
    for (int v : adj[u]) if (v != p) {
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int j = 0; j < LOG; j++)
        if (diff >> j & 1) u = up[j][u];
    if (u == v) return u;
    for (int j = LOG-1; j >= 0; j--)
        if (up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; }
    return up[0][u];
}

🌳 Heavy-Light Decomposition Khó

Truy vấn đường đi trên cây O(log² n).

vector<int> par, depth, sz, heavy, head, pos;
int curPos = 0;

void dfs1(int u) {
    sz[u] = 1;
    for (int v : adj[u]) if (v != par[u]) {
        par[v] = u;
        depth[v] = depth[u] + 1;
        dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}
void dfs2(int u, int h) {
    head[u] = h;
    pos[u] = ++curPos;
    if (heavy[u]) dfs2(heavy[u], h);
    for (int v : adj[u])
        if (v != par[u] && v != heavy[u]) dfs2(v, v);
}
int64_t queryPath(int u, int v) {
    int64_t res = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        res += segQuery(pos[head[u]], pos[u]);
        u = par[head[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res += segQuery(pos[u], pos[v]);
    return res;
}

🎯 Centroid Decomposition Khó

vector<int> sz;
vector<bool> removed;

int calcSize(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u])
        if (v != p && !removed[v])
            sz[u] += calcSize(v, u);
    return sz[u];
}
int findCentroid(int u, int p, int n) {
    for (int v : adj[u])
        if (v != p && !removed[v] && sz[v] > n/2)
            return findCentroid(v, u, n);
    return u;
}
void decompose(int u) {
    int c = findCentroid(u, -1, calcSize(u, -1));
    removed[c] = true;
    // Xử lý centroid c
    for (int v : adj[c])
        if (!removed[v]) decompose(v);
}

🗺️ Euler Tour Khó

vector<int> tin, tout;
int timer = 0;
void euler(int u, int p) {
    tin[u] = ++timer;
    for (int v : adj[u])
        if (v != p) euler(v, u);
    tout[u] = timer;
}
// u là tổ tiên của v iff tin[u] <= tin[v] && tout[v] <= tout[u]

💧 Max Flow (Dinic) Khó

struct Dinic {
    struct Edge { int to, rev; int64_t cap; };
    vector<vector<Edge>> g;
    vector<int> level, iter;
    Dinic(int n) : g(n), level(n), iter(n) {}
    void addEdge(int u, int v, int64_t cap) {
        g[u].push_back({v, (int)g[v].size(), cap});
        g[v].push_back({u, (int)g[u].size()-1, 0});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : g[u])
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
        }
        return level[t] != -1;
    }
    int64_t dfs(int u, int t, int64_t f) {
        if (u == t) return f;
        for (int &i = iter[u]; i < g[u].size(); i++) {
            auto &e = g[u][i];
            if (e.cap > 0 && level[u] + 1 == level[e.to]) {
                int64_t d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int64_t maxFlow(int s, int t) {
        int64_t flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            int64_t f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) flow += f;
        }
        return flow;
    }
};

💰 Min-Cost Max-Flow Khó

struct MCMF {
    struct Edge { int to, rev; int64_t cap, cost; };
    vector<vector<Edge>> g;
    MCMF(int n) : g(n) {}
    void addEdge(int u, int v, int64_t cap, int64_t cost) {
        g[u].push_back({v, (int)g[v].size(), cap, cost});
        g[v].push_back({u, (int)g[u].size()-1, 0, -cost});
    }
    pair<int64_t,int64_t> minCost(int s, int t) {
        int n = g.size();
        int64_t flow = 0, cost = 0;
        vector<int64_t> dist(n);
        vector<int> inq(n), pv(n), pe(n);
        while (true) {
            fill(dist.begin(), dist.end(), LLONG_MAX);
            fill(inq.begin(), inq.end(), 0);
            dist[s] = 0;
            queue<int> q; q.push(s); inq[s] = 1;
            while (!q.empty()) {
                int u = q.front(); q.pop(); inq[u] = 0;
                for (int i = 0; i < g[u].size(); i++) {
                    auto &e = g[u][i];
                    if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u; pe[e.to] = i;
                        if (!inq[e.to]) { q.push(e.to); inq[e.to] = 1; }
                    }
                }
            }
            if (dist[t] == LLONG_MAX) break;
            int64_t f = LLONG_MAX;
            for (int v = t; v != s; v = pv[v]) f = min(f, g[pv[v]][pe[v]].cap);
            flow += f; cost += f * dist[t];
            for (int v = t; v != s; v = pv[v]) {
                auto &e = g[pv[v]][pe[v]];
                e.cap -= f;
                g[v][e.rev].cap += f;
            }
        }
        return {flow, cost};
    }
};

💑 Bipartite Matching Khó

vector<int> matchL, matchR;
vector<bool> vis;
int nL, nR;

bool augment(int u) {
    for (int v : adj[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (matchR[v] == -1 || augment(matchR[v])) {
            matchL[u] = v;
            matchR[v] = u;
            return true;
        }
    }
    return false;
}
int maxMatching() {
    matchL.assign(nL, -1);
    matchR.assign(nR, -1);
    int res = 0;
    for (int u = 0; u < nL; u++) {
        vis.assign(nR, false);
        if (augment(u)) res++;
    }
    return res;
}

🇭🇺 Hungarian Khó

Gán tối ưu chi phí (bài toán phân công). O(n³).

int64_t hungarian(vector<vector<int64_t>>& cost) {
    int n = cost.size(), m = cost[0].size();
    vector<int64_t> u(n+1), v(m+1);
    vector<int> p(m+1), way(m+1);
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<int64_t> minv(m+1, LLONG_MAX);
        vector<bool> used(m+1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], j1;
            int64_t delta = LLONG_MAX;
            for (int j = 1; j <= m; j++) if (!used[j]) {
                int64_t cur = cost[i0-1][j-1] - u[i0] - v[j];
                if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
                if (minv[j] < delta) { delta = minv[j]; j1 = j; }
            }
            for (int j = 0; j <= m; j++) {
                if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
                else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    return -v[0];
}

🧩 DP Cơ Bản Trung bình

Đếm số cách leo cầu thang (1 hoặc 2 bước)

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

Đổi tiền (Coin Change)

// Số đồng ít nhất để đổi amount
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++)
    for (int c : coins)
        if (i >= c && dp[i-c] != INT_MAX)
            dp[i] = min(dp[i], dp[i-c] + 1);

📈 LIS — Dãy Con Tăng Dài Nhất Trung bình

O(n²)

vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
    for (int j = 0; j < i; j++)
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
cout << *max_element(dp.begin(), dp.end());

O(n log n)

vector<int> v;
for (int x : a) {
    auto it = lower_bound(v.begin(), v.end(), x);
    if (it == v.end()) v.push_back(x);
    else *it = x;
}
cout << v.size();
// Chú ý: strictly increasing dùng lower_bound
// Non-decreasing dùng upper_bound

🔤 LCS — Dãy Con Chung Dài Nhất Trung bình

int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

🎒 Ba Lô Trung bình

0/1 Knapsack

vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
cout << dp[W];

Unbounded Knapsack

for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= W; j++)
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

➕ Kadane — Đoạn Con Tổng Lớn Nhất Dễ

int64_t best = a[0], cur = a[0];
for (int i = 1; i < n; i++) {
    cur = max((int64_t)a[i], cur + a[i]);
    best = max(best, cur);
}
cout << best;

🎭 Bitmask DP Khó

TSP (Travelling Salesman)

int n;
int dist[20][20];
int dp[1 << 20][20];
int tsp(int mask, int u) {
    if (mask == (1 << n) - 1) return dist[u][0];
    if (dp[mask][u] != -1) return dp[mask][u];
    int res = INT_MAX;
    for (int v = 0; v < n; v++)
        if (!(mask & (1 << v)))
            res = min(res, dist[u][v] + tsp(mask | (1 << v), v));
    return dp[mask][u] = res;
}

Đếm tập con có tổng = S

vector<int> dp(1 << n, 0);
dp[0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++) if (mask >> i & 1) sum += a[i];
    if (sum == S) /* đếm */;
}

🔢 Digit DP Khó

Đếm số thỏa mãn điều kiện trong đoạn [L, R].

string s;
int64_t dp[20][2][2];

int64_t solve(int pos, bool tight, bool start) {
    if (pos == s.size()) return 1;
    if (dp[pos][tight][start] != -1) return dp[pos][tight][start];
    int lim = tight ? s[pos] - '0' : 9;
    int64_t res = 0;
    for (int d = 0; d <= lim; d++) {
        bool ntight = tight && (d == lim);
        bool nstart = start && (d == 0);
        // Kiểm tra điều kiện tại đây
        res += solve(pos + 1, ntight, nstart);
    }
    return dp[pos][tight][start] = res;
}
// Số trong [0, N]:
int64_t count(int64_t N) {
    if (N < 0) return 0;
    s = to_string(N);
    memset(dp, -1, sizeof(dp));
    return solve(0, true, true);
}

🌳 Tree DP Khó

Đường kính cây (đường đi dài nhất giữa 2 node).

int diameter = 0;
int dfs(int u, int p) {
    int mx1 = 0, mx2 = 0;
    for (int v : adj[u]) if (v != p) {
        int h = dfs(v, u) + 1;
        if (h > mx1) { mx2 = mx1; mx1 = h; }
        else if (h > mx2) mx2 = h;
    }
    diameter = max(diameter, mx1 + mx2);
    return mx1;
}

Đếm số node của subtree

int cnt[N];
void dfs(int u, int p) {
    cnt[u] = 1;
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        cnt[u] += cnt[v];
    }
}

📊 DP Trên DAG Khó

Đường đi dài nhất trong DAG.

// Sau topo sort
vector<int> dp(n+1, 0);
for (int u : topo)
    for (auto [v, w] : adj[u])
        dp[v] = max(dp[v], dp[u] + w);
cout << *max_element(dp.begin(), dp.end());

↔️ Interval DP Khó

Bài toán nhân chuỗi ma trận, xâu palindrome, ...

// Palindrome dài nhất trong string s
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        if (s[i] == s[j])
            dp[i][j] = (len == 2) ? 2 : dp[i+1][j-1] + 2;
        else
            dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
    }
}
// dp[0][n-1] = độ dài palindrome dài nhất

⛓️ Matrix Chain Multiplication Khó

// p[i-1] x p[i] là kích thước ma trận i
vector<vector<int64_t>> dp(n, vector<int64_t>(n, 0));
for (int len = 2; len <= n; len++)
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        dp[i][j] = LLONG_MAX;
        for (int k = i; k < j; k++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]
                           + p[i] * p[k+1] * p[j+1]);
    }

📊 SOS DP (Sum Over Subsets) Khó

// dp[mask] = tổng a[sub] với sub là tập con của mask
vector<int64_t> dp = a;
for (int i = 0; i < n; i++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask & (1 << i))
            dp[mask] += dp[mask ^ (1 << i)];

📈 Convex Hull Trick Khó

Tối ưu DP: $dp[i] = \min_j (m_j \cdot x_i + b_j)$.

struct Line {
    int64_t m, b;
    int64_t get(int64_t x) { return m * x + b; }
};
// Thêm line với slope tăng dần, query x tăng dần
deque<Line> hull;
bool bad(Line a, Line b, Line c) {
    return (__int128)(c.b - a.b) * (a.m - b.m)
        <= (__int128)(b.b - a.b) * (a.m - c.m);
}
void add(Line l) {
    while (hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), l))
        hull.pop_back();
    hull.push_back(l);
}
int64_t query(int64_t x) {
    while (hull.size() >= 2 && hull[0].get(x) >= hull[1].get(x))
        hull.pop_front();
    return hull[0].get(x);
}

🔀 Divide & Conquer DP Khó

Tối ưu DP khi thỏa mãn tính đơn điệu của opt.

void compute(int l, int r, int optL, int optR) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<int64_t,int> best = {LLONG_MAX, -1};
    for (int k = optL; k <= min(mid, optR); k++) {
        int64_t val = dpPrev[k-1] + cost(k, mid);
        if (val < best.first) best = {val, k};
    }
    dpCur[mid] = best.first;
    compute(l, mid - 1, optL, best.second);
    compute(mid + 1, r, best.second, optR);
}

📚 Knuth Optimization Khó

Giảm DP từ $O(n^3)$ xuống $O(n^2)$ nếu thỏa mãn điều kiện Knuth.

for (int len = 2; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = LLONG_MAX;
        int optL = opt[i][j-1], optR = opt[i+1][j];
        for (int k = optL; k <= optR && k < j; k++) {
            int64_t val = dp[i][k] + dp[k+1][j];
            if (val < dp[i][j]) { dp[i][j] = val; opt[i][j] = k; }
        }
    }

🔢 Matrix Exponentiation Khó

const int MOD = 1e9 + 7;
struct Mat {
    int64_t a[20][20];
    int n;
    Mat(int _n) : n(_n) { memset(a, 0, sizeof(a)); }
    Mat operator*(const Mat& o) const {
        Mat c(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) if (a[i][k])
                for (int j = 0; j < n; j++)
                    c.a[i][j] = (c.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return c;
    }
};
Mat power(Mat a, int64_t n) {
    Mat r(a.n);
    for (int i = 0; i < a.n; i++) r.a[i][i] = 1;
    while (n) {
        if (n & 1) r = r * a;
        a = a * a;
        n >>= 1;
    }
    return r;
}

🎵 FFT / NTT Khó

Nhân 2 đa thức trong $O(n \log n)$.

typedef complex<double> cd;
void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len *= 2) {
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len/2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (inv) for (auto &x : a) x /= n;
}
vector<int64_t> multiply(vector<int64_t> a, vector<int64_t> b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n *= 2;
    fa.resize(n); fb.resize(n);
    fft(fa, false); fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);
    vector<int64_t> res(n);
    for (int i = 0; i < n; i++) res[i] = round(fa[i].real());
    return res;
}

🤝 Meet in the Middle Khó

Giảm $2^n$ xuống $2^{n/2}$.

int n;
vector<int64_t> a;
vector<int64_t> generate(int l, int r) {
    vector<int64_t> res;
    int sz = r - l;
    for (int mask = 0; mask < (1 << sz); mask++) {
        int64_t sum = 0;
        for (int i = 0; i < sz; i++)
            if (mask >> i & 1) sum += a[l+i];
        res.push_back(sum);
    }
    return res;
}
// Đếm tập con có tổng = S
auto left = generate(0, n/2), right = generate(n/2, n);
sort(right.begin(), right.end());
int64_t cnt = 0;
for (auto x : left)
    cnt += upper_bound(right.begin(), right.end(), S - x)
         - lower_bound(right.begin(), right.end(), S - x);

🎲 Randomized Algorithms Khó

Miller-Rabin (đã có trên)

Tìm min cặp bằng cách random

Hash set kiểm tra tập hợp

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randInt(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

🔥 Simulated Annealing Khó

double anneal() {
    double T = 100.0;
    double cur = random();
    double best = cur;
    while (T > 1e-9) {
        double nxt = neighbor(cur);
        double diff = f(nxt) - f(cur);
        if (diff < 0 || exp(-diff / T) > randomDouble())
            cur = nxt;
        if (f(cur) < f(best)) best = cur;
        T *= 0.999;
    }
    return best;
}

⚙️ Bit Tricks Trung bình

x & 1                // Lẻ?
x >> 1               // Chia 2
x << 1               // Nhân 2
x & (x - 1)          // Xóa bit phải nhất
x & -x               // Lấy bit phải nhất
x | (1 << k)         // Bật bit k
x & ~(1 << k)        // Tắt bit k
x ^ (1 << k)         // Đảo bit k
(x >> k) & 1         // Bit k?
__builtin_popcount(x)     // Đếm bit 1
__builtin_popcountll(x)   // Cho ll
__builtin_ctz(x)          // Đếm bit 0 phải
__builtin_clz(x)          // Đếm bit 0 trái
__builtin_parity(x)       // Parity bit

Duyệt mọi tập con của mask

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // Xử lý tập con sub của mask
}

🔘 Gray Code Trung bình

Mã Gray của n: n ^ (n >> 1)

int gray(int n) { return n ^ (n >> 1); }
// Sinh dãy Gray n bit
for (int i = 0; i < (1 << n); i++)
    cout << gray(i) << " ";

📦 STL Hữu Dụng Dễ

sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
reverse(v.begin(), v.end());
*max_element(v.begin(), v.end());
*min_element(v.begin(), v.end());
accumulate(v.begin(), v.end(), 0LL);
lower_bound(v.begin(), v.end(), x);
upper_bound(v.begin(), v.end(), x);
binary_search(v.begin(), v.end(), x);
count(v.begin(), v.end(), x);
unique(v.begin(), v.end());         // Xóa trùng liền kề (sort trước)
next_permutation(v.begin(), v.end());
prev_permutation(v.begin(), v.end());
__gcd(a, b);
gcd(a, b);                          // C++17
lcm(a, b);                          // C++17
__builtin_popcount(x);
to_string(x);
stoi(s); stoll(s); stod(s);
string(s.rbegin(), s.rend());

🎲 Tổ Hợp Xác Suất Trung bình

• Hoán vị vòng: $(n-1)!$
• Hoán vị có lặp: $\frac{n!}{k_1! k_2! \ldots}$
• Chỉnh hợp lặp: $n^k$
• Tổ hợp lặp: $C(n+k-1, k)$
• Nguyên lý bù trừ: $|A \cup B| = |A| + |B| - |A \cap B|$
• Chia kẹo Euler: $C(n+k-1, k-1)$

📊 Xác Suất Trung bình

$$P(A|B) = \frac{P(A \cap B)}{P(B)}$$

Bayes: $P(A|B) = \frac{P(B|A) P(A)}{P(B)}$

Kỳ vọng: $E[X] = \sum x \cdot P(X = x)$

Phương sai: $Var(X) = E[X^2] - E[X]^2$

🔢 Phương Pháp Số Khó

Newton-Raphson tìm nghiệm

double newton(double x0) {
    double x = x0;
    for (int i = 0; i < 100; i++)
        x = x - f(x) / df(x);
    return x;
}

Tính căn bậc 2

double mySqrt(double x) {
    double r = x;
    for (int i = 0; i < 100; i++) r = (r + x/r) / 2;
    return r;
}

Simpson tính tích phân

double simpson(double a, double b) {
    double c = (a + b) / 2;
    return (b - a) / 6 * (f(a) + 4*f(c) + f(b));
}

✅ Checklist Khi Làm Bài Quan trọng

1. Đọc kỹ đề — Input/Output, ràng buộc, ví dụ.
2. Xác định kiểu dữ liệu — int? long long? string?
3. Edge cases — 0, âm, biên, số lớn nhất.
4. Tràn số — Nhân 2 số có thể > 10^9?
5. Độ phức tạp — O(n²) có kịp? Cần O(n log n)?
6. Test tay — Tự chạy ví dụ nhỏ trước khi nộp.
7. Định dạng output — Dấu cách, xuống dòng đúng?
8. Nộp nhiều lần — WA rồi sửa, đừng sợ!
9. Đọc lại code — Tên biến, dấu chấm phẩy, ngoặc.
10. Comment — Ghi chú những chỗ quan trọng.