ICPC 常用算法模板

flowchart LR
ICPC---3["Search"]
ICPC---4["Data Structure"]
ICPC---5["Dynamic Programming"]
ICPC---6["Number Theory、Linear Algebra"]
ICPC---7["Combinatorics、Polynomial"]
ICPC---8["Geometry"]
ICPC---9["String"]
ICPC---10["Graph Theory"]

基本算法

尺取法/双指针

$O (n)$

// 尺取法获取第k近的点下标
void getKth(int k) {
    int l = 1, r = k + 1;
    nxt[1] = k + 1;
    for (int i = 2; i <= n; i++) {
        while (r + 1 <= n && a[i] - a[l] > a[r + 1] - a[i])
            l++, r++;
        if (a[i] - a[l] < a[r] - a[i])
            nxt[i] = r;
        else
            nxt[i] = l;
    }
}

void add(int x) { if (++mp[a[x]] == 1) cnt++; }
void del(int x) { if (--mp[a[x]] == 0) cnt--; }
// 尺取法，f[i] 表示区间 [i, f[i]] 中有k个不同的数
for (int l = 1, r = 1; l <= n; l++) {
    while (cnt < k && r <= n)
        add(r++);
    if (cnt == k)
        f[l] = r - 1;
    else
        f[l] = n + 1;
    del(l);
}

void add(int x) { sum += a[x]; }
void del(int x) { sum -= a[x]; }
sum = 0, res = n + 1;
// 查询满足区间和大于等于 s 的最短区间
for (int l = 1, r = 1; l <= n; l++) {
    while (sum < s && r <= n)
        add(r++);
    if (sum < s)
        break;
    res = min(res, r - l);
    del(l);
}

二分和二分答案

$O (lo g n)$

整数二分

求数列分割点（一半满足一个性质，另一半满足相反的性质，如一半⇐25，另一半>25）

手写二分

auto check = [&](int x) { return x * x <= 25; };
int l = 0, r = 11; // 开区间(l, r)，保证左半为 true，右半为 false
while (r - l > 1) {
    int mid = (l + r) / 2;
    check(mid) ? l = mid : r = mid;
}
cout << r << '\n';
// l : last true
// r : first false

STL二分

// lower_bound(x) => first false mid <x
// upper_bound(x) => first false mid<=x
// lower_bound(x, check) => first false check(mid, x)
// upper_bound(x, check) => first true  check(x, mid)
// 以下为 C++20 后的用法
auto check = [](int x, int v) { return x * x <= v; };
cout << *ranges::lower_bound(ranges::iota_view(1, 11), 25, check) << '\n';

实数二分

求函数的零点

auto check = [&](double x) { return x * x - 2 < 0; };
double l = -1e9, r = 1e9; // 保证左半为 true，右半为 false
for (int t = 1; t <= 100; t++) {
    double mid = (l + r) / 2;
    check(mid) ? l = mid : r = mid;
}
cout << fixed << setprecision(10) << r << '\n';

三分和三分答案

$O (lo g n)$

整数三分

求单峰数列的极值

auto ternary = [&](ll l, ll r) {
    while (r - l > 2) {
        ll m1 = l + (r - l) / 3;
        ll m2 = r - (r - l) / 3;
        calc(m1) > calc(m2) ? r = m2 : l = m1; // 凸函数>，凹函数<，即二阶导数的符号
    }
    return (l + r) / 2;
};

实数三分

求单峰函数的极值

auto ternary = [&](lld l, lld r) {
    for (int t = 1; t <= 100; t++) {
        lld m1 = l + (r - l) / 3;
        lld m2 = r - (r - l) / 3;
        calc(m1) > calc(m2) ? r = m2 : l = m1; // 凸函数>，凹函数<，即二阶导数的符号
    }
    return l;
};

倍增

倍增法有两种主要应用场合，一种是从小区间扩大到大区间（如ST算法、后缀数组等），另一种是从小数值倍增到大数值（快速幂、最近公共祖先等）。

$O (n lo g m)$

// 初始化
int logm = __lg(m);
vector f(n + 1, vector<ll>(logm + 1));
for (int i = 1; i <= n; i++)
    f[i][0] = nxt[i];
for (int t = 1; t <= logm; t++)
    for (int i = 1; i <= n; i++)
        f[i][t] = f[f[i][t - 1]][t - 1];
// 查询
for (int t = logm; t >= 0; t--)
    if (m - (1 << t) >= 0) {
        for (int i = 1; i <= n; i++)
            ans[i] = f[ans[i]][t];
        m -= 1LL << t;
    }

对于已知跳跃次数的倍增，可以使用类似快速幂的写法

vector<ll> f(nxt);
for (; m; m >>= 1) {
    if (m & 1)
        for (int i = 1; i <= n; i++)
            ans[i] = f[ans[i]];
    vector<ll> ff(f);
    for (int i = 1; i <= n; i++)
        f[i] = ff[ff[i]];
}

前缀和与差分

一维

前缀和: $p r_{i} = p r_{i - 1} + a_{i}$

差分: $d f_{i} = a_{i} - a_{i - 1}$

差分区间修改:

add (l, r, k) \Rightarrow {d f_{l} \leftarrow d f_{l} + k d f_{r + 1} \leftarrow d f_{r + 1} - k

二维

前缀和: $p r_{i, j} = p r_{i, j - 1} + p r_{i - 1, j} - p r_{i - 1, j - 1} + a_{i, j}$

差分: $d f_{i, j} = a_{i, j} - a_{i - 1, j} - a_{i, j - 1} + a_{i - 1, j - 1}$

差分区间修改:

add ((x_{1}, y_{1}), (x_{2}, y_{2}), k) \Rightarrow ⎩ ⎨ ⎧ d f_{x_{1}, y_{1}} \leftarrow d f_{x_{1}, y_{1}} + k d f_{x_{1}, y_{2} + 1} \leftarrow d f_{x_{1}, y_{2} + 1} - k d f_{x_{2} + 1, y 1} \leftarrow d f_{x_{2} + 1, y 1} - k d f_{x_{2} + 1, y_{2} + 1} \leftarrow d f_{x_{2} + 1, y_{2} + 1} + k

树上

前缀和: 设 $p r_{i}$ 表示结点 $i$ 到根节点的权值总和。

差分:

若是点权, $x, y$ 路径上的和为 $p r_{x} + p r_{y} - p r_{l c a} - p r_{f a (l c a)}$ 。
若是边权, $x, y$ 路径上的和为 $p r_{x} + p r_{y} - 2 \cdot p r_{l c a}$ 。

差分修改:

对树上的一些路径 $δ (s_{1}, t_{1})$ , $δ (s_{2}, t_{2})$ , $δ (s_{3}, t_{3}) \dots$ 进行访问，问一条路径 $δ (s, t)$ 上的点被访问的次数。

对于一次 $δ (s, t)$ 的访问

点差分:

⎩ ⎨ ⎧ d_{s} \leftarrow d_{s} + 1 d_{l c a} \leftarrow d_{lca} - 1 d_{t} \leftarrow d_{t} + 1 d_{f a (l c a)} \leftarrow d_{f a (l c a)} - 1

边差分:

⎩ ⎨ ⎧ d_{s} \leftarrow d_{s} + 1 d_{t} \leftarrow d_{t} + 1 d_{l c a} \leftarrow d_{l c a} - 2

离散化

$a {1, 10, 100, 50} \to a {1, 2, 4, 3}, d {1, 10, 50, 100}$

将 $a_{i}$ 数组离散化，逆映射保存在 $d_{i}$ 中。 $d : a_{i}^{'} \to a_{i}$

$O (n lo g n)$

int compress(vector<pii> &a, vector<int> &d) {
    for (auto &[l, r] : a)
        d.push_back(l), d.push_back(r);
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    auto get = [&d](int x) { return lower_bound(d.begin(), d.end(), x) - d.begin(); };
    for (auto &[l, r] : a)
        l = get(l), r = get(r);
    return d.size();
}
// 离散后修改
vector<int> f(compress(a, d));
for (auto &[l, r] : a)
    fill(f.begin() + l, f.begin() + r, 1);
// 逆映射到离散前的原数值
for (int i = 0; i < f.size() - 1; i++)
    if (f[i])
        ans += d[i + 1] - d[i];

二维的可以对两个维度分别离散化

排列和组合枚举

全排列

$O (n!)$

vector<int> a(n);
iota(a.begin(), a.end(), 1);
do {
    // 判断排列的合法性
} while (next_permutation(a.begin(), a.end()));

组合

$O (2^{n})$

int n = 4;
vector<int> a(n + 1);
for (int i = 0; i < (1 << n); i++) {
    int cnt = __builtin_popcount(i);
    a[cnt]++;
    for (int j = 0; j < n; j++)
        if (i >> j & 1) {
            // do something
        }
}
for (int i = 0; i <= n; i++)
    cout << a[i] << " ";

数据结构

哈希表

防止卡哈希冲突的哈希函数

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_set<int, custom_hash> st;

单调栈

维护某值的左边第一大，右边第一小 $O (n)$

stack<int> s;
for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] < a[i]) { // 单调递减栈
        // 此时a[i]是第一个 > a[s.top()]的数
        s.pop();
    }
    // 此时a[i]左边有 s.size() 个 >= a[i] 的数
    // 此时a[i]是第一个 <= a[s.top()]的数
    s.push(i);
}

单调队列

维护k区间最值 $O (n)$

deque<int> q;
for (int i = 0; i < n; i++) {
    while (!q.empty() && i - q.front() >= k) // 调整覆盖范围
        q.pop_front();
    while (!q.empty() && a[q.back()] < a[i]) // 保持单调递减
        q.pop_back();
    q.push_back(i);
    if (i >= k - 1)
        cout << a[q.front()] << endl; // 区间[i-k+1,i]最大值
}

ST表/稀疏表/Sparse Table

维护区间最值

预处理: $O (n lo g n)$

查询: $O (1)$

template <typename T, T (*op)(T, T)> struct SparseTable {
    int n, logn;
    std::vector<std::vector<T>> dat;
    SparseTable(const std::vector<T> &v) : n(v.size()), logn(std::__lg(n) + 1), dat(n + 1, std::vector<T>(logn + 1)) {
        for (int i = 1; i <= n; i++)
            dat[i][0] = v[i - 1];
        for (int j = 1; j <= logn; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dat[i][j] = op(dat[i][j - 1], dat[i + (1 << (j - 1))][j - 1]);
    }
    T query(int l, int r) {
        int s = std::__lg(r - l + 1);
        return op(dat[l][s], dat[r - (1 << s) + 1][s]);
    }
};
int maxn(int a, int b) { return a > b ? a : b; }

并查集

维护集合的合并与查询是否相交

初始化: $O (n)$

查询/合并: $O (lo g n)$

struct DSU {
    vector<int> p, sz;
    DSU(int n = 1e6) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    void merge(int x, int y) { x = find(x), y = find(y), (x != y ? p[y] = x, sz[x] += sz[y] : 0); }
    int size(int x) { return sz[find(x)]; }
};

树状数组

维护具有差分性质的序列，维护序列的前缀和信息

单点修改: $O (lo g n)$

区间查询: $O (lo g n)$

template <typename T> struct BIT {
    int n;
    vector<T> tr;
    BIT(int _n = 0) : n(_n), tr(n + 1, T()) {}
    inline int lowbit(int x) { return x & -x; }
    void add(int i, T x) {
        for (assert(i > 0); i <= n; i += lowbit(i))
            tr[i] += x;
    }
    T ask(int i) {
        T res = 0;
        for (i = min(i, n); i; i -= lowbit(i))
            res += tr[i];
        return res;
    }
    T query(int l, int r) { return ask(r) - ask(l - 1); }
    int kth(int k) {
        int l = 0, r = n + 1, mid;
        while (r - l > 1)
            ask(mid = (l + r) >> 1) < k ? l = mid : r = mid;
        return r;
    }
};

权值树状数组

struct BIT {
    int n;
    vector<int> tr;
    BIT(int _n = 0) : n(_n), tr(n + 1, 0) {}
    inline int lowbit(int x) { return x & -x; }
    void add(int i, int x) {
        for (assert(i > 0); i <= n; i += lowbit(i))
            tr[i] += x;
    }
    int ask(int i) {
        int res = 0;
        for (i = min(i, n); i; i -= lowbit(i))
            res += tr[i];
        return res;
    }
    int rank(int x) { return 1 + ask(x - 1); } // x的排名
    int kth(int k) {                           // 第k小的数
        int x = 0;
        for (int t = 1 << __lg(n); t; t >>= 1)
            if (x + t <= n && tr[x + t] < k) {
                k -= tr[x + t];
                x += t;
            }
        return x + 1;
    }
    int pre(int x) { return kth(rank(x) - 1); } // x的前缀
    int nxt(int x) { return kth(rank(x + 1)); } // x的后缀
};

线段树

维护“满足幺半群（封闭性；结合律；单位元）的性质的信息”的序列

如区间和、区间积、区间最大/小值、区间或/与/异或、区间gcd/lcm等可合并信息

zkw线段树

非递归实现，常数小，功能有限。

初始化建树: $O (n)$

单点修改: $O (lo g n)$

区间查询: $O (lo g n)$

template <typename T, T (*op)(T, T), T (*e)()> struct SegmentTree {
    SegmentTree() : SegmentTree(0) {}
    SegmentTree(int n_) : n(2 << __lg(n_ - 1)), info(n << 1, e()) {}
    SegmentTree(const std::vector<T> &v) : SegmentTree(v.size()) {
        copy(v.begin(), v.end(), info.begin() + n);
        for (int p = n - 1; p; p--)
            info[p] = op(info[p << 1], info[p << 1 | 1]);
    }
    void modify(int i, T k) { // update a[i]=k
        for (info[i += n] = k; i; i >>= 1)
            info[i >> 1] = op(info[i], info[i ^ 1]);
    }
    void apply(int i, T k) { // apply a[i] with k
        for (i += n, info[i] = op(info[i], k); i; i >>= 1)
            info[i >> 1] = op(info[i], info[i ^ 1]);
    }
    T query(int i, int j) { // query[i,j)
        T res = e();
        for (i += n, j += n; i < j; i >>= 1, j >>= 1) {
            if (i & 1)
                res = op(res, info[i++]);
            if (j & 1)
                res = op(res, info[--j]);
        }
        return res;
    }
    int n;
    vector<T> info;
};
template <typename T> T op(T a, T b) { return a + b; }
template <typename T> T e() { return 0; }

线段树

结构体实现，可扩展性强；lazy-tag 延迟更新。

维护 operator+ pushup apply pushdown 实现区间信息合并、标记与下传。

初始化建树: $O (n)$

区间修改: $O (lo g n)$

区间查询: $O (lo g n)$

单点修改

template <typename Info> struct SegmentTree {
    int n;
    vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n) : n(n), info(4 << __lg(n)) {}
    SegmentTree(const vector<Info> &a) : SegmentTree(a.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r)
                return void(info[p] = a[l - 1]);
            int m = (l + r) / 2;
            build(p << 1, l, m);
            build(p << 1 | 1, m + 1, r);
            info[p] = info[p << 1] + info[p << 1 | 1];
        };
        build(1, 1, n);
    }
    void modify(int p, int l, int r, int i, const Info &v) {
        if (i < l || r < i)
            return;
        if (l == r)
            return void(info[p] = v);
        int m = (l + r) / 2;
        modify(p << 1, l, m, i, v);
        modify(p << 1 | 1, m + 1, r, i, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int a, int b) {
        if (b < l || r < a)
            return Info();
        if (a <= l && r <= b)
            return info[p];
        int m = (l + r) / 2;
        return rangeQuery(p << 1, l, m, a, b) + rangeQuery(p << 1 | 1, m + 1, r, a, b);
    }
    Info rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
};template <typename Info> struct SegmentTree {
    SegmentTree() : n(0) {}
    SegmentTree(int n_) : n(n_), info(4 << __lg(n)) {}
    SegmentTree(const vector<Info> &a) : SegmentTree(a.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r)
                return void(info[p] = a[l - 1]);
            int m = (l + r) / 2;
            build(p << 1, l, m);
            build(p << 1 | 1, m + 1, r);
            info[p] = info[p << 1] + info[p << 1 | 1];
        };
        build(1, 1, n);
    }
    void modify(int p, int l, int r, int i, const Info &v) {
        if (i < l || r < i)
            return;
        if (l == r)
            return void(info[p] = v);
        int m = (l + r) / 2;
        modify(p << 1, l, m, i, v);
        modify(p << 1 | 1, m + 1, r, i, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    void apply(int p, int l, int r, int i, const Info &v) {
        if (i < l || r < i)
            return;
        if (l == r)
            return void(info[p] += v);
        int m = (l + r) / 2;
        apply(p << 1, l, m, i, v);
        apply(p << 1 | 1, m + 1, r, i, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void apply(int x, const Info &v) { apply(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int a, int b) {
        if (b < l || r < a)
            return Info();
        if (a <= l && r <= b)
            return info[p];
        int m = (l + r) / 2;
        return rangeQuery(p << 1, l, m, a, b) + rangeQuery(p << 1 | 1, m + 1, r, a, b);
    }
    Info query(int x) { return rangeQuery(1, 1, n, x, x); }
    Info rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
    int n;
    vector<Info> info;
};

区间修改

template <typename Info, typename Tag> struct LazySegmentTree {
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_) : n(n_), info(4 << __lg(n)), tag(4 << __lg(n)) {}
    LazySegmentTree(const vector<Info> &a) : LazySegmentTree(a.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r)
                return void(info[p] = a[l - 1]);
            int m = (l + r) / 2;
            build(p << 1, l, m);
            build(p << 1 | 1, m + 1, r);
            info[p] = info[p << 1] + info[p << 1 | 1];
        };
        build(1, 1, n);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (x < l || r < x)
            return;
        if (l == r)
            return void(info[p] = v);
        pushdown(p, l, r);
        int m = (l + r) / 2;
        modify(p << 1, l, m, x, v);
        modify(p << 1 | 1, m + 1, r, x, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    void rangeApply(int p, int l, int r, int a, int b, const Tag &v) {
        if (b < l || r < a)
            return;
        if (a <= l && r <= b)
            return map(p, l, r, v);
        pushdown(p, l, r);
        int m = (l + r) / 2;
        rangeApply(p << 1, l, m, a, b, v);
        rangeApply(p << 1 | 1, m + 1, r, a, b, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void apply(int x, const Tag &v) { rangeApply(1, 1, n, x, x, v); }
    void rangeApply(int a, int b, const Tag &v) { rangeApply(1, 1, n, a, b, v); }
    Info rangeQuery(int p, int l, int r, int a, int b) {
        if (b < l || r < a)
            return Info();
        if (a <= l && r <= b)
            return info[p];
        pushdown(p, l, r);
        int m = (l + r) / 2;
        return rangeQuery(p << 1, l, m, a, b) + rangeQuery(p << 1 | 1, m + 1, r, a, b);
    }
    Info query(int x) { return rangeQuery(1, 1, n, x, x); }
    Info rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
    int n;
    vector<Info> info;
    vector<Tag> tag;
    void map(int p, int l, int r, const Tag &v) {
        info[p].mapping(l, r, v);
        tag[p].composition(l, r, v);
    }
    void pushdown(int p, int l, int r) {
        int m = (l + r) / 2;
        map(p << 1, l, m, tag[p]);
        map(p << 1 | 1, m + 1, r, tag[p]);
        tag[p] = Tag();
    }
};
struct Tag {
    int x;
    void composition(int l, int r, const Tag &v) { x += v.x; }
};
struct Info {
    long long sum = 0;
    void mapping(int l, int r, const Tag &v) { sum += (r - l + 1) * v.x; }
    friend Info operator+(Info a, Info b) { return Info{a.sum + b.sum}; }
};
// void modifty(int a, int b, T k, int p = 1) {
//     if (a <= tr[p].l && tr[p].r <= b)
//         return mark(k, p);
//     pushdown(p);
//     int mid = (tr[p].l + tr[p].r) >> 1;
//     if (a <= mid) modifty(a, b, k, p << 1); // 左半区间与修改区间相交
//     if (b > mid) modifty(a, b, k, p << 1 | 1); // 右半区间与修改区间相交
//     tr[p] = tr[p << 1] + tr[p << 1 | 1];
// }
// Node query(int a, int b, int p = 1) {
//     if (a <= tr[p].l && tr[p].r <= b)
//         return tr[p];
//     pushdown(p);
//     int mid = (tr[p].l + tr[p].r) >> 1;
//     if (b <= mid) return query(a, b, p << 1); // 只有左半区间与查询区间相交
//     else if (a > mid) return query(a, b, p << 1 | 1); // 只有右半区间与查询区间相交
//     else return query(a, b, p << 1) + query(a, b, p << 1 | 1); // (a <= mid < b) 两端区间都与查询区间相交
// }

可持久化线段树/主席树

$O (lo g n)$ 修改和查询

class SegmentTree {
    struct Node {
        int l = 0, r = 0, sum = 0;
    };
    vector<Node> tr;
    vector<int> rt;
    int n, cnt;
    int update(int k, int d, int p, int l, int r) {
        int q = tr.size();
        tr.push_back(tr[p]);
        if (l == r) {
            tr[q].sum += d;
            return q;
        }
        int mid = (l + r) / 2;
        if (k <= mid)
            tr[q].l = update(k, d, tr[p].l, l, mid);
        else
            tr[q].r = update(k, d, tr[p].r, mid + 1, r);
        tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
        return q;
    }
    int kth(int k, int p, int q, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        int x = tr[tr[q].l].sum - tr[tr[p].l].sum;
        if (x >= k)
            return kth(k, tr[p].l, tr[q].l, l, mid);
        else
            return kth(k - x, tr[p].r, tr[q].r, mid + 1, r);
    }
 
  public:
    SegmentTree(int n) : n(n), rt(1), cnt(1), tr(1) {}
    void update(int k, int d) { rt.push_back(update(k, d, rt.back(), 1, n)); }
    int kth(int k, int p, int q) { return kth(k, rt[p - 1], rt[q], 1, n); }
};

分块与莫队算法

分块

$O (n)$ 预处理， $O (n)$ 查询

template <typename T> class Block {
    int n, t, m;
    vector<int> l, r, id;
    vector<T> &v, sum, tag;
    void add(int p, int a, int b, T k) {
        sum[p] += k * (b - a + 1);
        for (int i = a; i <= b; i++)
            v[i] += k;
    }
    T ask(int p, int a, int b) {
        T res = tag[p] * (b - a + 1);
        for (int i = a; i <= b; i++)
            res += v[i];
        return res;
    }
 
  public:
    Block(vector<T> &v) // 1-index
        : n(v.size() - 1), t(sqrt(n)), m(n / t + (n % t > 0)), l(m + 1), r(m + 1), id(n + 1),
          v(v), sum(m + 1), tag(m + 1) {
        for (int i = 1; i <= m; i++) {
            l[i] = (i - 1) * t + 1, r[i] = min(i * t, n);
            for (int j = l[i]; j <= r[i]; j++) {
                sum[i] += v[j];
                id[j] = (j - 1) / t + 1;
            }
        }
    }
    void update(int a, int b, T k) {
        int p = id[a], q = id[b];
        if (p == q) {
            add(p, a, b, k);
        } else {
            for (int i = p + 1; i <= q - 1; i++)
                tag[i] += k;
            add(p, a, r[p], k);
            add(q, l[q], b, k);
        }
    }
    T query(int a, int b) {
        T res = 0;
        int p = id[a], q = id[b];
        if (p == q) {
            res += ask(p, a, b);
        } else {
            for (int i = p + 1; i <= q - 1; i++)
                res += sum[i] + tag[i] * (r[i] - l[i] + 1);
            res += ask(p, a, r[p]);
            res += ask(q, l[q], b);
        }
        return res;
    }
};

二叉搜索树&平衡树

vector平衡树

template <typename T> struct BST {
    vector<T> tr;
    void insert(T x) { tr.insert(lower_bound(tr.begin(), tr.end(), x), x); }
    void erase(T x) { tr.erase(lower_bound(tr.begin(), tr.end(), x)); }
    int rank(T x) { return lower_bound(tr.begin(), tr.end(), x) - tr.begin() + 1; }
    int kth(int x) { return tr.at(x - 1); }
    int pre(int x) { return *prev(lower_bound(tr.begin(), tr.end(), x)); }
    int nxt(int x) { return *upper_bound(tr.begin(), tr.end(), x); }
};

AVL树

#define height(p) (p ? p->_height : 0)
template <typename T> struct BinNode {
    BinNode *_lc, *_rc; // 左右子树
    T _val;             // 键值对
    int _height;        // 高度
    BinNode(T val) : _lc(nullptr), _rc(nullptr), _val(val), _height(1) {}
    int updateHeight() {
        return _height = std::max(height(this->_lc), height(this->_rc)) + 1;
    } // 更新高度
    BinNode *zig() { // 右旋
        if (!_lc)
            return this;
        BinNode *lc = _lc;
        _lc = lc->_rc;
        lc->_rc = this;
        updateHeight();
        lc->updateHeight();
        return lc;
    }
    BinNode *zag() { // 左旋
        if (!_rc)
            return this;
        BinNode *rc = _rc;
        _rc = rc->_lc;
        rc->_lc = this;
        updateHeight();
        rc->updateHeight();
        return rc;
    }
    // 可视化接口
    const BinNode *left() const { return _lc; }
    const BinNode *right() const { return _rc; }
    std::string val() const {
        std::ostringstream ss;
        ss << _val;
        return ss.str();
    }
};
 
template <typename T> class BST {
  public:
    using Node = BinNode<T>;
    BST() : _root(nullptr), _size(0) {}
    Node *search(T val) {
        Node *cur = _root;
        while (cur && val != cur->_val) {
            if (val < cur->_val) {
                cur = cur->_lc;
            } else {
                cur = cur->_rc;
            }
        }
        return cur;
    }
    bool insert(T val) {
        if (search(val)) {
            return false;
        } else {
            _size++;
            _root = add(_root, val);
            return true;
        }
    }
    bool erase(T val) {
        if (search(val)) {
            _root = del(_root, val);
            return true;
        } else {
            return false;
        }
    }
    Node *root() const { return _root; }
 
  protected:
    Node *add(Node *cur, T val) {
        if (!cur) {
            return new Node(val);
        } else {
            if (val < cur->_val)
                cur->_lc = add(cur->_lc, val);
            else
                cur->_rc = add(cur->_rc, val);
            cur->updateHeight();
            return maintain(cur);
        }
    }
    Node *del(Node *cur, T val) {
        if (val < cur->_val)
            cur->_lc = del(cur->_lc, val);
        else if (val > cur->_val)
            cur->_rc = del(cur->_rc, val);
        else
            cur = del(cur);
        if (cur)
            cur->updateHeight();
        return maintain(cur);
    }
    static Node *del(Node *cur) {
        Node *succ = nullptr; // 删除cur后形成子树的根节点
        if (!cur->_lc) {
            succ = cur->_rc;
        } else if (!cur->_rc) {
            succ = cur->_lc;
        } else {
            succ = cur;
            Node *pre = cur;
            for (cur = cur->_rc; cur->_lc; cur = cur->_lc)
                pre = cur;
            (pre == succ ? pre->_rc : pre->_lc) = cur->_rc;
            swap(cur->_val, succ->_val);
        }
        delete cur;
        return succ;
    }
    virtual Node *maintain(Node *cur) { return cur; }
    Node *_root;
    int _size;
};
template <typename T> class AVL : public BST<T> {
  protected:
    BinNode<T> *maintain(BinNode<T> *cur) override {
        if (!cur)
            return nullptr;
        int Lheight = height(cur->_lc);   // 计算出cur左树的高度
        int Rheight = height(cur->_rc);   // 计算出cur右树的高度
        if (abs(Lheight - Rheight) > 1) { // 出现不平衡
            if (Lheight > Rheight) {
                // 计算cur左树的左右子树的高度
                int LLheight = cur->_lc ? height(cur->_lc->_lc) : 0;
                int LRheight = cur->_lc ? height(cur->_lc->_rc) : 0;
                if (LLheight >= LRheight) { // LL型右单旋转
                    cur = cur->zig();
                } else { // LR型左右双旋
                    cur->_lc = cur->_lc->zag();
                    cur = cur->zig();
                }
            } else {
                // 计算cur右树的左右子树的高度
                int RLheight = cur->_rc ? height(cur->_rc->_lc) : 0;
                int RRheight = cur->_rc ? height(cur->_rc->_rc) : 0;
                if (RRheight >= RLheight) { // RR型左单旋转
                    cur = cur->zag();
                } else { // RL型右左双旋
                    cur->_rc = cur->_rc->zig();
                    cur = cur->zag();
                }
            }
        }
        return cur; // 返回调整好的新父节点
    }
};

图论

存图

邻接表/邻接矩阵

using Node = pair<int, int>;
vector<int> G[N];
int G[N][N];
int n, m;
 
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
    G[u][v] = G[v][u] = w;
}
for (int u = 0; u < n; u++)
    for (auto &[v, w] : G[u]) {}
    for (int v = 0; v < n; v++) if (G[u][v]) {}

链式前向星

struct ChainForwardStar {
    using Edge = pair<int, int>;
    vector<int> head, next;
    vector<Edge> edges;
    int E;
    ChainForwardStar(int V = 0) { head.resize(V + 1, -1); }
    void addEdge(int u, int v, int w = 1) {
        edges.push_back({v, w});
        next.push_back(head[u]);
        head[u] = E++;
    }
};
ChainForwardStar G(n);
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G.addEdge(u, v, w);
}
for (int u = 0; u < n; u++)
    for (int i = G.head[u]; ~i; i = G.next[i]) {
        auto &[v, w] = G.edges[i];
        cout << u << " " << v << " " << w << endl;
    }

DFS/BFS

$O (n)$

void dfs(int u) {
    if (vis[u])
        return;
    vis[u] = true;
    for (int v : G[u])
        dfs(v);
}
void bfs(int u) {
    queue<int> Q;
    vis[u] = true;
    Q.push(u);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : G[u])
            if (!vis[v]) {
                vis[v] = true;
                Q.push(v);
            }
    }
}

拓扑排序

$O (n)$

int n;
vector<int> ans;
queue<int> q;
int indeg[N];
 
bool tsort() {
    queue<int> q;
    vector<int> ans;
    for (int u = 1; u <= n; u++)
        for (int v : G[u])
            indeg[v]++;
    for (int u = 1; u <= n; u++)
        if (indeg[u] == 0)
            q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for (int v : G[u])
            if (--indeg[v] == 0)
                q.push(v);
    }
    return ans.size() == n;
}

最短路径

Dijkstra

朴素算法: $O (n^{2})$

堆优化: $O (m lo g n)$

int V;
int dist[N];
bool vis[N];
 
void dijkstra(int s) {
    memset(0, 0x3f, sizeof(dist));
    dist[s] = 0;
    while (true) {
        int u = -1;
        for (int i = 0; i < V; i++)
            if ((u == -1 || dist[u] > dist[i]) && !vis[i])
                u = i;
        if (u == -1)
            break;
        vis[u] = true;
        for (auto &[v, w] : G[u])
            dist[v] = min(dist[v], dist[u] + w);
    }
}
void dijkstra_heap(int s) {
    priority_queue<Node, vector<Node>, greater<Node>> q;
    memset(0, 0x3f, sizeof(dist));
    dist[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto [dist_u, u] = q.top();
        q.pop();
        if (dist[u] < dist_u)
            continue;
        for (auto &[v, w] : G[u])
            if (dist[v] > dist[u] + w)
                q.push({dist[v] = dist[u] + w, v});
    }
}

最小生成树

kurskal

$O (m lo g m)$

vector<int> p;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
 
int kruskal() {
    int sum = 0, cnt = 0;
    p.resize(V + 1);
    iota(p.begin(), p.end(), 0);
    sort(edges.begin(), edges.end());
    for (auto &[u, v, w] : edges)
        if (find(u) != find(v)) {
            sum += w;
            cnt++;
            p[find(u)] = find(v);
        }
    return cnt == V - 1 ? sum : -1;
}

LCA

$O (n)$ dfs预处理， $O (lo g n)$ 查询

int n;
vector<int> G[N];
int p[N][20], dep[N], sum[N];
 
void dfs(int u, int fa) {
    p[u][0] = fa;
    dep[u] = dep[fa] + 1;
    sum[u] = sum[fa] + 1;
    for (int i = 1; i <= __lg(dep[u]); i++)
        p[u][i] = p[p[u][i - 1]][i - 1];
    for (int v : G[u])
        if (v != fa)
            dfs(v, u);
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = __lg(dep[x] - dep[y]); i >= 0; i--)
        if (dep[p[x][i]] >= dep[y])
            x = p[x][i];
    if (x == y)
        return x;
    for (int i = __lg(dep[x]); i >= 0; i--)
        if (p[x][i] != p[y][i]) {
            x = p[x][i];
            y = p[y][i];
        }
    return p[x][0];
}
int dist(int x, int y) { return sum[x] + sum[y] - 2 * sum[LCA(x, y)]; }
int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    return 0;
}

有向图的强连通分量

int dfn[N], low[N];
int cnt = 0, timer = 0;
int scc[N], sz[N]; // scc[i]：i所在的强连通分量，sz[i]：强连通分量i包含的节点数
stack<int> s;
bool in_stack[N];
 
void tarjan(int u) {
    low[u] = dfn[u] = ++timer;
    s.push(u);
    in_stack[u] = true;
    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int v;
        ++cnt;
        do {
            v = s.top(), s.pop();
            in_stack[v] = false;
            scc[v] = cnt;
            sz[cnt]++;
        } while (u != v);
    }
}

割点

int dfn[N], low[N];
int cnt = 0, timer = 0;
bool cut_vertex[N];
 
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++timer;
    int child = 0;
    for (int v : G[u]) {
        if (!dfn[v]) {
            child++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (fa != u && low[v] >= dfn[u] && !cut_vertex[u])
                cut_vertex[u] = true, cnt++;
        } else if (fa != v)
            low[u] = min(low[u], dfn[v]);
    }
    if (fa == u && child >= 2 && !cut_vertex[u])
        cut_vertex[u] = true, cnt++;
}

桥

int dfn[N], low[N];
int cnt = 0, timer = 0;
bool cut_edge[N];
int father[N];
 
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++timer;
    father[u] = fa;
    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u] && !cut_edge[u])
                cut_edge[v] = true, cnt++;
        } else if (fa != v)
            low[u] = min(low[u], dfn[v]);
    }
}

数学

数列公式

$i = 1 \sum n (ai + b) q^{i - 1} = (A n + B) q^{n} - B (A = \frac{a}{q - 1}, B = \frac{b - A}{q - 1})$

$i = 1 \sum n i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$

$i = 1 \sum n i^{3} = \frac{n ^{2} ( n + 1 ) ^{2}}{4}$

位运算

实用函数

int getBit(int a, int b) { return (a >> b) & 1; }
int unsetBit(int a, int b) { return a & ~(1 << b); }
int setBit(int a, int b) { return a | (1 << b); }
int flapBit(int a, int b) { return a ^ (1 << b); }
 
int __builtin_popcount(int n) // 返回n的二进制中有多少个1
int __builtin_parity(int n)   // 判断n的二进制中1的个数的奇偶性，偶0奇1
int __builtin_ffs(int n) // 返回n的二进制末尾最后一个1的位置，从一开始
int __builtin_clz(int n) // 返回n的二进制前导0的个数，当n为0时，结果未定义
int __builtin_ctz(int n) // 返回n的二进制后导0的个数
int __builtin_popcountll(long long n) // 支持long long
 
n & (n - 1) // 判断n是否为2的次幂，是0否1
n & -n; // lowbit 最低位1
 
int bit_floor(n) -> 1 << __lg(n)
int bit_ceil(n) -> 2 << __lg(n - 1)
int bit_width(n) -> __lg(n) + 1

<bitset>

bitset<1024> bs;  // bitset 存储 1024 个 bit
bitset(); // 每一位都是 0
bitset(unsigned long val); // 设为 val 的二进制形式
bitset(const string& str); // 设为 01 串 str
// 支持操作 [] == != & &= | |= ^ ^= << <<= >> >>=
int count() // 返回 true 的数量。
int size()  //  返回 bitset 的大小。
bool any()  // 若存在某一位是 true 则返回 true，否则返回 false。
bool none() // 若所有位都是 false 则返回 true，否则返回 false。
bool all()  // 若所有位都是 true 则返回 true，否则返回 false。
void set() // 将整个 bitset 设置成 true。
void set(int pos, bool val = true) // 将某一位设置成 true/false。
void reset() // 将整个 bitset 设置成 false。
void reset(int pos) // 将某一位设置成 false。相当于 set(pos, false)。
void flip() // 翻转每一位。
void flip(int pos) // 翻转某一位。
string to_string() // 返回转换成的字符串表达。
long to_ulong() // 返回转换成的 unsigned long 表达（long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。
long to_ullong() //（C++11 起）返回转换成的 unsigned long long 表达。

二进制集合

for (int s = 0; s < (1 << n); ++s)
// 降序遍历 m 的非空子集
for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集

// n元集合所有 k元子集
void GospersHack(int k, int n) {
    int cur = (1 << k) - 1;
    int limit = (1 << n);
    while (cur < limit) {
        // do something
        int lb = cur & -cur;
        int r = cur + lb;
        cur = ((r ^ cur) >> __builtin_ctz(lb) + 2) | r;
    }
}

快速幂

$O (lo g n)$

template <typename T> T ksm(T a, ll b) {
    T s = 1;
    for (; b; b >>= 1, a = a * a)
        if (b & 1)
            s = s * a;
    return s;
}

数论

最大公约数

欧几里得算法/辗转相除法

$O (lo g n)$

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// c++14 : __gcd(a, b)
// c++17 : std::gcd(a, b) <numeric>

扩展欧几里得算法

求 $a x + b y = g cd (a, b)$ 的一组特解

$O (lo g n)$

int extgcd(int a, int b, int &x, int &y) {
    int d;
    if (b == 0)
        x = 1, y = 0, d = a;
    else {
        d = extgcd(b, a % b, y, x); // x'  y'
        y -= a / b * x;             // y = y - a / b * x = x' - a / b * y' = y'' - a / b * y'
    }
    return d;
}

裴蜀定理

设 $a, b$ 是不全为零的整数，则存在整数 $x, y$ , 使得 $a x + b y = g cd (a, b)$

欧拉定理

若 $g cd (a, m) = 1$ ，则 $a^{φ (m)} \equiv 1 (mod m)$

费马小定理

若 $p$ 为素数， $g cd (a, p) = 1$ ，则 $a^{p - 1} \equiv 1 (mod p)$

另一个形式：对于任意整数 $a$ ，有 $a^{p} \equiv a (mod p)$

二元丢番图方程

$a x + b y = c$ 只有无解和无穷多解两种情况

根据裴蜀定理，当 $g cd (a, b) ∣ c$ 时 $a (\frac{g cd ( a , b )}{c} x) + b (\frac{g cd ( a , b )}{c} x) = a x^{'} + b y^{'} = g cd (a, b)$ 有解，即 $a x + b y = c$ 有解，否则无解

使用扩展欧几里得算法解 $a x^{'} + b y^{'} = g cd (a, b)$ 得一组解 $(x^{'}, y^{'})$

则原方程得一组特解为 $x_{0} = \frac{c}{g cd ( a , b )} x^{'}, y_{0} = \frac{c}{g cd ( a , b )} y^{'}$

通解为 $x = x_{0} + \frac{b}{g cd ( a , b )} n, y = y_{0} - \frac{a}{g cd ( a , b )} n$

$O (lo g n)$

若该方程无整数解，输出 $- 1$ 。
若该方程有整数解，且有正整数解，则输出：

其正整数解的数量
所有正整数解中 $x$ 的最小值
所有正整数解中 $y$ 的最小值
所有正整数解中 $x$ 的最大值
所有正整数解中 $y$ 的最大值。
若方程有整数解，但没有正整数解，则输出：
所有整数解中 $x$ 的最小正整数值
所有整数解中 $y$ 的最小正整数值。

vector<ll> solveEquation(ll a, ll b, ll c, ll &x0, ll &y0) { // solve ax+by=c
    ll d = extgcd(a, b, x0, y0);
    if (c % d != 0)
        return {-1};
    x0 *= c / d, y0 *= c / d;
    ll p = b / d, q = a / d, k, x1, y1;
    k = ceil((1.0 - x0) / p);
    x0 = x0 + k * p, y0 = y0 - k * q; // (x0, y0) is (x_min, y_max) x_min > 0
    k = ceil((1.0 - y0) / q);
    x1 = x0 - k * p, y1 = y0 + k * q; // (x1, y1) is (x_max, y_min) y_min > 0
    if (y0 > 0) {
        return {-k + 1, x0, y1, x1, y0};
    } else {
        return {x0, y1};
    }
}

x的最小和最大值

// 0<=x,y<=x+y<=n, ax+by=c
pair<ll, ll> minmax(ll a, ll b, ll c, ll n) {
    ll x0, y0, gcd = extgcd(a, b, x0, y0);
    if (c < 0) {
        return {-1, -1};
    } else if (c == 0 && gcd == 0) {
        return {0, n};
    } else if (c == 0) {
        return {0, 0};
    } else if (gcd == 0 || c % gcd != 0) {
        return {-1, -1};
    }
    // c > 0, gcd != 0, c % gcd == 0
    x0 *= c / gcd;
    y0 *= c / gcd;
    ll k_min = ceil(double(-x0) / (b / gcd));
    ll k_max = floor(double(y0) / (a / gcd));
    if (k_min > k_max) {
        return {-1, -1};
    }
    ll x_min = 1e8, x_max = -1;
    for (ll k = k_min; k <= k_max; k++) {
        ll x_k = x0 + k * (b / gcd);
        ll y_k = y0 - k * (a / gcd);
        if (x_k + y_k <= n) {
            x_min = min(x_min, x_k);
            x_max = max(x_max, x_k);
        }
    }
    return {x_min, x_max};
}

乘法逆元

如果一个线性同余方程 $a x \equiv 1 (mod b)$ ，则 $x$ 称为 $a mod b$ 的逆元，记作 $a^{- 1}$

扩展欧几里得法

$a x \equiv 1 (mod b) ⟺ a x + b y = 1$

int inv(int a, int b) {
    int x, y;
    extgcd(a, b, x, y);
    return x;
}

快速幂法

$a x \equiv 1 (mod b) ⟺ a x \equiv a^{b - 1} (mod b) ⟺ x \equiv a^{b - 2} (mod b)$

int inv(int a, int b) { return pow_mod(a, b - 2, b); }

线性同余方程

$a x \equiv b (mod n)$

逆元法

$a x \equiv b (mod n) ⟺ x \equiv b a^{- 1} (mod n)$

扩展欧几里得法

$a x \equiv b (mod n) ⟺ a x + n y = b$

线性同余方程组：中国剩余定理

LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

素数

分解质因数/唯一分解定理

$O (n)$

vector<int> getPrimeFactor(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0)
                n /= i, cnt++;
            res.push_back(i);
        }
    if (n != 1)
        res.push_back(n);
    return res;
}

素数测试

$O (n)$

bool Prime(int x) {
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return x > 1;
}

$O (k lo g n)$

bool millerRabin(int n, int k = 50) {
    if (n < 3 || n % 2 == 0)
        return n == 2;
    int u = n - 1, t = 0;
    while (u % 2 == 0)
        u /= 2, ++t;
    // test_time 为测试次数，建议设为不小于 8
    // 的整数以保证正确率，但也不宜过大，否则会影响效率
    for (int i = 0; i < k; ++i) {
        int a = rand() % (n - 2) + 2, v = qpow(a, u, n);
        if (v == 1)
            continue;
        int s;
        for (s = 0; s < t; ++s) {
            if (v == n - 1)
                break; // 得到平凡平方根 n-1，通过此轮测试
            v = (long long)v * v % n;
        }
        // 如果找到了非平凡平方根，则会由于无法提前 break; 而运行到 s == t
        // 如果 Fermat 素性测试无法通过，则一直运行到 s == t 前 v 都不会等于 -1
        if (s == t)
            return 0;
    }
    return 1;
}

埃氏筛

$O (n lo g lo g n)$

vector<int> isPrime, primes;
void eratosthenes(int n) {
    isPrime.assign(n + 1, 1);
    primes.clear();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j <= n; j += i)
                isPrime[j] = 0;
        }
}

线性筛

$O (n)$

vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (!minp[i])
            minp[i] = i, primes.push_back(i);
        for (int j = 0; i * primes[j] <= n; j++) {
            minp[i * primes[j]] = primes[j];
            if (i % primes[j] == 0)
                break;
        }
    }
}

积性函数

如果有 $g cd (a, b) = 1$ , 那么 $φ (a \times b) = φ (a) \times φ (b)$

欧拉函数

欧拉函数，即 $φ (n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数

当 $n$ 是质数的时候，显然有 $φ (n) = n - 1$

$φ (n) = \sum_{i = 1}^{n} [g cd (i, n) = 1] = n \times \prod_{i = 1}^{k}$

性质

欧拉函数是积性函数
$n = \sum_{d ∣ n} φ (d)$
若 $n = p^{k}$ , 其中 $p$ 是质数，那么 $φ (n) = p^{k} - p^{k - 1}$ （根据定义可知）
由唯一分解定理，设 $n = \prod_{i = 1}^{s} p_{i}^{k_{i}}$ , 其中 $p_{i}$ 是质数，有 $φ (n) = n \times \prod_{i = 1}^{s} \frac{p _{i} - 1}{p _{i}}$

求一个数欧拉函数的值

$O (n)$

int euler_phi(int n) 
  int ans = n;
  for (int i = 2; i * i<= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

求多个数的欧拉函数值

$O (n)$

void init_phi(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && ll(i) * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
    }
}

数论分块

$\sum_{i = 1}^{n} \sum_{d ∣ i} f (d) = \sum_{i = 1}^{n} f (i) ⌊ \frac{n}{i} ⌋$

快速计算 $\sum_{i = 1}^{n} f (i) g (⌊ \frac{n}{i} ⌋)$ , 其中 $f (i)$ 可以预处理前缀和 $s (i)$

$O (n)$

int f[N], g[N];
ll s[N];
ll H(int n) {
    ll res = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        ll d = n / l;
        r = n / d;
        // res += (r - l + 1) * d;
        res += (s[r] - s[l - 1]) * g[d];
    }
    return res;
}

模意义下的运算

const int mod = 1e9 + 7;
template <typename T> T pow(T a, long long b) {
    T s = 1;
    for (; b; a = a * a, b >>= 1)
        if (b & 1)
            s = s * a;
    return s;
}
struct Z {
    long long x;
    Z() {}
    Z(long long x) : x(Norm(x)) {}
    static long long Norm(long long x) { return x %= mod, x < 0 ? x + mod : x; }
    Z inv() const { return pow(*this, mod - 2); }
    friend Z operator+(const Z &a, const Z &b) { return Z(a.x + b.x); }
    friend Z operator-(const Z &a, const Z &b) { return Z(a.x - b.x); }
    friend Z operator*(const Z &a, const Z &b) { return Z(a.x * b.x); }
    friend Z operator/(const Z &a, const Z &b) { return a * b.inv(); }
    friend ostream &operator<<(ostream &os, const Z &z) { return os << z.x; }
    friend istream &operator>>(istream &os, Z &z) { return os >> z.x, z.x = Norm(z.x), os; }
};

组合数学

排列数和组合数

$O (n)$ 预处理， $O (1)$ 查询

struct Binom {
    vector<Z> fac;
    Binom(int n = 0) : fac(n + 1) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i;
    }
    Z C(int n, int m) { return (n < m || m < 0) ? 0 : fac[n] / fac[m] / fac[n - m]; }
    Z P(int n, int m) { return (n < m || m < 0) ? 0 : fac[n] / fac[n - m]; }
} binom;

卢卡斯定理

Z lucas(int n, int m, int p) {
    if (n < p && m < p)
        return binom.C(n, m);
    return binom.C(n % p, m % p) * lucas(n / p, m / p, p);
}

线性代数

向量与矩阵

矩阵快速幂

$k^{3} O (lo g n)$

using ll = long long;
using Matrix = vector<vector<ll>>;
Matrix operator*(const Matrix &A, const Matrix &B) {
    Matrix C(A.size(), vector<ll>(B[0].size()));
    for (int i = 0; i < A.size(); i++)
        for (int k = 0; k < B.size(); k++)
            for (int j = 0; j < B[0].size(); j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod;
    return C;
}
Matrix MatPow(Matrix A, ll b) {
    Matrix B(A.size(), vector<ll>(A[0].size()));
    for (int i = 0; i < B.size(); i++)
        B[i][i] = 1;
    for (; b; b >>= 1, A = A * A)
        if (b & 1)
            B = B * A;
    return B;
}

旋转矩阵

[cos θ sin θ - sin θ cos θ]

高斯消元

$O (n^{3})$

返回 0 无解，返回 1 有解，解为 $x_{i} = a [i] [n]$

// a:增广矩阵 n*(n+1)
int gauss(vector<vector<double>> &a, int n) {
    for (int i = 0; i < n; i++) { // 枚举列
        int r = i;                // 该列最大数所在的行
        for (int j = i + 1; j < n; j++)
            if (abs(a[j][i]) > abs(a[r][i]))
                r = j;
        if (abs(a[r][i]) < eps)
            return 0;     // 列最大数为0，无解
        swap(a[i], a[r]); // 把这一行移上来
        for (int j = n; j >= i; j--) a[i][j] /= a[i][i];     // 这一行的主元系数变为1
        for (int j = 0; j < n; j++) // 消去主元所在列的其他行的主元
            if (j != i && abs(a[j][i]) > eps)
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[i][k] * a[j][i] / a[i][i];
    }
    return 1;
}
if (!gauss(a, n)) {
    cout << "No Solution" << '\n';
} else {
    for (int i = 0; i < n; i++)
        printf("%.2lf\n", a[i][n]);
}

博弈论

mex函数

int mex(const vector<int> &v) {
    set<int> s(v.begin(), v.end());
    for (int i = 0;; i++)
        if (s.find(i) == s.end())
            return i;
}

SG函数

$SG (x) = 0 ⟺ x$ 对应的局面为必败态

$SG (x) > 0 ⟺ x$ 对应的局面为必胜态

线性

vector<int> getSG(int n, const vector<int> &f) {
    vector<int> SG(n + 1);
    for (int i = 1; i <= n; i++) {
        vector<int> S;
        for (int j = 0; f[j] <= i && j < f.size(); j++)
            S.push_back(SG[i - f[j]]);
        SG[i] = mex(S);
    }
    return SG;
}

dfs

void dfs(int u) {
    for (int v : G[u])
        dfs(v);
    vector<int> S;
    for (int v : G[u])
        S.push_back(SG[v]);
    SG[u] = mex(S);
}

微积分

自适应辛普森积分

double simpson(double l, double r) {
  double mid = (l + r) / 2;
  return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;  // 辛普森公式
}
 
double asr(double l, double r, double eps, double ans, int step) {
  double mid = (l + r) / 2;
  double fl = simpson(l, mid), fr = simpson(mid, r);
  if (abs(fl + fr - ans) <= 15 * eps && step < 0)
    return fl + fr + (fl + fr - ans) / 15;  // 足够相似的话就直接返回
  return asr(l, mid, eps / 2, fl, step - 1) +
         asr(mid, r, eps / 2, fr, step - 1);  // 否则分割成两段递归求解
}
 
double calc(double l, double r, double eps) {
  return asr(l, r, eps, simpson(l, r), 12);
}

多项式

FFT

using Poly = vector<int>;
using Complex = complex<double>;
const double eps = 0.49;
const double PI = acos(-1);
int rev[1 << 22];
void FFT(Complex a[], int n, int inv) {
    for (int i = 0; i < n; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << __lg(n >> 1));
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 2; i <= n; i <<= 1) {
        Complex wn(cos(2 * PI / i), inv * sin(2 * PI / i));
        for (int j = 0; j < n; j += i) {
            Complex w0(1, 0);
            for (int k = j; k < j + i / 2; ++k, w0 *= wn) {
                Complex x = a[k], y = w0 * a[k + i / 2];
                a[k] = x + y;
                a[k + i / 2] = x - y;
            }
        }
    }
    if (inv == -1)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}
Poly operator*(Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    vector<Complex> c(2 << __lg(n - 1));
    for (int i = 0; i < a.size(); i++)
        c[i].real(a[i]);
    for (int i = 0; i < b.size(); i++)
        c[i].imag(b[i]);
    FFT(c.data(), c.size(), 1);
    for (int i = 0; i < c.size(); i++)
        c[i] = c[i] * c[i];
    FFT(c.data(), c.size(), -1);
    Poly s(n);
    for (int i = 0; i < n; i++)
        s[i] = (int)(c[i].imag() / 2 + eps);
    return s;
}

NTT

using Poly = vector<int>;
int rev[1 << 22];
const int P = 998244353;
int ksm(int a, int b) {
    int s = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P)
        if (b & 1)
            s = 1LL * s * a % P;
    return s;
}
void NTT(int a[], int n, int inv) {
    for (int i = 0; i < n; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << std::__lg(n >> 1));
    for (int i = 0; i < n; i++)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);
    for (int i = 2; i <= n; i <<= 1) {
        int gn = ksm(3, (P - 1) / i);
        for (int j = 0; j < n; j += i) {
            int g0 = 1;
            for (int k = j; k < j + i / 2; ++k, g0 = 1LL * g0 * gn % P) {
                int x = a[k], y = 1LL * g0 * a[k + i / 2] % P;
                a[k] = (x + y) % P;
                a[k + i / 2] = (x - y + P) % P;
            }
        }
    }
    if (inv == -1) {
        reverse(a + 1, a + n);
        int n_inv = ksm(n, P - 2);
        for (int i = 0; i < n; i++)
            a[i] = 1LL * a[i] * n_inv % P;
    }
}
Poly operator*(Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    a.resize(2 << __lg(n - 1));
    b.resize(2 << __lg(n - 1));
    NTT(a.data(), a.size(), 1);
    NTT(b.data(), b.size(), 1);
    Poly c(2 << __lg(n - 1));
    for (int i = 0; i < c.size(); i++)
        c[i] = 1LL * a[i] * b[i] % P;
    NTT(c.data(), c.size(), -1);
    c.resize(n);
    return c;
}

计算几何

平面几何

#include <bits/stdc++.h>
using namespace std;
namespace Geometry {
using ld = long double;
ld pi = acos(-1);
ld eps = 1e-8;
int sgn(ld x) { return (x > eps) - (x < -eps); }
ld norm(ld x) { return sgn(x) ? x : 0; }
ld toRad(ld d) { return d * pi / 180; }
// Point
struct Vector {
    ld x, y;
    Vector(ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}
    Vector operator-() const { return Vector(-x, -y); }
    friend Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
    friend Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
    friend Vector operator*(Vector a, ld b) { return Vector(a.x * b, a.y * b); }
    friend Vector operator*(ld a, Vector b) { return Vector(a * b.x, a * b.y); }
    friend Vector operator/(Vector a, ld b) { return Vector(a.x / b, a.y / b); }
    friend bool operator==(Vector a, Vector b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }
    friend ld operator*(Vector a, Vector b) { return a.x * b.x + a.y * b.y; } // 点乘
    friend ld operator^(Vector a, Vector b) { return a.x * b.y - a.y * b.x; } // 叉乘
    Vector unitVec() { return *this / len(); }                                // 单位向量
    ld len() { return sqrt(*this * *this); }                                  // 欧几里得距离
    ld len2() { return *this * *this; }       // 欧几里得距离平方
    ld lenM() { return abs(x) + abs(y); }     // 曼哈顿距离
    Vector rotate() { return Vector(-y, x); } // 逆时针旋转90
    Vector rotate(ld rad) {                   // 逆时针旋转rad
        return Vector(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }
    // 向量的极角[0,pi):1, [pi,2*pi):-1
    int direction() { return y > 0 || (sgn(y) == 0 && x > 0) ? 1 : -1; }
    friend istream &operator>>(istream &is, Vector &p) { return is >> p.x >> p.y; }
    friend ostream &operator<<(ostream &os, Vector &p) {
        return os << "(" << norm(p.x) << ", " << norm(p.y) << ")";
    }
};
using Point = Vector;
// Vector
ld angle1(Vector a, Vector b) { return acos(a * b / a.len() / b.len()); } // 向量夹角
ld angle2(Vector a, Vector b) { return abs(atan2(abs(a ^ b), a * b)); }   // 向量夹角
bool parallel(Vector a, Vector b) { return sgn(a ^ b) == 0; }             // 向量平行
bool vertical(Vector a, Vector b) { return sgn(a * b) == 0; }             // 向量正交
// Line
struct Line {
    Vector a, b;
    Line(Vector a_ = Vector(), Vector b_ = Vector()) : a(a_), b(b_) {}
    friend ostream &operator<<(ostream &os, Line l) {
        return os << "<" << l.a << ", " << l.b << ">";
    }
};
using Segment = Line;
// 点在直线上
bool pointOnLine(Point p, Line l) { return parallel(l.b - l.a, p - l.a); }
// 点和直线的位置关系 0:在直线上 1:在直线左侧 -1:在直线右侧
int pointLinePosition(Point p, Line l) { return sgn((l.b - l.a) ^ (p - l.a)); }
// 点在线段上
bool pointOnSegment(Point p, Line l) {
    return pointOnLine(p, l) && sgn((l.a - p) * (l.b - p)) <= 0;
}
// 点到直线的距离
ld pointLineDist(Point p, Line l) { return abs((l.b - l.a) ^ (p - l.a)) / (l.b - l.a).len(); }
// 点在直线的投影
Point pointLineProjection(Point p, Line l) {
    return l.a + ((p - l.a) * (l.b - l.a)) / (l.b - l.a).len2() * (l.b - l.a);
}
// 点到线段的最近点
Point pointSegmentNearestPoint(Point p, Segment s) {
    Point pedal = pointLineProjection(p, s);
    if (pointOnSegment(pedal, s))
        return pedal;
    else
        return (s.a - p).len2() < (s.b - p).len2() ? s.a : s.b;
}
// 线线关系 0:平行 1:重合 2:垂直 3:相交但不垂直
int lineRelation(Line l1, Line l2) {
    if (!parallel(l2.b - l2.a, l1.b - l1.a))
        return !vertical(l2.b - l2.a, l1.b - l1.a) ? 3 : 2;
    else
        return pointOnLine(l1.a, l2) ? 1 : 0;
}
// 直线的交点
Point lineIntersection(Line l1, Line l2) {
    assert(lineRelation(l1, l2) > 1);
    ld t = ((l2.a - l1.a) ^ (l2.b - l2.a)) / ((l1.b - l1.a) ^ (l2.b - l2.a)); // (AC×CD)/(AB×CD)
    return l1.a + (l1.b - l1.a) * t;
}
// 线段关系 0:不相交 1:相交
bool segmentRelation(Segment s1, Segment s2) {
    // 快速排斥实验
    if (max(s1.a.x, s1.b.x) < min(s2.a.x, s2.b.x) || max(s2.a.x, s2.b.x) < min(s1.a.x, s1.b.x) ||
        max(s1.a.y, s1.b.y) < min(s2.a.y, s2.b.y) || max(s2.a.y, s2.b.y) < min(s1.a.y, s1.b.y))
        return false;
    // 跨立实验，点在线段同则不相交
    else if (pointLinePosition(s1.a, s2) * pointLinePosition(s1.b, s2) > 0 ||
             pointLinePosition(s2.a, s1) * pointLinePosition(s2.b, s1) > 0)
        return false;
    else
        return true;
}
// 线段的交点 0:不相交 1:普通相交 2:重合 3:交于端点
tuple<int, Point, Point> segmentIntersection(Segment s1, Segment s2) {
    ld L1 = min(s1.a.x, s1.b.x), R1 = max(s1.a.x, s1.b.x);
    ld B1 = min(s1.a.y, s1.b.y), T1 = max(s1.a.y, s1.b.y);
    ld L2 = min(s2.a.x, s2.b.x), R2 = max(s2.a.x, s2.b.x);
    ld B2 = min(s2.a.y, s2.b.y), T2 = max(s2.a.y, s2.b.y);
    // 快速排斥实验
    if (R1 < L2 || R2 < L1 || T1 < B2 || T2 < B1)
        return {0, Point(), Point()};
    if (parallel(s1.b - s1.a, s2.b - s2.a)) {
        if (!pointOnLine(s2.a, s1))
            return {0, Point(), Point()};
        // 线段共线
        Point LB(max(L1, L2), max(B1, B2));
        Point RT(min(R1, R2), min(T1, T2));
        if (!pointOnSegment(LB, s1))
            swap(LB.y, RT.y); // 水平翻转
        if (LB == RT)
            return {3, LB, RT};
        else
            return {2, LB, RT};
    }
    // 跨立实验，点在线段同则不相交
    ld cp1 = pointLinePosition(s1.a, s2);
    ld cp2 = pointLinePosition(s1.b, s2);
    ld cp3 = pointLinePosition(s2.a, s1);
    ld cp4 = pointLinePosition(s2.b, s1);
    if (cp1 * cp2 > 0 || cp3 * cp4 > 0)
        return {0, Point(), Point()};
    Point p = lineIntersection(s1, s2);
    if (cp1 != 0 && cp2 != 0 && cp3 != 0 && cp4 != 0)
        return {1, p, p};
    else
        return {3, p, p};
}
// 多边形
using Polygon = vector<Point>;
ld polygonArea(const Polygon &polygon) {
    ld s = 0;
    for (int i = 0, n = polygon.size(); i < n; i++)
        s += (polygon[i] ^ polygon[(i + 1) % n]);
    return s / 2;
}
// 点在多边形内部 1: 内部 0: 外部
bool pointInPolygon(Point p, const Polygon &polygon) {
    int n = polygon.size();
    bool c = false;
    for (int i = 0; i < n; i++) {
        Point u = polygon[i], v = polygon[(i + 1) % n];
        if (((u.x > p.x) != (v.x > p.x)) && (p.y < (p.x - u.x) * (v.y - u.y) / (v.x - u.x) + u.y))
            c = !c;
    }
    return c;
}
// 点和多边形的关系 3: 顶点上 2: 边上 1: 内部 0: 外部
int pointPolygonPosition(Point p, const Polygon &polygon) {
    int n = polygon.size();
    for (int i = 0; i < n; i++)
        if (pointOnSegment(p, Segment(polygon[i], polygon[(i + 1) % n])))
            return (p == polygon[i] || p == polygon[(i + 1) % n]) ? 3 : 2;
    return pointInPolygon(p, polygon);
}
}; // namespace Geometry
using namespace Geometry;

立体几何

namespace Gepmetry {
using ld = double;
const ld pi = acos(-1), eps = 1e-8;
int sgn(ld x) { return (x > eps) - (x < -eps); }
int cmp(ld x, ld y) { return sgn(x - y); }
ld norm(ld x) { return sgn(x) ? x : 0; }
ld toRad(ld d) { return d * pi / 180; }
struct Vector {
    ld x, y, z;
    Vector(ld x_ = 0, ld y_ = 0, ld z_ = 0) : x(x_), y(y_), z(z_) {}
    Vector operator-() const { return Vector(-x, -y, -z); }
    friend Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y, a.z + b.z); }
    friend Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y, a.z - b.z); }
    friend Vector operator*(Vector a, ld b) { return Vector(a.x * b, a.y * b, a.z * b); }
    friend Vector operator*(ld a, Vector b) { return Vector(a * b.x, a * b.y, a * b.z); }
    friend Vector operator/(Vector a, ld b) { return Vector(a.x / b, a.y / b, a.z / b); }
    friend bool operator==(Vector a, Vector b) {
        return !cmp(a.x, b.x) && !cmp(a.y, b.y) && !cmp(a.z, b.z);
    }
    friend ld operator*(Vector a, Vector b) { return a.x * b.x + a.y * b.y + a.z * b.z; } // 点乘
    friend Vector operator^(Vector a, Vector b) {
        return Vector(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
    } // 叉乘
    Vector unit() { return (*this) / len(); }    // 单位向量
    ld len() { return sqrt((*this) * (*this)); } // 欧几里得距离
    ld len2() { return (*this) * (*this); }      // 欧几里得距离平方
    ld lenM() { return abs(x) + abs(y); }        // 曼哈顿距离
    Vector rotate() { return Vector(-y, x); }    // 逆时针旋转90
    Vector rotate(Vector u, double rad) {        // 逆时针旋转rad
        u = u.unit();
        double c = cos(rad), s = sin(rad);
        double m00 = c + u.x * u.x * (1 - c);
        double m01 = u.x * u.y * (1 - c) - u.z * s;
        double m02 = u.x * u.z * (1 - c) + u.y * s;
        double m10 = u.y * u.x * (1 - c) + u.z * s;
        double m11 = c + u.y * u.y * (1 - c);
        double m12 = u.y * u.z * (1 - c) - u.x * s;
        double m20 = u.z * u.x * (1 - c) - u.y * s;
        double m21 = u.z * u.y * (1 - c) + u.x * s;
        double m22 = c + u.z * u.z * (1 - c);
        return Vector(m00 * x + m01 * y + m02 * z, m10 * x + m11 * y + m12 * z,
                      m20 * x + m21 * y + m22 * z);
    }
    friend istream &operator>>(istream &is, Vector &p) { return is >> p.x >> p.y >> p.z; }
    friend ostream &operator<<(ostream &os, Vector &p) {
        return os << "(" << norm(p.x) << ", " << norm(p.y) << ", " << norm(p.z) << ")";
    }
};
}

字符串

字符串哈希

const int N = 1e6 + 5, P = 131, mod = 1e9 + 7;
struct strHash {
    static vector<int> p;
    int n;
    vector<int> h;
    strHash(const string &s) : n(s.size()), h(n + 1) {
        if (!p[0])
            for (int i = p[0] = 1; i <= N; i++)
                p[i] = p[i - 1] * P;
        for (int i = 1; i <= n; i++)
            h[i] = h[i - 1] * P + s[i - 1];
    }
    int get() { return get(1, n); }
    int get(int l, int r) { return h.at(r) - h[l - 1] * p[r - l + 1]; }
};
vector<int> strHash::p(N + 1);

Tire/字典树

struct Tire {
    int nxt[100000][26], cnt;
    bool exist[100000]; // 该结点结尾的字符串是否存在
 
    void insert(string s) { // 插入字符串
        int p = 0;
        for (char c : s) {
            c -= 'a';
            if (!nxt[p][c])
                nxt[p][c] = ++cnt; // 如果没有，就添加结点
            p = nxt[p][c];
        }
        exist[p] = 1;
    }
 
    bool find(string s) { // 查找字符串
        int p = 0;
        for (char c : s) {
            c -= 'a';
            if (!nxt[p][c])
                return false;
            p = nxt[p][c];
        }
        return exist[p];
    }
};

KMP

next数组

// pi[i]: 子串 s[0, i-1] 最长的相等的真前缀与真后缀的长度
// pi[i]: s[0, pi[i]-1] == s[i-pi[i], i-1]
vector<int> prefix(string s) {
    int n = s.size();
    vector<int> pi(n + 1);
    for (int i = 1; i < n; i++) {
        int j = pi[i];
        while (j && s[i] != s[j])
            j = pi[j];
        if (s[i] == s[j])
            j++;
        pi[i + 1] = j;
    }
    return pi;
}

动态规划

杂项

随机数生成器

uint32_t seed;
inline uint32_t getnext() {
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

mt19937 算法

mt19937 myrand(time(0));
cout << myrand() << endl;

Quartz

探索

ICPC 常用算法模板