算法模板 SFMB.XYZ

全网最好的ACM/ICPC零基础算法模板，代码简短，封装完美，解释清晰，通用性强。

只包含常用算法，适合 Rating 1200 ~ 2000 。

版本

By dqw ，Version 4.0 - 2025.3.15

许可

CC BY 4.0 允许任何形式的使用、复制、修改、合并、转载

资源

官方在线网页版（https://sfmb.xyz）

下载纸质版 PDF 文件（TBC）（不要直接打印此网页）

算法模板 SFMB.XYZ全网最好的ACM/ICPC零基础算法模板，代码简短，封装完美，解释清晰，通用性强。只包含常用算法，适合 Rating 1200 ~ 2000 。版本许可资源目录i. 初始化1. Vim for Linux 快速配置2. C++ 初始文件3. C++ 火车头编译优化4. 随机数生成 64 位随机数（初始文件默认已包含）卡时自定义 unordered_map/unordered_set 防卡哈希ii. 数论1. 快速幂2. 快速平方根3. 扩展欧几里得4. 逆元与组合数扩展欧几里得求单个数字的逆元线性求逆元和组合数5. 素数测试与因式分解Miller Rabin 判断素数Pollard Rho 分解因数6. 欧拉筛法7. 扩展中国剩余定理8. 数论分块iii. 数据结构1. 并查集 DSU2. ST 表3. 树状数组单点修改，区间求和求逆序对二维树状数组4. 线段树普通线段树单点修改，区间查询懒标记线段树区间加，区间乘，区间赋值，区间求和5. 莫队iv. 图论1. 最短路2. 树的直径3. 最近公共祖先 LCA4. 拓扑排序5. 最小生成树 MSTPrimKruskal6. 二分图v. 字符串1. 字符串哈希 String Hash2. 前缀函数 KMP3. Z 函数拓展 KMP4. 最长回文串 Manacher5. 后缀数组 SA6. 字典树 Trie字符串字典树0-1 字典树7. Lyndon 分解8. 最小表示法9. AC 自动机 Aho-Corasickvi. 动态规划1. 最长上升子序列 LIS2. 最长公共子序列 LCS3. 最长公共上升子序列 LCISvii. 几何1. 二维计算几何基础2. 多边形的周长与面积Pick 定理多边形求周长三角形求有向面积多边形求有向面积3. 凸包Andrew 算法求凸包闵可夫斯基和判断点是否在凸包中4. 旋转卡壳 —— 求凸包直径viii. 代数1. 快速傅里叶变换 FFT2. 快速数论变换 NTT3. 行列式高斯消元行列式求值4. 矩阵

i. 初始化

1. Vim for Linux 快速配置

终端 vim .vimrc 修改配置
F8 一键编译运行 C++ 代码


xxxxxxxxxx
syn on
set nocp nu ts=4 sw=4 ai cin hls is mouse=a
map <F8> :w<CR>:!g++ -O2 % -o %.run && time ./%.run<CR>

2. C++ 初始文件

后面所有代码片段均基于此头文件


xxxxxxxxxx
#include <bits/stdc++.h>
#define int long long
#define iint __int128
using namespace std;
const int mod = 1e9 + 7;
mt19937_64 randl(random_device{}());
void solve()
{

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
    return 0;
}

3. C++ 火车头编译优化

加在代码开头，略微加快运行速度。（编译不成功可以删掉 target("avx") ）


xxxxxxxxxx
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

4. 随机数

生成 64 位随机数（初始文件默认已包含）

randl()：返回64位随机数


xxxxxxxxxx
mt19937_64 randl(random_device{}());

或


xxxxxxxxxx
mt19937_64 randl(chrono::steady_clock::now().time_since_epoch().count());

卡时

MAX_TIME 略小于时间限制（秒）


xxxxxxxxxx
double MAX_TIME = 1.8;
while ((double)clock() / CLOCKS_PER_SEC < MAX_TIME)
{
    // random function
}

自定义 unordered_map/unordered_set 防卡哈希

使用 unordered_map<int,int,CustomHash> 或 unordered_set<int,CustomHash> 防卡哈希


xxxxxxxxxx
struct CustomHash {
    int operator()(int x) const {
        static const int i = randl();
        x ^= i;
        x ^= x << 25;
        x ^= x >> 15;
        x ^= x << 35;
        return x;
    }
};

ii. 数论

1. 快速幂

qpow(a,b,m) $a^{b}\ \%\ m$
qpow(a,b) $a^{b}\ \%\ mod$
qpow(a) $a^{-1}\ \%\ mod$ $a$ 的逆元


xxxxxxxxxx
int qpow(int a, int b = mod - 2, int m = mod)
{
    int ret = 1;
    while (b)
    {
        if (b & 1) ret = ret * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ret;
}

2. 快速平方根

qsqrt(a,eps)：返回精度为 eps 的 a 的平方根


xxxxxxxxxx
double qsqrt(double a, double eps)
{
    if (a <= 0) return 0;
    double x = 0, y = a;
    while (fabs(x - y) > eps)
    {
        x = y;
        y = (x + a / x) / 2.0;
    }
    return y;
}

3. 扩展欧几里得

exgcd(a,b,x,y) $a,b$ $x$ $y$ $a \cdot x + b \cdot y = \gcd(a, b)$ $\gcd(a, b)$


xxxxxxxxxx
int exgcd(int a, int b, int &x, int &y)
{
    if (not b) return x = 1, y = 0, a;
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

4. 逆元与组合数

扩展欧几里得求单个数字的逆元

inverse(x) $x^{-1}\ \%\ mod$ $x$ 的逆元


xxxxxxxxxx
int inverse(int a)
{
    int u = 0, v = 1, m = mod;
    while (a != 0)
    {
        int t = m / a;
        m -= t * a;
        swap(a, m);
        u -= t * v;
        swap(u, v);
    }
    return (u + mod) % mod;
}

线性求逆元和组合数

init() $1\sim N$ 的组合数
comb(n,m) $\displaystyle C_n^m$
inv[x] $x^{-1}\ \%\ mod$ $x$ 的逆元


xxxxxxxxxx
const int N = 2e6 + 5;
int F[N], inv[N], Finv[N];
void init()
{
    F[0] = Finv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++)
    {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    for (int i = 1; i < N; i++)
    {
        F[i] = F[i - 1] * i % mod;
        Finv[i] = Finv[i - 1] * inv[i] % mod;
    }
}
int comb(int n, int m)
{
    if (m < 0 or n < 0 or n < m) return 0;
    return F[n] * Finv[n - m] % mod * Finv[m] % mod;
}

5. 素数测试与因式分解

Miller Rabin 判断素数

isprime(n)：返回 n 是否为素数


xxxxxxxxxx
bool isprime(int n)
{
    if (n < 2) return 0;
    int t = __builtin_ctzll(n - 1);
    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
    {
        if (a == n) return 1;
        int v = 1, d = (n - 1) >> t;
        for (; d; d >>= 1)
        {
            if (d & 1) v = (iint)v * a % n;
            a = (iint)a * a % n;
        }
        if (v == 1) continue;
        for (; d < t; d++)
        {
            if (v == n - 1) break;
            v = (iint)v * v % n;
        }
        if (d == t) return 0;
    }
    return 1;
}

Pollard Rho 分解因数

前置：Miller Rabin 判断素数（isprime）

factorize(n)：返回 n 的所有因数，从小到大排列


xxxxxxxxxx
vector<int> factorize(int a)
{
    map<int, int> m;
    function<void(int)> f = [&](int n) -> void {
        if (n <= 1000)
        {
            for (int i = 2; i * i <= n; i++)
                for (; n % i == 0; n /= i)
                    m[i]++;
            if (n > 1) m[n]++;
            return;
        }
        if (isprime(n))
        {
            m[n]++;
            return;
        }
        for (int i = 2;; i++)
        {
            int x = i, y = i, d = 1, r = 1, l = 0, v = 1;
            while (d == 1)
            {
                y = ((iint)y * y + 1) % n;
                v = (iint)v * abs(x - y) % n;
                l++;
                if (l % 127 == 0) d = gcd(v, n), v = 1;
                if (l == r) d = gcd(v, n), v = 1, x = y, r *= 2, l = 0;
            }
            if (d != n)
            {
                f(d);
                f(n / d);
                return;
            }
        }
    };
    f(a);
    vector<pair<int, int>> tmp(m.begin(), m.end());
    vector<int> fac;
    function<void(int, int)> dfs = [&](int id, int x) -> void {
        if (id == m.size())
        {
            fac.push_back(x);
            return;
        }
        int p = 1;
        for (int i = 0; i <= tmp[id].second; i++)
        {
            dfs(id + 1, x * p);
            p *= tmp[id].first;
        }
    };
    dfs(0, 1);
    sort(fac.begin(), fac.end());
    return fac;
}

6. 欧拉筛法

sieve() $1\sim N$ $1\sim N$ 内的所有素数
phi[n] $n$ $1$ $n$ $n$ 互质的数字个数
notprime[i] == 0：表示 i 是素数
pri[]：从小到大存所有筛出的素数


xxxxxxxxxx
const int N = 2e6 + 5;
vector<int> pri;
bool notprime[N];
int phi[N];
void sieve()
{
    phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (not notprime[i])
        {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for (int j : pri)
        {
            if (i * j >= N) break;
            notprime[i * j] = true;
            if (i % j == 0)
            {
                phi[i * j] = phi[i] * j;
                break;
            }
            phi[i * j] = phi[i] * phi[j];
        }
    }
}

7. 扩展中国剩余定理

前置：扩展欧几里得（exgcd）

excrt(b,a) $\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}$ 的最小解 x


xxxxxxxxxx
int excrt(vector<int> a, vector<int> b)
{
    int x, y, m = b[0], ans = a[0];
    for (int i = 1; i < a.size(); i++)
    {
        int c = (a[i] + b[i] - ans % b[i]) % b[i];
        int g = exgcd(m, b[i], x, y);
        if (c % g) return -1;
        x = (iint)x * c / g % b[i];
        ans += x * m;
        m = (iint)m * b[i] / g;
        ans = (ans + m) % m;
    }
    return ans;
}

8. 数论分块

div(n) $\sum_{i=1}^n\left\lfloor\dfrac ni\right\rfloor$


xxxxxxxxxx
int div(int n)
{
    int res = 0;
    int l = 1, r;
    while (l <= n)
    {
        r = n / (n / l);
        res += (r - l + 1) * (n / l);
        l = r + 1;
    }
    return res;
}

iii. 数据结构

1. 并查集 DSU

DSU dsu(n) $[1,n]$ 并查集
dsu.find(x) $x$ 的父节点
dsu.size(x) $x$ 所在并查集大小
dsu.same(x,y) $x$ $y$ 是否在同一区间
dsu.merge(x,y) $x$ $y$ $y$ $x$ ，若已合并返回 false


xxxxxxxxxx
struct DSU {
    vector<int> fa, sz;
    DSU(int n)
    {
        fa.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; i++) sz[i] = 1, fa[i] = i;
    }
    int find(int x)
    {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
    int size(int x)
    {
        return sz[find(x)];
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y) return false;
        sz[x] += sz[y];
        fa[y] = x;
        return true;
    }
};

2. ST 表

ST st(a)a $1$ 开始，初始化 ST 表
st.query(l,r) $[l,r]$ 的区间 combine 信息（最大值/最小值/或/与此部分在 combine() 函数中修改）


xxxxxxxxxx
struct ST {
    vector<vector<int>> f;
    int combine(int x, int y)
    {
        return max(x, y);
    }
    ST(vector<int> a)
    {
        int n = a.size() - 1;
        f.resize(n + 1, vector<int>(64 - __builtin_clzll(n)));
        for (int i = 1; i <= n; i++)
            f[i][0] = a[i];
        for (int j = 1; j <= f[0].size(); j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)
                f[i][j] = combine(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    int query(int l, int r)
    {
        int i = 63 - __builtin_clzll(r - l + 1);
        return combine(f[l][i], f[r - (1 << i) + 1][i]);
    }
};

3. 树状数组

单点修改，区间求和求逆序对

Fenwick a(n) $[1,n]$ 的树状数组
a.add(pos,val)：将下标为 pos 的值增加 val
a.sum(r) $[1,r]$ 的和
a.query(l,r) $[l,r]$ 的和
invpair(x)：计算数组 x 的逆序对数量


xxxxxxxxxx
struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int x)
    {
        n = x;
        a.resize(x + 1);
    }
    void add(int x, int v)
    {
        for (int i = x; i <= n; i += i & -i)
        {
            a[i] += v;
        }
    }
    int sum(int x)
    {
        int ans = 0;
        for (int i = x; i > 0; i -= i & -i)
        {
            ans += a[i];
        }
        return ans;
    }
    int query(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};
int invpair(vector<int> a)
{
    int n = a.size(), ret = 0;
    vector<pair<int, int>> x(n);
    for (int i = 0; i < n; i++)
    {
        x[i] = {a[i], i};
    }
    sort(x.rbegin(), x.rend());
    Fenwick f(n);
    for (auto p : x)
    {
        f.add(p.second + 1, 1);
        ret += f.sum(p.second);
    }
    return ret;
}

二维树状数组

Fenwick2D a(n,m) $[(1,1),(n,m)]$ 的 2D 树状数组
a.add(x,y,val)：将下标为 (x,y) 的值增加 val
a.sum(x,y) $[(1,1),(x,y)]$ 的和
a.query(x1,y1,x2,y2) $[(x_1,y_1),(x_2,y_2)]$ 的和


xxxxxxxxxx
struct Fenwick2D {
    int n, m;
    vector<vector<int>> a;
    Fenwick2D(int x, int y)
    {
        n = x, m = y;
        a.resize(x + 1, vector<int>(y + 1));
    }
    void add(int x, int y, int v)
    {
        for (int i = x; i <= n; i += i & -i)
        {
            for (int j = y; j <= m; j += j & -j)
            {
                a[i][j] += v;
            }
        }
    }
    int sum(int x, int y)
    {
        int ans = 0;
        for (int i = x; i > 0; i -= i & -i)
        {
            for (int j = y; j > 0; j -= j & -j)
            {
                ans += a[i][j];
            }
        }
        return ans;
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    }
};

4. 线段树

普通线段树单点修改，区间查询

Segment a(n) $[1,n]$ 的线段树
a.update(pos,val)：将下标为 pos 的值设置为 val
a.query(l,r) $[l,r]$ 的 combine 信息


xxxxxxxxxx
struct Segment {
    int n;
    vector<int> t;
    Segment(int x)
    {
        n = x;
        t.resize(x * 4 + 1);
    }
    int combine(int x, int y)
    {
        return max(x, y);
    }
    void pushup(int p)
    {
        t[p] = combine(t[p << 1], t[p << 1 | 1]);
    }
    void update(int pos, int val, int l, int r, int p)
    {
        if (l == r)
        {
            t[p] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(pos, val, l, m, p << 1);
        else update(pos, val, m + 1, r, p << 1 | 1);
        pushup(p);
    }
    int query(int L, int R, int l, int r, int p)
    {
        if (L <= l and r <= R) return t[p];
        int m = (l + r) >> 1;
        int res = 0;
        if (L <= m) res = combine(res, query(L, R, l, m, p << 1));
        if (R > m) res = combine(res, query(L, R, m + 1, r, p << 1 | 1));
        return res;
    }
    void update(int pos, int val)
    {
        update(pos, val, 1, n, 1);
    }
    int query(int l, int r)
    {
        return query(l, r, 1, n, 1);
    }
};

懒标记线段树区间加，区间乘，区间赋值，区间求和

Lazy a(n) $[1,n]$ 的线段树
a.mul(l,r,val) $[l,r]$ 的值乘上 val
a.add(l,r,val) $[l,r]$ 的值加上 val
a.update(l,r,val) $[l,r]$ 的值设置为 val
a.query(l,r) $[l,r]$ 的区间和模 mod


xxxxxxxxxx
struct Lazy {
    int n;
    vector<int> a, m, t;
    Lazy(int x)
    {
        n = x;
        m.resize(x * 4 + 1, 1);
        a.resize(x * 4 + 1);
        t.resize(x * 4 + 1);
    }
    void pushup(int p)
    {
        t[p] = (t[p << 1] + t[p << 1 | 1]) % mod;
    }
    void pushdown(int p, int c)
    {
        t[p << 1] = (t[p << 1] * m[p] + a[p] * (c - (c >> 1))) % mod;
        t[p << 1 | 1] = (t[p << 1 | 1] * m[p] + a[p] * (c >> 1)) % mod;
        m[p << 1] = m[p << 1] * m[p] % mod;
        m[p << 1 | 1] = m[p << 1 | 1] * m[p] % mod;
        a[p << 1] = (m[p] * a[p << 1] + a[p]) % mod;
        a[p << 1 | 1] = (m[p] * a[p << 1 | 1] + a[p]) % mod;
        m[p] = 1;
        a[p] = 0;
    }
    void mul(int L, int R, int c, int l, int r, int p)
    {
        if (L <= l and r <= R)
        {
            a[p] = a[p] * c % mod;
            m[p] = m[p] * c % mod;
            t[p] = t[p] * c % mod;
            return;
        }
        pushdown(p, r - l + 1);
        int m = (l + r) >> 1;
        if (L <= m) mul(L, R, c, l, m, p << 1);
        if (m < R) mul(L, R, c, m + 1, r, p << 1 | 1);
        pushup(p);
    }
    void add(int L, int R, int c, int l, int r, int p)
    {
        if (L <= l and r <= R)
        {
            a[p] = (a[p] + c) % mod;
            t[p] = (t[p] + c * (r - l + 1)) % mod;
            return;
        }
        pushdown(p, r - l + 1);
        int m = (l + r) >> 1;
        if (L <= m) add(L, R, c, l, m, p << 1);
        if (m < R) add(L, R, c, m + 1, r, p << 1 | 1);
        pushup(p);
    }
    int query(int L, int R, int l, int r, int p)
    {
        if (L <= l and r <= R) return t[p];
        pushdown(p, r - l + 1);
        int m = (l + r) >> 1;
        int res = 0;
        if (L <= m) res = (res + query(L, R, l, m, p << 1)) % mod;
        if (m < R) res = (res + query(L, R, m + 1, r, p << 1 | 1)) % mod;
        return res;
    }
    void mul(int l, int r, int c)
    {
        mul(l, r, c, 1, n, 1);
    }
    void add(int l, int r, int c)
    {
        add(l, r, c, 1, n, 1);
    }
    void update(int l, int r, int c)
    {
        mul(l, r, 0);
        add(l, r, c);
    }
    int query(int l, int r)
    {
        return query(l, r, 1, n, 1);
    }
};

5. 莫队

$n=m$ $[l,r]$ $O(1)$ $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$ $[l,r]$ $O(n\sqrt{n})$ 的复杂度内求出所有询问的答案。离线。


xxxxxxxxxx
int block;
struct info {
    int l, r, id;
    bool operator<(const info &x) const {
        if (l / block != x.l / block) return l < x.l;
        return (l / block) & 1 ? r < x.r : r > x.r;
    }
};
void solve()
{
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    block = sqrt(n);
    vector<info> q(m);
    for (int i = 0; i < m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q.begin(), q.end());
    int sum = 0, l = 1, r = 0;
    int ans[m];
    auto move = [&](int pos, int sign) -> void {
        if (sign) // move +
        else // move -
    };
    for (int i = 0; i < m; i++)
    {
        while (l > q[i].l) move(--l, 1);
        while (r < q[i].r) move(++r, 1);
        while (l < q[i].l) move(l++, 0);
        while (r > q[i].r) move(r--, 0);
        ans[q[i].id] = ; // get ans
    }
    for (int i = 0; i < m; i++)
    {
        cout << ans[i] << endl;
    }
}

iv. 图论

1. 最短路

堆优化 Dijkstra 求最短路，dis[i]：出发点 s 到各点 i 的最短距离


xxxxxxxxxx
void solve()
{
    int n, m, s;
    cin >> n >> m >> s;
    vector<pair<int, int>> g[n + 1];
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    vector<int> dis(n + 1, INT_MAX), vis(n + 1);
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    dis[s] = 0;
    while (not q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [v, w] : g[x])
        {
            if (dis[x] + w < dis[v])
            {
                dis[v] = dis[x] + w;
                q.push({-dis[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << ' ';
    }
}

2. 树的直径

树上任意两节点之间最长的简单路径即为树的直径

两次 DFS 求树的直径，DFS 两次后 dis[c] 为树的直径


xxxxxxxxxx
void solve()
{
    int n;
    cin >> n;
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> dis(n + 1);
    int c = 0;
    function<void(int, int)> dfs = [&](int x, int fa) -> void {
        for (auto p : g[x])
        {
            if (p == fa) continue;
            dis[p] = dis[x] + 1;
            if (dis[p] > dis[c]) c = p;
            dfs(p, x);
        }
    };
    dfs(1, 0);
    dis[c] = 0;
    dfs(c, 0);
    cout << dis[c] << endl;
}

3. 最近公共祖先 LCA

给定一棵有根树，求出指定两个点直接最近的公共祖先，倍增算法求 LCA

dfs(s,0)：s 为根节点，预处理 LCA
LCA(x,y)：求 x 和 y 节点的 LCA


xxxxxxxxxx
void solve()
{
    int n, m, s;
    cin >> n >> m >> s;
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> depth(n + 1), lg(n + 1);
    vector<array<int, 24>> fa(n + 1);
    for (int i = 1; i <= n; i++)
    {
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    }
    function<void(int, int)> dfs = [&](int x, int f) -> void {
        fa[x][0] = f;
        depth[x] = depth[f] + 1;
        for (int i = 1; i <= lg[depth[x]]; i++)
        {
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        }
        for (auto p : g[x])
        {
            if (p == f) continue;
            dfs(p, x);
        }
    };
    function<int(int, int)> LCA = [&](int x, int y) -> int {
        if (depth[x] < depth[y]) swap(x, y);
        while (depth[x] > depth[y])
        {
            x = fa[x][lg[depth[x] - depth[y]] - 1];
        }
        if (x == y) return x;
        for (int i = lg[depth[x]] - 1; i >= 0; i--)
        {
            if (fa[x][i] == fa[y][i]) continue;
            x = fa[x][i];
            y = fa[y][i];
        }
        return fa[x][0];
    };
    dfs(s, 0);
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        cout << LCA(x, y) << endl;
    }
}

4. 拓扑排序

给一个有向无环图的所有节点排序

Kahn 算法求有向图顺序，ans[]：图的所有节点顺序


xxxxxxxxxx
void solve()
{
    int n;
    cin >> n;
    vector<int> g[n + 1];
    vector<int> in(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1;; j++)
        {
            int t;
            cin >> t;
            if (t == 0) break;
            g[i].push_back(t);
            in[t]++;
        }
    }
    vector<int> ans;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);
        }
    }
    while (not q.empty())
    {
        int x = q.front();
        q.pop();
        ans.push_back(x);
        for (auto p : g[x])
        {
            if (--in[p] == 0)
            {
                q.push(p);
            }
        }
    }
    for (auto p : ans)
    {
        cout << p << ' ';
    }
}

5. 最小生成树 MST

无向连通图的最小生成树为边权和最小的生成树。Prim 在稠密图中比 Kruskal 优，在稀疏图中比 Kruskal 劣。

Prim

Prim+堆优化求最小生成树，ans：最小生成树的大小，若 cnt < n 该图不连通。


xxxxxxxxxx
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> g[n + 1];
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int cnt = 0, ans = 0;
    vector<int> dis(n + 1, INT_MAX), vis(n + 1);
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    dis[1] = 0;
    while (not q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        cnt++;
        ans += dis[x];
        for (auto [v, w] : g[x])
        {
            if (dis[v] > w)
            {
                dis[v] = w;
                q.push({-dis[v], v});
            }
        }
    }
    if (cnt < n)
    {
        cout << "Graph discontinuity" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}

Kruskal

前置：并查集（DSU）

Kruskal 求最小生成树，ans：最小生成树的大小，若 cnt < n - 1 该图不连通。


xxxxxxxxxx
void solve()
{
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    vector<array<int, 3>> g(m);
    for (int i = 0; i < m; i++)
    {
        cin >> g[i][1] >> g[i][2] >> g[i][0];
    }
    sort(g.begin(), g.end());
    int cnt = 0, ans = 0;
    for (auto [w, u, v] : g)
    {
        if (dsu.same(u, v)) continue;
        ans += w;
        dsu.merge(u, v);
        if (++cnt == n - 1) break;
    }
    if (cnt < n - 1)
    {
        cout << "Graph discontinuity" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}

6. 二分图

$G$ $n$ $m$ $k$ ，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。

匈牙利算法求二分图最大匹配的边数：ans


xxxxxxxxxx
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> g[n + m + 1], vis(n + m + 1), match(n + m + 1);
    for (int i = 0; i < k; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    function<bool(int, int)> dfs = [&](int x, int tag) -> bool {
        if (vis[x] == tag) return false;
        vis[x] = tag;
        for (auto p : g[x])
        {
            if (match[p] == 0 or dfs(match[p], tag))
            {
                match[p] = x;
                return true;
            }
        }
        return false;
    };
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += dfs(i, i);
    }
    cout << ans << endl;
}

v. 字符串

1. 字符串哈希 String Hash

Hash sh(s)：初始化字符串 s 的所有区间的哈希值，模数 hmod 默认为随机数，可自定义
sh.get(l,r)：字符串 s 的 [l,r] 区间的哈希值


xxxxxxxxxx
const int hmod = 1e9 + randl() % 10000;
struct Hash {
    vector<int> h, p;
    Hash(string s)
    {
        h.resize(s.size() + 1);
        p.resize(s.size() + 1);
        p[0] = 1;
        for (int i = 1; i <= s.size(); i++)
        {
            h[i] = (h[i - 1] * 13331 + s[i - 1]) % hmod;
            p[i] = p[i - 1] * 13331 % hmod;
        }
    }
    int get(int l, int r)
    {
        return (h[r] - h[l - 1] * p[r - l + 1] % hmod + hmod) % hmod;
    }
};

2. 前缀函数 KMP

$n$ $s$ 前缀函数 $n$ $\pi$ $\pi[i]$ $s[0\dots i]$ $\pi[0]=0$ 。

KMP(s)：生成字符串 s 的 pi 数组


xxxxxxxxxx
vector<int> KMP(string s)
{
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

3. Z 函数拓展 KMP

$n$ $s$ $z[i]$ $s$ $s[i,n-1]$ $s[i]$ $z$ $s$ Z 函数 $z[0] = n$ 。

Z(s)：生成字符串 s 的 Z 数组


xxxxxxxxxx
vector<int> Z(string s)
{
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++)
    {
        if (i <= r and z[i - l] < r - i + 1)
        {
            z[i] = z[i - l];
        }
        else
        {
            z[i] = max(0LL, r - i + 1);
            while (i + z[i] < n and s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    z[0] = n;
    return z;
}

4. 最长回文串 Manacher

$i = 0 \dots n - 1$ $d_1[i]$ $d_2[i]$ $i$ $i-1$ $i$ 之间为中心长度为偶数的回文串个数（最长回文串的半径长度）

Manacher1(s)：求字符串 s 的 d1[] 数组
Manacher2(s)：求字符串 s 的 d2[] 数组


xxxxxxxxxx
vector<int> Manacher1(string s)
{
    int n = s.size();
    vector<int> d1(n);
    for (int i = 0, l = 0, r = -1; i < n; i++)
    {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (0 <= i - k and i + k < n and s[i - k] == s[i + k])
        {
            k++;
        }
        d1[i] = k--;
        if (i + k > r)
        {
            l = i - k;
            r = i + k;
        }
    }
    return d1;
}
vector<int> Manacher2(string s)
{
    int n = s.size();
    vector<int> d2(n);
    for (int i = 0, l = 0, r = -1; i < n; i++)
    {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k])
        {
            k++;
        }
        d2[i] = k--;
        if (i + k > r)
        {
            l = i - k - 1;
            r = i + k;
        }
    }
    return d2;
}

5. 后缀数组 SA

$S$ $i$ 的后缀记为 sa[i]。

$i$ $i-1$ 的后缀，把二者的最长公共前缀的长度记为 height[i] ，规定 height[0]=0 。

SA sa(s)：初始化字符串 s 的 sa.sa[] 数组和 sa.height[] 数组


xxxxxxxxxx
struct SA {
    vector<int> sa, rk, height;
    SA(string s)
    {
        int n = s.size();
        sa.resize(n);
        height.resize(n);
        rk.resize(n);
        iota(sa.begin(), sa.end(), 0);
        sort(sa.begin(), sa.end(), [&](int a, int b) { return s[a] < s[b]; });
        for (int i = 1; i < n; ++i) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        int k = 1;
        vector<int> tmp, cnt(n);
        while (rk[sa[n - 1]] < n - 1)
        {
            tmp.clear();
            for (int i = 0; i < k; ++i) tmp.push_back(n - k + i);
            for (int i : sa) if (i >= k) tmp.push_back(i - k);
            fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; ++i) ++cnt[rk[i]];
            for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i) sa[--cnt[rk[tmp[i]]]] = tmp[i];
            swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; ++i) rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] or sa[i - 1] + k == n or tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            k *= 2;
        }
        for (int i = 0, j = 0; i < n; ++i)
        {
            if (rk[i] == 0)
            {
                j = 0;
            }
            else
            {
                for (j -= j > 0; i + j < n and sa[rk[i] - 1] + j < n and s[i + j] == s[sa[rk[i] - 1] + j];) ++j;
                height[rk[i]] = j;
            }
        }
    }
};

6. 字典树 Trie

字符串字典树

Trie trie：初始化空字典树
trie.insert(s)：插入字符串 s
trie.query(s)：查询字符串 s 作为前缀出现的次数


xxxxxxxxxx
struct Trie {
    vector<array<int, 65>> t;
    vector<int> sum;
    Trie()
    {
        t.resize(1);
        sum.push_back(0);
    }
    int getnum(char x)
    {
        if (x >= 'A' and x <= 'Z') return x - 'A';
        else if (x >= 'a' and x <= 'z') return x - 'a' + 26;
        else return x - '0' + 52;
    }
    void insert(string s)
    {
        int p = 0;
        for (char x : s)
        {
            int c = getnum(x);
            if (not t[p][c])
            {
                t[p][c] = t.size();
                t.resize(t.size() + 1);
                sum.push_back(0);
            }
            p = t[p][c];
            sum[p]++;
        }
    }
    int query(string s)
    {
        int p = 0;
        for (char x : s)
        {
            int c = getnum(x);
            if (not t[p][c])
            {
                return 0;
            }
            p = t[p][c];
        }
        return sum[p];
    }
};

0-1 字典树

Trie trie：初始化空字典树
trie.insert(x)：插入数字 x
trie.query(x)：查询与 x 异或最大的数和 x 的异或值


xxxxxxxxxx
struct Trie {
    vector<array<int, 2>> t;
    Trie()
    {
        t.push_back({0, 0});
    }
    void insert(int x)
    {
        int p = 0;
        for (int i = 30; i >= 0; i--)
        {
            int c = x >> i & 1;
            if (not t[p][c])
            {
                t[p][c] = t.size();
                t.push_back({0, 0});
            }
            p = t[p][c];
        }
    }
    int query(int x)
    {
        int p = 0, res = 0;
        for (int i = 30; i >= 0; i--)
        {
            int c = x >> i & 1;
            if (t[p][not c])
            {
                res += 1 << i;
                p = t[p][not c];
            }
            else
            {
                p = t[p][c];
            }
        }
        return res;
    }
};

7. Lyndon 分解

定义一个串是 Lyndon 串，当且仅当这个串的最小后缀就是这个串本身。

$s$ $s=w_1w_2\cdots w_k$ $w_i$ $w_1\ge w_2\ge\cdots\ge w_k$ 。可以发现，这样的分解存在且唯一。

Duval(s)：求字符串 s 的 Lyndon分解方案


xxxxxxxxxx
vector<string> Duval(string s)
{
    int n = s.size(), i = 0;
    vector<string> fact;
    while (i < n)
    {
        int j = i + 1, k = i;
        while (j < n and s[k] <= s[j])
        {
            if (s[k] < s[j]) k = i;
            else k++;
            j++;
        }
        while (i <= k)
        {
            fact.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return fact;
}

8. 最小表示法

$S$ $S$ 循环同构的所有字符串中字典序最小的字符串。

mincyclic(s)：求字符串 s 的最小表示


xxxxxxxxxx
string mincyclic(string s)
{
    s += s;
    int n = s.size();
    int i = 0, ans = 0;
    while (i < n / 2)
    {
        ans = i;
        int j = i + 1, k = i;
        while (j < n and s[k] <= s[j])
        {
            if (s[k] < s[j]) k = i;
            else k++;
            j++;
        }
        while (i <= k) i += j - k;
    }
    return s.substr(ans, n / 2);
}

9. AC 自动机 Aho-Corasick

$S$ $n$ $T_{1 \sim n}$ $T_i$ $S$ 中出现的次数。AC 开始时已初始化且只能处理一次。

AC.insert(s,i)：插入第 i 个模式串 s
AC.process(s)：处理文本串 s
AC.res(i)：第 i 个模式串的出现次数


xxxxxxxxxx
const int N = 2e6 + 5;
struct {
    struct {
        int son[26], ans, fail, idx;
    } tr[N];
    int tot, idx[N], ans[N], pidx;
    vector<int> g[N];
    void insert(string s, int id)
    {
        int u = 0;
        for (int c : s)
        {
            if (not tr[u].son[c - 'a']) tr[u].son[c - 'a'] = ++tot;
            u = tr[u].son[c - 'a'];
        }
        if (not tr[u].idx) tr[u].idx = ++pidx;
        idx[id] = tr[u].idx;
    }
    void build()
    {
        queue<int> q;
        for (int i = 0; i < 26; i++)
        {
            if (tr[0].son[i])
            {
                q.push(tr[0].son[i]);
                g[0].push_back(tr[0].son[i]);
            }
        }
        while (not q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u].son[i])
                {
                    tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                    g[tr[tr[u].fail].son[i]].push_back(tr[u].son[i]);
                    q.push(tr[u].son[i]);
                }
                else tr[u].son[i] = tr[tr[u].fail].son[i];
            }
        }
    }
    void dfs(int u)
    {
        for (int v : g[u])
        {
            dfs(v);
            tr[u].ans += tr[v].ans;
        }
        ans[tr[u].idx] = tr[u].ans;
    }
    void process(string s)
    {
        build();
        int u = 0;
        for (int c : s)
        {
            u = tr[u].son[c - 'a'];
            tr[u].ans++;
        }
        dfs(0);
    }
    int res(int i)
    {
        return ans[idx[i]];
    }
} AC;

vi. 动态规划

1. 最长上升子序列 LIS

LIS(a)：返回最长上升子序列的长度（若是严格上升子序列则 upper_bound 改为 lower_bound）


xxxxxxxxxx
int LIS(vector<int> a)
{
    int n = a.size();
    vector<int> f(n, INT_MAX);
    for (int i = 0; i < n; i++)
    {
        *upper_bound(f.begin(), f.end(), a[i]) = a[i];
    }
    int ret = 0;
    while (ret < n and f[ret] < INT_MAX)
        ret++;
    return ret;
}

2. 最长公共子序列 LCS

$a$ $b$ 都是排列且长度相等时可使用此方法

前置：最长上升子序列（LIS）

LCS(a,b)：返回最长公共子序列的长度


xxxxxxxxxx
int LCS(vector<int> a, vector<int> b)
{
    int n = a.size();
    vector<int> c(n + 1), d(n);
    for (int i = 0; i < n; i++)
    {
        c[a[i]] = i + 1;
    }
    for (int i = 0; i < n; i++)
    {
        d[i] = c[b[i]];
    }
    return LIS(d);
}

3. 最长公共上升子序列 LCIS

求LCIS长度：LCIS(a,b)：返回最长公共上升子序列的长度


xxxxxxxxxx
int LCIS(vector<int> a, vector<int> b)
{
    int n = a.size(), m = b.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (a[i - 1] == b[j - 1])
                f[i][j] = max(f[i][j], x + 1);
            if (b[j - 1] < a[i - 1])
                x = max(x, f[i][j]);
        }
    }
    return *max_element(f[n].begin(), f[n].end());
}

vii. 几何

1. 二维计算几何基础

这里的 Z 是用于坐标的某种类型，通常是 int（已定义为 long long），double 或 long double 。

point 类型可以和 point 类型进行加减运算，和 Z 类型进行乘除运算。

point a(x,y) $\vec a=(x,y)$
point(x,y)(point){x,y} $(x,y)$
dot(a,b) $\vec a$ $\vec b$ 的点积
norm(a) $\vec a$ 的模方
abs(a) $\vec a$ 的 绝对值（长度）
proj(a,b) $\vec a$ $\vec b$ 的投影
angle(a,b) $\vec a$ $\vec b$ 的夹角
cross(a,b) $\vec a$ $\vec b$ 的叉积
dis(a,b,c) $\vec c$ $(\vec b-\vec a)$ 的距离
intersect(a1,d1,a2,d2) $(\vec a_1-\vec d_1)$ $(\vec a_2-\vec d_2)$ 的交点


xxxxxxxxxx
#define Z long long
struct point {
    Z x, y;
    point() {}
    point(Z x, Z y): x(x), y(y) {}
    point& operator+=(const point &t) {
        x += t.x;
        y += t.y;
        return *this;
    }
    point& operator-=(const point &t) {
        x -= t.x;
        y -= t.y;
        return *this;
    }
    point& operator*=(Z t) {
        x *= t;
        y *= t;
        return *this;
    }
    point& operator/=(Z t) {
        x /= t;
        y /= t;
        return *this;
    }
    point operator+(const point &t) const {
        return point(*this) += t;
    }
    point operator-(const point &t) const {
        return point(*this) -= t;
    }
    bool operator==(const point &t) const {
        return x == t.x and y == t.y;
    }
    bool operator<(const point &t) const {
        return x == t.x ? y < t.y : x < t.x;
    }
    point operator*(Z t) const {
        return point(*this) *= t;
    }
    point operator/(Z t) const {
        return point(*this) /= t;
    }
};
point operator*(Z a, point b) {
    return b * a;
}
Z dot(point a, point b) {
    return a.x * b.x + a.y * b.y;
}
Z norm(point a) {
    return dot(a, a);
}
double abs(point a) {
    return sqrt(norm(a));
}
double proj(point a, point b) {
    return dot(a, b) / abs(b);
}
double angle(point a, point b) {
    return acos(dot(a, b) / abs(a) / abs(b));
}
Z cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
double dis(point a, point b, point c) {
    return fabs(cross(c - a, b - a) / abs(b - a));
}
point intersect(point a1, point d1, point a2, point d2) {
    return a1 + cross(a2 - a1, d2) / cross(d1, d2) * d1;
}

2. 多边形的周长与面积

前置：二维计算几何基础（point）

Pick 定理

平面上以整点为顶点的简单多边形的面积 = 边上的点数 / 2 + 内部的点数 - 1 。

多边形求周长

circum(a)：多边形 a 的周长


xxxxxxxxxx
double circum(vector<point> a)
{
    double res = 0;
    for (int i = 0; i < a.size(); i++)
    {
        point p = i ? a[i - 1] : a.back();
        point q = a[i];
        res += abs(p - q);
    }
    return res;
}

三角形求有向面积

area(p1,p2,p3)：三角形 p1,p2,p3 的面积
signedarea(p1,p2,p3)：三角形 p1,p2,p3 的有向面积（顺时针为负，逆时针为正）


xxxxxxxxxx
double signedarea(point p1, point p2, point p3)
{
    return cross(p2 - p1, p3 - p2) / 2.0;
}
double area(point p1, point p2, point p3)
{
    return fabs(signedarea(p1, p2, p3));
}

多边形求有向面积

area(a)：多边形 a 的面积
signedarea(a)：多边形 a 的有向面积（同三角形有向面积，顺时针为负，逆时针为正）


xxxxxxxxxx
double signedarea(vector<point> a)
{
    double res = 0;
    for (int i = 0; i < a.size(); i++)
    {
        point p = i ? a[i - 1] : a.back();
        point q = a[i];
        res += (p.x - q.x) * (p.y + q.y);
    }
    return res / 2.0;
}
double area(vector<point> a)
{
    return fabs(signedarea(a));
}

3. 凸包

前置：二维计算几何基础（point）

凸多边形 $[0,\pi]$ 范围内的 简单多边形。

凸包：在平面上能包含所有给定点的周长最小的凸多边形叫做凸包。

Andrew 算法求凸包

Andrew(a)：点集 a 的凸包


xxxxxxxxxx
vector<point> Andrew(vector<point> a)
{
    vector<int> s(1), vis(a.size());
    sort(all(a));
    for (int i = 1; i < a.size(); i++)
    {
        while (s.size() >= 2 and cross(a[s.back()] - a[s[s.size() - 2]], a[i] - a[s.back()]) <= 0)
        {
            vis[s.back()] = 0;
            s.pop_back();
        }
        vis[i] = 1;
        s.push_back(i);
    }
    int tmp = s.size();
    for (int i = a.size() - 2; i >= 0; i--)
    {
        if (not vis[i])
        {
            while (s.size() > tmp and cross(a[s.back()] - a[s[s.size() - 2]], a[i] - a[s.back()]) <= 0)
            {
                vis[s.back()] = 0;
                s.pop_back();
            }
            vis[i] = 1;
            s.push_back(i);
        }
    }
    vector<point> ret;
    for (int i : s)
    {
        ret.push_back(a[i]);
    }
    return ret;
}

闵可夫斯基和判断点是否在凸包中

$P,Q$ $q$ $Q$ ，问每次移动后两凸包是否有交点。

Minkowski(a,b)：点集 a 和点集 b 的闵可夫斯基和
rev(a)：将点集 a 对原点对称
isin(i)：二分判断点 i 是否在凸包 c 中


xxxxxxxxxx
vector<point> Minkowski(vector<point> a, vector<point> b)
{
    vector<point> c{a[0] + b[0]};
    for (int i = 0; i < a.size() - 1; i++)
    {
        a[i] = a[i + 1] - a[i];
    }
    for (int i = 0; i < b.size() - 1; i++)
    {
        b[i] = b[i + 1] - b[i];
    }
    a.pop_back();
    b.pop_back();
    int i = 0, j = 0;
    while (i < a.size() and j < b.size())
    {
        if (cross(a[i], b[j]) > 0)
            c.push_back(c.back() + a[i++]);
        else
            c.push_back(c.back() + b[j++]);
    }
    while (i < a.size())
        c.push_back(c.back() + a[i++]);
    while (j < b.size())
        c.push_back(c.back() + b[j++]);
    c.pop_back();
    return c;
}
vector<point> rev(vector<point> a)
{
    for (auto &p : a)
    {
        p *= -1;
    }
    return a;
}
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<point> a(n), b(m);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i].x >> b[i].y;
    }
    a = Andrew(a);
    b = Andrew(rev(b));
    vector<point> c = Minkowski(a, b);
    auto isin = [&](point i) -> bool {
        int sz = c.size() - 1;
        if (cross(i - c[0], c[1] - c[0]) > 0 or cross(c[sz] - c[0], i - c[0]) > 0)
            return 0;
        int l = 1, r = sz - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (cross(c[mid] - c[0], i - c[0]) >= 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if (r >= sz or r <= 0)
            return 0;
        return cross(c[r + 1] - c[r], i - c[r]) >= 0;
    };
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        cout << isin(point(x, y)) << endl;
    }
}

4. 旋转卡壳 —— 求凸包直径

前置：二维计算几何基础（point）

凸包直径，即凸包上各点的平面最远点对的距离。

需要提前引入 Andrew(a) 求凸包
longest(Andrew(a))：对点集 a 求凸包直径


xxxxxxxxxx
double longest(vector<point> a)
{
    if (a.size() <= 3)
        return abs(a[1] - a[0]);
    double ret = 0;
    for (int i = 0, j = 0; i < a.size() - 1; i++)
    {
        while (dis(a[i], a[i + 1], a[j]) <= dis(a[i], a[i + 1], a[(j + 1) % a.size()]))
        {
            j = (j + 1) % a.size();
        }
        ret = max(ret, max(abs(a[i] - a[j]), abs(a[i + 1] - a[j])));
    }
    return ret;
}

viii. 代数

$n$ $F(x)$ $n+1$ $m$ $G(x)$ $m+1$ ），系数从低到高。

$F(x)$ $G(x)$ $F(x) \cdot G(x)$ 的系数）。

1. 快速傅里叶变换 FFT

multiply(f,g)：对多项式 f[]g[] $n+m+1$ ）


xxxxxxxxxx
#define cd complex<double>
const double PI = acos(-1);
void FFT(vector<cd> &a, bool invert)
{
    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 <<= 1)
    {
        double ang = 2 * PI / len * (invert ? -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 (invert)
    {
        for (cd &x : a) x /= n;
    }
}
vector<int> multiply(vector<int> &a, vector<int> &b)
{
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    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<int> result(n);
    for (int i = 0; i < n; i++) result[i] = round(fa[i].real());
    result.resize(a.size() + b.size() - 1);
    return result;
}

2. 快速数论变换 NTT

前置：快速幂（qpow）

模数意义下求卷积， $998244353$ ！

multiply(f,g)：对多项式 f[]g[] $n+m+1$ ）


xxxxxxxxxx
const int mod = 998244353, modg = 3;
void NTT(vector<int> &a, bool invert)
{
    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 <<= 1)
    {
        int wlen = qpow(modg, (mod - 1) / len);
        if (invert) wlen = qpow(wlen);
        for (int i = 0; i < n; i += len)
        {
            int w = 1;
            for (int j = 0; j < len / 2; j++)
            {
                int u = a[i + j];
                int v = a[i + j + len / 2] * w % mod;
                a[i + j] = (u + v) % mod;
                a[i + j + len / 2] = (u - v + mod) % mod;
                w = w * wlen % mod;
            }
        }
    }
    if (invert)
    {
        int ni = qpow(n);
        for (int &x : a) x = x * ni % mod;
    }
}
vector<int> multiply(vector<int> &a, vector<int> &b)
{
    vector<int> fa(a), fb(b);
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n);
    fb.resize(n);
    NTT(fa, false);
    NTT(fb, false);
    for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % mod;
    NTT(fa, true);
    fa.resize(a.size() + b.size() - 1);
    return fa;
}

3. 行列式

高斯消元

给定一个线性方程组，对其求解。

$\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$

Gauss(a,ans)：输入行列式矩阵 a ，其中最后一列是 b ，答案保存在 ans 中，并返回解的数量（ 0、1、无穷（用 2 表示））


xxxxxxxxxx
const double eps = 1e-9;
int Gauss(vector<vector<double>> a, vector<double> &ans)
{
    int n = a.size(), m = a[0].size() - 1;
    vector<int> where(m, -1);
    for (int col = 0, row = 0; col < m and row < n; ++col)
    {
        int sel = row;
        for (int i = row; i < n; ++i)
            if (abs(a[i][col]) > abs(a[sel][col]))
                sel = i;
        if (abs(a[sel][col]) < eps)
            continue;
        for (int i = col; i <= m; ++i)
            swap(a[sel][i], a[row][i]);
        where[col] = row;
        for (int i = 0; i < n; ++i)
            if (i != row)
            {
                double c = a[i][col] / a[row][col];
                for (int j = col; j <= m; ++j)
                    a[i][j] -= a[row][j] * c;
            }
        ++row;
    }
    ans.assign(m, 0);
    for (int i = 0; i < m; ++i)
        if (where[i] != -1)
            ans[i] = a[where[i]][m] / a[where[i]][i];
    for (int i = 0; i < n; ++i)
    {
        double sum = 0;
        for (int j = 0; j < m; ++j)
            sum += ans[j] * a[i][j];
        if (abs(sum - a[i][m]) > eps)
            return 0;
    }
    for (int i = 0; i < m; ++i)
        if (where[i] == -1)
            return 2;
    return 1;
}

行列式求值

$n$ $A$ $|A|$ 。

DetGauss(a)：求解行列式 a


xxxxxxxxxx
const double eps = 1e-9;
double DetGauss(vector<vector<double>> a)
{
    int n = a.size();
    double det = 1;
    for (int i = 0; i < n; ++i)
    {
        int k = i;
        for (int j = i + 1; j < n; ++j)
            if (abs(a[j][i]) > abs(a[k][i]))
                k = j;
        if (abs(a[k][i]) < eps)
        {
            det = 0;
            break;
        }
        swap(a[i], a[k]);
        if (i != k)
            det = -det;
        det *= a[i][i];
        for (int j = i + 1; j < n; ++j)
            a[i][j] /= a[i][i];
        for (int j = 0; j < n; ++j)
            if (j != i and abs(a[j][i]) > eps)
                for (int k = i + 1; k < n; ++k)
                    a[j][k] -= a[i][k] * a[j][i];
    }
    return det;
}

4. 矩阵

matrix a(n) $n \times n$ $+ - \times$ ” 运算符
a.pow(x)：矩阵快速幂求 a 的 x 次方
a.read()：读入矩阵
a.print()：输出矩阵


xxxxxxxxxx
struct matrix {
    int n;
    vector<vector<int>> a;
    matrix(int x)
    {
        a.resize(x, vector<int>(x));
        n = x;
    }
    matrix operator-(const matrix &t) const {
        matrix res(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                res.a[i][j] = (a[i][j] - t.a[i][j] + mod) % mod;
        return res;
    }
    matrix operator+(const matrix &t) const {
        matrix res(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                res.a[i][j] = (a[i][j] + t.a[i][j]) % mod;
        return res;
    }
    matrix operator*(const matrix &t) const {
        matrix res(n);
        int r;
        for (int i = 0; i < n; ++i)
        {
            for (int k = 0; k < n; ++k)
            {
                r = a[i][k];
                for (int j = 0; j < n; ++j)
                    res.a[i][j] = (res.a[i][j] + t.a[k][j] * r % mod) % mod;
            }
        }
        return res;
    }
    matrix pow(int x) const {
        matrix res(n), bas(n);
        for (int i = 0; i < n; ++i)
            res.a[i][i] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                bas.a[i][j] = a[i][j] % mod;
        while (x)
        {
            if (x & 1)
                res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
    void print()
    {
        for (int i = 0; i < n; ++i, cout << endl)
            for (int j = 0; j < n; ++j)
                cout << a[i][j] << ' ';
    }
    void read()
    {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
    }
};

算法模板 SFMB.XYZ

全网最好的ACM/ICPC零基础算法模板，代码简短，封装完美，解释清晰，通用性强。

只包含常用算法，适合 Rating 1200 ~ 2000 。

版本

许可

资源

目录

i. 初始化

1. Vim for Linux 快速配置

2. C++ 初始文件

3. C++ 火车头编译优化

4. 随机数

生成 64 位随机数（初始文件默认已包含）

卡时

自定义 unordered_map/unordered_set 防卡哈希

ii. 数论

1. 快速幂

2. 快速平方根

3. 扩展欧几里得

4. 逆元与组合数

扩展欧几里得求单个数字的逆元

线性求逆元和组合数

5. 素数测试与因式分解

Miller Rabin 判断素数

Pollard Rho 分解因数

6. 欧拉筛法

7. 扩展中国剩余定理

8. 数论分块

iii. 数据结构

1. 并查集 DSU

2. ST 表

3. 树状数组

单点修改，区间求和 求逆序对

二维树状数组

4. 线段树

普通线段树 单点修改，区间查询

懒标记线段树 区间加，区间乘，区间赋值，区间求和

5. 莫队

iv. 图论

1. 最短路

2. 树的直径

3. 最近公共祖先 LCA

4. 拓扑排序

5. 最小生成树 MST

Prim

Kruskal

6. 二分图

v. 字符串

1. 字符串哈希 String Hash

2. 前缀函数 KMP

3. Z 函数 拓展 KMP

4. 最长回文串 Manacher

5. 后缀数组 SA

6. 字典树 Trie

字符串字典树

0-1 字典树

7. Lyndon 分解

8. 最小表示法

9. AC 自动机 Aho-Corasick

vi. 动态规划

1. 最长上升子序列 LIS

2. 最长公共子序列 LCS

3. 最长公共上升子序列 LCIS

vii. 几何

1. 二维计算几何基础

2. 多边形的周长与面积

Pick 定理

多边形求周长

三角形求有向面积

多边形求有向面积

3. 凸包

Andrew 算法 求凸包

闵可夫斯基和 判断点是否在凸包中

4. 旋转卡壳 —— 求凸包直径

viii. 代数

1. 快速傅里叶变换 FFT

2. 快速数论变换 NTT

3. 行列式

高斯消元

行列式求值

单点修改，区间求和求逆序对

普通线段树单点修改，区间查询

懒标记线段树区间加，区间乘，区间赋值，区间求和

3. Z 函数拓展 KMP

Andrew 算法求凸包

闵可夫斯基和判断点是否在凸包中