「模板」算法竞赛模板库——Mohao's Template Folder

莫号模板库（Mohao’s Template Folder, MTF）是一个由我个人创建个人使用不欢迎贡献的算法竞赛模板库。

主要的设计灵感来自于 AtCoder Library 以及 WIDA 的 XCPC 模板库。

目前正在施工中……

0x00 - 杂类

0x01 - 约定

C++ 版本：
1. 最低支持版本：c++17；
2. 默认版本：gnu++23；
格式：
1. 缩进宽度为 4 个空格；
2. 大括号换行；
3. 一元运算符不空格，其他运算符空一格；
命名：
1. 遵循 GoLang 的命名规范；
其他：
1. 使用邻接表存图；
2. 使用 0-indexed 的左闭右闭区间；
3. 使用解绑同步流的 std::cin 和 std::cout 输入输出；
4. 使用 using namespace std;，非必要不使用 #define int long long；
5. 使用局部变量而非全局变量，局部 lambda 而非全局函数；
6. 使用 emplace 而非 push，使用 contains 而非 count；
7. 若键值较小，使用 vector 而非 map；不要求顺序的情况下可以用 unordered_ 系列，但在 Codeforces 上记得使用随机模数；

0x02 - 初始

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) std::println(std::cerr, "{}:\n{}", #x, x)

using i8 = signed char; using u8 = unsigned char;
using i32 = signed; using u32 = unsigned;
using i64 = long long; using u64 = unsigned long long;
using i128 = __int128; using u128 = unsigned __int128;

namespace rg = std::ranges;
namespace vw = rg::views;

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {

}

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

0x03 - 随机哈希

使用的随机算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct custom_hash {
    static u64 splitmix64(u64 x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    u64 operator()(u64 x) const {
        static const u64 SEED = chrono::high_resolution_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};

0x04 - 二分答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int l, r, ans;
bool check(int);
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;
        // l 和 r 取决于方向
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

0x05 - Lambda 递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// C++23
auto dfs = [&](this auto&& self, int x, int p) -> void {
    for (auto y : adj[x]) {
	    if (y == p)
	        continue;
		self(y, x);
    }
}
// C++17
function<void(int,int)> dfs = [&](int x, int p) {
   for (auto y : adj[x]) {
       if (y == p)
	       continue;
	    dfs(y, x);
   }
}

0x10 - 数学

0x11 - 线性筛

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
vector<int> pri, mp;
// 如果不求最小素因数可以改成 vector<bool> np;
void Sieve(int n) {
    mp.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!mp[i]) pri.emplace_back(i);
        for (int p : pri) {
            if (i * p > n) break;
            np[i * p] = p;
            if (i % j == 0) break;
        }
    }
}

0x12 - 快速幂

1
2
3
4
5
6
7
8
9
int PowMod(i64 a, i64 b, int p) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        b = b >> 1;
        a = a * a % p;
    }
    return res;
}

0x13 - 因数/约数分解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
auto Factor(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res.emplace_back(i);
            n /= i;
        }
    }
    if (n > 1)
        res.emplace_back(i);
    return res;
}

auto Divisor(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i * i != n)
                res.emplace_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

0x14 - 扩展欧几里得

1
2
3
4
5
6
7
8
9
auto ExGCD(auto a, auto b, auto &x, auto &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    auto d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

0x20 - 数据结构

0x21 - 并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
struct DSU {
    vector<int> f, sz;
   
    DSU(int n) : f(n), sz(n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    
    int Find(int x) {
        while (x != f[x])
            x = f[x] = f[f[x]];
        return x;
    }
    
    void Merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)
            return;
        f[y] = x;
        sz[x] += sz[y];
    }
};

0x22 - 树状数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename T = i64>
struct Fenwick {
    int n;
    vector<T> a;
    
    Fenwick(int n) : n(n), a(n + 1) {}
    
    void Add(int x, T v) {
        for (; x <= n; x += x & -x)
            a[x] += v;
    }
    
    T sum(int x) {
        T res = {};
        for (; x; x -= x & -x)
            res += a[x];
        return res;
    }
    
    T Sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

0x23 - 线段树

关于 S 的约束：

存在满足封闭性结合律的 operator+ 运算；
存在单位元 {} （具有默认构造函数，且满足和单位元运算后不改变原值）

关于初始数组 vector<T>：

若 T $\neq$ S，则必须保证 S 存在可由 T 构造的构造函数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
template <class S>
struct SegTree {
    int n;
    std::vector<S> tree;

    void pull(int p) {
        tree[p] = tree[2 * p] + tree[2 * p + 1];
    }

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    S query(int ql, int qr, int p, int l, int r) {
        if (ql > r or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + 
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int pos, const S &val, int p, int l, int r) {
        if (l == r) {
            tree[p] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid)
            update(pos, val, 2 * p, l, mid);
        else
            update(pos, val, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    SegTree() : n(0) {}
    SegTree(int _n) : n(_n), tree(4 * n, {}) {}
    SegTree(auto &&v) : n(v.size()) {
        tree.resize(4 * n);
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) {
        return query(l, r, 1, 0, n - 1);
    }

    void Update(int p, const S &v) {
        update(p, v, 1, 0, n - 1);
    }
};

0x24 - 懒标记线段树

关于 T 的约束：

存在满足封闭性的 operator+= 运算；
存在一个恒等映射 {}（默认构造函数）；
存在运算 operator== 判断是否和恒等映射相等；
- 其实这里也不是非常必要的，但是可以提高性能；

关于 S 的约束：

存在满足封闭性结合律的 operator+ 运算；
存在单位元 {} （具有默认构造函数，且满足和单位元运算后不改变原值）
存在 operator*= 运算满足将映射 F 应用于 S 返回一个 S，并且满足分配律。

关于初始数组 vector<T>：

若 T $\neq$ S，则必须保证 S 存在可由 T 构造的构造函数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
template <class S, class F>
struct LazySegTree {
    int n;
    std::vector<S> tree;
    std::vector<F> tag;

    void pull(int p) {
        tree[p] = tree[2 * p] + tree[2 * p + 1];
    }

    void apply(int p, F f) {
        tree[p] *= f;
        tag[p] += f;
    }

    void push(int p) {
        if (tag[p] != F{}) 
            return;
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = {};
    }

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    S query(int ql, int qr, int p, int l, int r) {
        if (ql > r or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        push(p);
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + 
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int ul, int ur, F f, int p, int l, int r) {
        if (ul > r or ur < l) return;
        if (ul <= l and r <= ur) {
            apply(p, f);
            return;
        }
        push(p);
        int mid = l + (r - l) / 2;
        update(ul, ur, f, 2 * p, l, mid);
        update(ul, ur, f, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    LazySegTree() : n(0) {}
    LazySegTree(int _n) : n(_n), tree(4 * n, {}), 
                          tag(4 * n, {}) {}
    LazySegTree(auto &&v) : n(v.size()) {
        tree.resize(4 * n);
        tag.resize(4 * n, {});
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) {
        return query(l, r, 1, 0, n - 1);
    }

    void Update(int l, int r, F f) {
        update(l, r, f, 1, 0, n - 1);
    }
};

0x25 - 取模类

fork from jiangly.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
template <class T> constexpr T power(T a, u64 b, T res = 1) {
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template <u32 P> constexpr u32 mulMod(u32 a, u32 b) { return u64(a) * b % P; }

template <u64 P> constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

constexpr i64 safeMod(i64 x, i64 m) {
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
    a = safeMod(a, b);
    if (a == 0) {
        return {b, 0};
    }

    i64 s = b, t = a;
    i64 m0 = 0, m1 = 1;

    while (t) {
        i64 u = s / t;
        s -= t * u;
        m0 -= m1 * u;

        std::swap(s, t);
        std::swap(m0, m1);
    }

    if (m0 < 0) {
        m0 += b / s;
    }

    return {s, m0};
}

template <std::unsigned_integral U, U P> struct ModIntBase {
  public:
    constexpr ModIntBase() : x(0) {}
    template <std::unsigned_integral T> constexpr ModIntBase(T x_) : x(x_ % mod()) {}
    template <std::signed_integral T> constexpr ModIntBase(T x_) {
        using S = std::make_signed_t<U>;
        S v = x_ % S(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }

    constexpr static U mod() { return P; }

    constexpr U val() const { return x; }

    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }

    constexpr ModIntBase inv() const { return power(*this, mod() - 2); }

    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<mod()>(x, rhs.val());
        return *this;
    }
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & { return *this *= rhs.inv(); }

    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }

    friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs,
                                                      const ModIntBase &rhs) {
        return lhs.val() <=> rhs.val();
    }

  private:
    U x;
};

template <u32 P> using ModInt = ModIntBase<u32, P>;
template <u64 P> using ModInt64 = ModIntBase<u64, P>;