# TỔNG ÔN KIẾN THỨC

## Xử lý xâu

### So khớp xâu
- **Thuật toán/kỹ thuật:** hash, hash tràn số, hash 2 base, hash xor, hash cộng.
- **Lưu ý**: chọn **base** với **mod** phù hợp, đối với hash xor và hash cộng cần có **hàm random**.
- **Các dạng bài tập:** so khớp xâu, so khớp tập hợp, băm một tập hợp, …

### Cây tiền tố
- **Thuật toán/kỹ thuật:** trie kí tự, trie nhị phân.
- **Lưu ý:** lựa chọn cách cài phù hợp (dùng mảng hoặc dùng con trỏ), đối với dùng mảng cần tính toán kĩ kích thước mảng.
- **Các dạng bài tập:** liên quan đến tiền tố của xâu, biểu diễn nhị phân của 1 số.

## Toán học

### Số học

- **Công thức:**
- Giai thừa: $$n!$$

        int fact[N];
        void prepare(){
            fact[0] = 1;
            for(int i=1; i<=n; i++)
                fact[i] = 1LL*fact[i-1]*i%MOD;
        }

- Tổ hợp:
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n (n-1) \cdots (n-k+1)}{k (k-1) \cdots 1}
$$
$$\binom{n}{2} = \frac{n(n-1)}{2}$$
$$\binom{n}{3} = \frac{n (n-1) (n-2)}{6}$$

        int fact[N], ifact[N];
        void prepare(){
            fact[0] = 1;
            for(int i=1; i<=n; i++)
                fact[i] = 1LL*fact[i-1]*i%MOD;
            ifact[n] = Pow(fact[n], MOD-2);
            for(int i=n; i>=1; i--)
                ifact[i-1] = 1LL*ifact[i]*i%MOD;
        }
        
        
        int C(int k, int n){
            return 1LL*fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
        }

- Chỉnh hợp:
$$
A_n^k = \binom{n}{k} \times k! = \frac{n!}{(n-k)!} = n (n-1) (n-2) \cdots (n-k+1)
$$

- Số Fibonacci:
$$
F(n) =
\begin{cases}
1, & \text{khi } n = 1;\\
1, & \text{khi } n = 2;\\
F(n-1) + F(n-2), & \text{khi } n > 2.
\end{cases}
$$

$$ \gcd(F(a), F(b)) = F(\gcd(a, b))$$

- Số Catalan: đếm dãy ngoặc đúng độ dài $2n$
$$
C_n = \frac{1}{n+1} \binom{2n}{n}
= \frac{(2n)!}{(n+1)! \, n!}
$$

$$
C_0 = 1,\quad
C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}
$$

- Tổng bình phương/lập phương:
$$
S_n = 1^2 + 2^2 + 3^2 + \cdots + n^2
= \frac{n(n+1)(2n+1)}{6}
$$

$$
S_n = 1^3 + 2^3 + 3^3 + \cdots + n^3
= \left( 1 + 2 + 3 + \cdots + n \right)^2 =\left( \frac{n(n+1)}{2} \right)^2
$$

- **Thuật toán/kỹ thuật:**
- Sàng nguyên tố, tìm thừa số số nguyên tố bé nhất của một số

        bool ck[N];
        int minprime[N];
        vector<int> primes;
        void sieve(){
            for(int i=2; 1LL*i*i<=n; i++)
                if(ck[i])
                    for(int j=i*i; j<=n; j+=i)
                        ck[j] = false;
                        
            for(int i=2; 1LL*i*i<=n; i++)
                if(minprime[i] == 0)
                    for(int j=i*i; j<=n; j+=i)
                        minprime[j] = i;  
            
            for(int i=2; i<=n; i++)
                if(!minprime[i])
                    primes.push_back(i);
        }

- Tìm ước, tổng các ước
- Phân tích thừa số nguyên tố (chia cho thừa số nguyên tố nhỏ nhất của x cho đến khi x = 1)
- Các số nguyên tố cùng nhau ($\gcd(a, b) = 1$).
- Nhân nhị phân, lũy thừa nhị phân

    // sử dụng khi mod*mod > giới hạn long long a*b = (a%mod)*(b%mod) > giới hạn long long
    ll mul(ll a, ll b){
        ll ans=0;
        for(; b>0; b>>=1){
            if(b&1) ans = (ans+a)%mod;
            a = (a+a)%mod;
        }
        return ans;
    }
    
    // lưu ý kiểu dữ liệu trả về của từng hàm là int hoặc long long tùy vào giá trị của mod.
    
    int pow(ll n, ll k){
        n%=mod;
        int ans=1;
        for(; k>0; k>>=1){
            if(k&1) ans = 1LL*ans*n%mod;
            n = 1LL*n*n%mod;
        }
        return ans;
    }

- Nghịch đảo modulo: $\frac{1}{x} \% mod = x^{mod-2} \% mod$

- GCD / LCM:
$$
\gcd(a, b) =
\begin{cases}
a, & \text{khi } b = 0;\\
\gcd(b, a \bmod b), & \text{khi } b \ne 0.
\end{cases}
$$

$$\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b$$

$$
k \in \mathbb{N}^+$:
\gcd(ka, kb) = k \cdot \gcd(a, b)
$$

$$\gcd(a, b) = \gcd(a - b, b) = \gcd(a, b - a)$$

- Bao hàm loại trừ
- Phi hàm euler*

### Hình học
- Sweepline

## Quy hoạch động
### Các dạng bài tập
- DP digit
- DP thứ tự từ điển
- DP knapsack
- DP range
- DP bitmask
- Lưu ý: Cách duyệt submask của một mask, một số phép toán bit thông dụng

    // dpt O(3^n)
    for(int mask = 0; mask < (1<<n); mask++)
        for(int submask=mask; submask > 0; submask = (submask-1)&mask)
    // nếu muốn lấy submask = 0 thì thay đổi vòng for và thêm dòng if(submask == 0) break để tránh tle.
    //đếm số bit bật của mask
    __builtin_popcount(mask);
    

- DP SOS*
- DP trên đồ thị
- DP trên DAG
- DP on tree
- DP reroot
- DP đảo nhãn
- DP chia để trị*

### Một số kĩ thuật tối ưu nên nhớ
- Dãy con tăng sử dụng chặt nhị phân
- DP cái túi tối ưu bằng chia log
- Nếu $dp[i][j]$ chỉ phụ thuộc vào $dp[i-1][k]$ có thể khai báo $dp[0/1][N]$ để tối ưu bộ nhớ

    int cur = i&1;
    int pre = cur^1;
    // khi này dp hiện tại là cur và trước đó là pre
    // khi sử dụng kĩ thuật này lưu ý memset lại giá trị của dp[cur] trước khi thực hiện tính toán để tránh sai sót

- Tối ưu bằng deque*

## Đồ thị
### Đơn đồ thị, đa đồ thị
- DFS/BFS, BFS 0-1 trên đồ thị có trọng số cạnh là 0-1, BFS một nguồn, đa nguồn
- Kiểm tra đồ thị hai phía
- Kiểm tra chu trình, đếm chu trình (euler, halminton)
- Cây khung nhỏ nhất (kruskal, prim)
- Lưu ý: Nắm các tính chất của cây khung để áp dụng vào bài, thường sử dụng nhất là tính chất đường đi hẹp nhất (cực tiểu hóa cạnh lớn nhất)
- Tìm khớp cầu, tplt mạnh trên đồ thị vô hướng/có hướng (tarjan, kosaraju)
- Lưu ý: Các trường hợp cạnh vô hướng, có hướng, cạnh lặp có thể sẽ khác nhau một chút về cách cài của tarjan
- Ví dụ đối với đồ thị vô hướng có cạnh lặp thì thay vì sử dụng dfs(int u, int p) nên sử dụng dfs(int u, int id) với id là cạnh vừa duyệt trước đó để tránh lặp lại cạnh đã duyệt
- Nén đồ thị thành cây (các cạnh là cầu, các đỉnh là các tplt).
- Đường đi ngắn nhất (dijkstra, floyd, bellman-ford) một nguồn/đa nguồn, dijkstra + bitmask
- Lưu ý: Một số bài cần cài đặt hàm sort riêng cho priority_queue của dijkstra

    
    // Data là kiểu dữ liệu sử dụng cho các phần tử trong priority queue (int, long long, struct, ...)
    struct Data{
        int w;
    }
    
    struct cmp{
        bool operator () (Data a, Data b){
            // hàm sort theo chiều ngược lại
            // ví dụ để priority queue sort tăng dần theo w (phần tử đầu tiên bé nhất) thì trả về như sau
            return a.w > b.w;
        }
    };
    
    priority_queue<Data, vector<Data>, cmp> Q;

### DAG
- Toposort

### Cây
- LCA
- Euler Tour
- HLD Decomposition
- Sack (Small to large on tree)
- Centroid Decomposition*
- Cây ảo*

## CTDL
- Segment Tree (Interval Tree)
- Update Point/Range/Lazy
- Polynomial Update
- Walk on IT (chặt nhị phân trên IT)
- Lưu ý: mấy bài khó yêu cầu nhiều thông tin trong một node và cài đặt hàm merge các node con để cập nhập đáp án cho node cha
- Fenwick Tree
- RMQ, RMQ 2D (Sparse Table)
- Mảng cộng dồn, mảng hiệu
- STL: vector, map, set, queue, deque, stack, heap, ...
- Monotonic deque (Min - Max tịnh tiến)
- DSU, DSU rollback
- Small to Large
- Sqrt Decompostion (Chia căn)
- Chia căn block
- Chia căn truy vấn
- Chia căn nặng nhẹ
- Chia căn dựa vào tổng giới hạn
- Mo's algorithm
- Lưu ý: kích thước block = const

    const int nr = 320;
    
    // hàm sort của mo's
    struct Data{
        int l, r, id;
        bool operator < (const Data &other){
            if(l/nr == other.l/nr){
                if((l/nr)&1) return r > other.r;
                return r < other.r;
            }
            return l < other.l;
        }
    }

## Kỹ thuật
- Chặt nhị phân (kết quả, số nguyên, số thực, trên hàm số có dạng parabol)
- 2 con trỏ
- Tham lam
- Chia đôi tập
- Đệ quy
- Lưu ý: Nếu dùng codeblock thì nên chỉnh cài đặt kích thước stack trước để chạy được những test lớn
- Backtrack
- Sinh hoán vị
- Lưu ý: Sử dụng hàm next_permutation của c++ nhớ sort lại vector trước khi dùng

## Template
### Sinh test

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

#define ll long long
#define nl '\n'
#define fu(i, a, b) for(int i=a; i<=b; i++)
#define fd(i, a, b) for(int i=a; i>=b; i--)
#define pb push_back
#define eb emplace_back
#define BIT(i, n) (((n) >> (i))&(1))
#define pii pair<int, int>
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define SZ(s) (int)(s.size())

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

// st = bắt đầu
// en = kết thúc
const int st = 1;
const int en = 50;
const string NAME = "quan";

ll rnd(ll l, ll r){
    assert(l <= r);
    uniform_int_distribution<ll> dis(l, r);
    return dis(rd);
}


void gen(){
    ofstream cout ((NAME + ".inp").c_str());
    ///code sinh test
    
}

int main(){
    srand(time(0));
    fu(i, st, en){
        gen();
        system((NAME + ".exe").c_str());
        system((NAME + "_trau.exe").c_str());
        if(system(("fc " + NAME + ".out ans.out").c_str())){
            cout << "Test " << i << ": WRONG" << nl; 
            break;
        }else cout << "Test " << i << ": ACCEPTED" << nl; 
    }
}