ACM-ICPC Scoreboard

基本算法

尺取法/双指针

$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
// 尺取法获取第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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
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(\log n)$

1
2
3
4
5
6
7
8
9
10
int l, r， m; // [l,r)
while (r - l > 1)
	if (check(m = (l + r) / 2))
		l = m;
	else
		r = m;
// l : last true
// r : first false
// lower_bound(x) | check(mid) <x -> r |
// upper_bound(x) | check(mid)<=x -> r |

倍增

快速幂式

$O(n\log m)$

1
2
3
4
5
6
7
8
9
10
// n个点跳跃m次位置
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]]; //倍增跳
}

朴素式

$O(n\log m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化
vector<vector<ll>> f(n + 1, vector<ll>(__lg(m) + 2));
for (int i = 1; i <= n; i++)
    f[i][0] = nxt[i];
for (int t = 1; t <= __lg(m) + 1; t++)
    for (int i = 1; i <= n; i++)
        f[i][t] = f[f[i][t - 1]][t - 1];
// 查询
int p = 1;
for (int t = __lg(m) + 1; t >= 0; t--)
	if (f[p][t] is 合法) {
        p = f[p][t];
        其他操作
    }

前缀和与差分

一维

前缀和: $pr_i = pr_{i-1}+a_i$

差分: $df_i=a_i-a_{i-1}$

差分区间修改:

$$
\mathrm{add}(l,r,k)\to
\begin{cases}
df_l\gets df_l+k,\newline
df_{r+1}\gets df_{r+1}-k
\end{cases}
$$

二维

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

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

差分区间修改:

$$
\mathrm{add}((x_1,y_1),(x_2,y_2),k)\to
\begin{cases}
df_{x_1,y_1}\gets df_{x_1,y_1}+k\newline
df_{x_1,y_2+1}\gets df_{x_1,y_2+1}-k\newline
df_{x_2+1,y1}\gets df_{x_2+1,y1}-k\newline
df_{x_2+1,y_2+1}\gets df_{x_2+1,y_2+1}+k\newline
\end{cases}
$$

树上

前缀和: 设 $pr_i$ 表示结点 $i$ 到根节点的权值总和。

  • 若是点权, $x,y$ 路径上的和为 $pr_x + pr_y - pr_{lca} - pr_{fa(lca)}$。
  • 若是边权, $x,y$ 路径上的和为 $pr_x + pr_y - 2\cdot pr_{lca}$。

差分:

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

  • 点差分:

$$
\begin{cases}
d_s\gets d_s+1,\newline
d_{lca}\gets d_{\textit{lca}}-1\newline
d_t\gets d_t+1\newline
d_{fa(lca)}\gets d_{fa(lca)}-1\newline
\end{cases}
$$

  • 边差分:

$$
\begin{cases}
d_s\gets d_s+1\newline
d_t\gets d_t+1\newline
d_{lca}\gets d_{lca}-2\newline
\end{cases}
$$

离散化

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

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

$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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!)$

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

组合

$O(2^n)$

1
2
3
4
5
6
7
8
9
10
11
12
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) {
            // 判断某位
        }
}
for (int i = 0; i <= n; i++)
    cout << a[i] << " ";

数据结构

单调栈

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

1
2
3
4
5
6
7
8
9
10
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)$

1
2
3
4
5
6
7
8
9
10
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\log n)$

查询: $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T, T (*op)(T, T)> struct SparseTable {
    int n, logn;
    vector<vector<T>> dat;
    SparseTable(const vector<T> &v) : n(v.size()), logn(__lg(n) + 1), dat(n + 1, 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 = __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(\log n)$

1
2
3
4
5
6
7
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(\log n)$

区间查询: $O(\log n)$ 

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

template <typename T> struct BIT {
    int size;
    vector<T> dat;
    BIT(int n = 0) : size(n), dat(n + 1, 0) {}
    inline int lowbit(int x) { return x & -x; }
    void add(int i, T x) {
        for (; i <= size; i += lowbit(i))
            dat[i] += x;
    }
    T get(int i) {
        T res = 0;
        for (i = min(i, size); i; i -= lowbit(i))
            res += dat[i];
        return res;
    }
    T query(int l, int r) { return get(r) - get(l - 1); }
    int kthLe(int k) {
        int l = 0, r = size + 1, mid;
        while (r - l > 1)
            get(mid = (l + r) >> 1) < k ? l = mid : r = mid;
        return r;
    }
    int kthGe(int k) {
        int l = 0, r = size + 1, mid;
        int sum = get(size);
        while (r - l > 1)
            sum - get(mid = (l + r) >> 1) < k ? r = mid : l = mid;
        return r;
    }
};

线段树

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

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

zkw线段树

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

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

单点修改: $O(\log n)$

区间查询: $O(\log n)$

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
template <typename T, T (*op)(T, T), T (*e)()> class SegmentTree {
    int n;
    vector<T> dat;

  public:
    SegmentTree(const int _n) : n(2 << __lg(_n - 1)), dat(n << 1, e()) {}
    SegmentTree(const vector<T> &v) : n(2 << __lg(v.size() - 1)), dat(n << 1, e()) {
        copy(v.begin(), v.end(), dat.begin() + n);
        for (int p = n - 1; p; p--)
            dat[p] = op(dat[p << 1], dat[p << 1 | 1]);
    }
    void update(int i, T k) { // update[i]=k
        for (dat[i += n] = k; i; i >>= 1)
            dat[i >> 1] = op(dat[i], dat[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) {
            res = i & 1 ? op(res, dat[i++]) : res;
            res = j & 1 ? res : op(res, dat[j--]);
        }
        return res;
    }
};
template <typename T> T Add(T a, T b) { return a + b; }
template <typename T> T e() { return 0; }

线段树

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

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

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

区间修改: $O(\log n)$

区间查询: $O(\log n)$

单点修改

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
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); }
};

区间修改

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
template <typename Info, typename Tag> struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    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 apply(int p, int l, int r, const Tag &v) {
        info[p].apply(l, r, v);
        tag[p].apply(l, r, v);
    }
    void pushdown(int p, int l, int r) {
        int m = (l + r) / 2;
        apply(p << 1, l, m, tag[p]);
        apply(p << 1 | 1, m + 1, r, tag[p]);
        tag[p] = Tag();
    }
    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 apply(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 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 rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
};
struct Tag {
    int x;
    void apply(int l, int r, const Tag &v) { x += v.x; }
};
struct Info {
    ll sum = 0;
    void apply(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(\log n)$ 修改和查询

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
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(\sqrt{n})$ 查询

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
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平衡树

1
2
3
4
5
6
7
8
9
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); }
};

图论

存图

邻接表/邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]) {}

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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\log n)$

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
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\log m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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(\log n)$ 查询

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<int> G[N];
int dep[N], p[N][20];
void dfs(int u, int fa) {
    p[u][0] = fa;
    for (int t = 1; (1 << t) <= dep[u]; t++)
        p[u][t] = p[p[u][t - 1]][t - 1];
    for (int v : G[u])
        if (v != fa) {
            dfs(v, u);
            dep[v] = dep[u] + 1;
        }
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = p[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (p[x][i] != p[y][i])
            x = p[x][i], y = p[x][i];
    return p[x][0];
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
}

无向图的双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// x 代表当前搜索树的根节点，in_edge 代表其对应的序号（tot）
void tarjan(int x, int in_edge) {
    // 在搜索之前，先初始化节点 x 的时间戳与追溯值
    dfn[x] = low[x] = ++num;
    // 通过 head 变量获取节点 x 的直接连接的第一个相邻节点的序号
    // 通过 Next 变量，迭代获取剩下的与节点 x 直接连接的节点的序号
    for (int i = head[x]; i; i = Next[i]) {
        // 此时，i 代表节点 y 的序号
        int y = ver[i];
        // 如果当前节点 y 没有被访问过
        if (!dfn[y]) {
            // 递归搜索以 y 为跟的子树
            tarjan(y, i);
            // 计算 x 的追溯值
            low[x] = min(low[x], low[y]);
            // 桥的判定法则
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true; // 标记当前节点是否为桥（具体见下文）
        }
        else if (i != (in_edge ^ 1)) // 当前节点被访问过，且 y 不是 x 的“父节点”（具体见下文）
            low[x] = min(low[x], dfn[y]);
    }
}

有向图的强连通分量

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
void tarjan(int u)
{
	 //u的时间戳
 	dfn[u] = low[u] = ++timestamp;
     //把当前点加到栈中  当前点在栈中
    stk[++top] = u,in_stk[u] = true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])//j点未被遍历过
        {
            tarjan(j);//继续dfs 遍历j
            //j也许存在反向边到达比u还高的层,所以用j能到的最小dfn序(最高点)更新u能达到的(最小dfn序)最高点
            low[u] = min(low[u],low[j]);
        }
        //j点在栈中  说明还没出栈 是dfs序比当前点u小的
        //则其 1要么是横插边(左边分支的点)
        //         o
        //        / \
        //       j ← u    
        //     2要么是u的祖宗节点
        //         j
        //      ↗/ 
        //       u    
        //    两种情况u的dfs序都比j大 所以用dfn[j]更新low[u]
        else if(in_stk[j])
        {
            low[u] = min(low[u],dfn[j]);//直接用j的时间戳更新u
        }
        //栈代表当前未被搜完的强连通分量的所有点
    }
    // ⭐
    // 解释一下为什么tarjan完是逆dfs序
    // 假设这里是最高的根节点fa
    // 上面几行中 fa的儿子节点j都已经在它们的递归中走完了下面9行代码
    // 其中就包括 ++scc_cnt 
    // 即递归回溯到高层节点的时候 子节点的scc都求完了
    // 节点越高 scc_id越大
    // 在我们后面想求链路dp的时候又得从更高层往下
    // 所以得for(int i=scc_cnt(根节点所在的scc);i;i--)开始

    // 所以当遍历完u的所有能到的点后 发现u最高能到的点是自己
    // 1 则u为强连通分量中的最高点,则以u为起点往下把该强连通分量所有节点都找出来
    // 2 要么它就没有环,就是一个正常的往下的点
    if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;//强连通分量总数+1
        do
        {
            y = stk[top--];//取栈顶元素y
            in_stk[y] = false;//则y不再在栈中
            id[y] = scc_cnt;
            Size[scc_cnt] ++;//第scc_cnt个连通块点数+1
        }while(y!=u);
        //1 因为栈中越高的元素的dfs序越大,那么我们只需要把dfs序比u大的这些pop到u
        //即因为最终会从下至上回到u 所以当y==u     
        //则说明点u所在的所有强连通分量都标记了id
        //           →  u
        //          /  /
        //         /  ne1
        //         ← ne2
        //      因为ne2会在u能到的dfs序里最大的,也就是此时的栈顶
        //      那么我们就逐一pop出ne2和ne1
        //2 要么它就是一个没有环的点 则该点单点成一个连通分量
    }
}

割点

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
const int V = 20;
int dfn[V], low[V], parent[V];
bool vis[V], ap[V];
vector<int> g[V];

void dfs(int u)
{
    static int count = 0;
    // 子树数量
    int children = 0;
    // 默认low[u]等于dfn[u]
    dfn[u] = low[u] = ++count;
    vis[u] = true;

    // 遍历与u相邻的所有顶点
    for (int v: g[u])
    {
        // (u, v)为树边
        if (!vis[v])
        {
            // 递增子树数量
            children++;
            // 设置v的父亲为u
            parent[v] = u;
            // 继续DFS
            dfs(v);
            // DFS完毕，low[v]已求出，如果low[v]<low[u]则更新low[u]
            low[u] = min(low[u], low[v]);

            // 如果是根节点且有两棵以上的子树则是割点
            if (parent[u] == -1 && children >= 2)
                cout << "Articulation point: " << u << endl;
            // 如果不是根节点且low[v]>=dfn[u]则是割点
            else if (parent[u] != -1 && low[v] >= dfn[u])
                cout << "Articulation point: " << u << endl;
        }
        // (u, v)为回边，且v不是u的父亲
        else if (v != parent[u])
            low[u] = min(low[u], dfn[v]);
    }
}

数学

位运算

实用函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 表达。

二进制集合

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

快速幂

$O(\log n)$

1
2
3
4
5
6
7
ll pow(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x)
        if (n & 1)
            s = s * x;
    return s;
}

数论

最大公约数

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

$O(\log n)$

1
2
3
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>

扩展欧几里得算法

求 $ax+by=\gcd(a,b)$ 的一组特解

$O(\log n)$

1
2
3
4
5
6
7
8
9
10
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$, 使得 $ax+by=\gcd(a,b)$

欧拉定理

若 $\gcd(a, m) = 1，则 a^{\varphi(m)} \equiv 1 \pmod{m}$

费马小定理

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

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

二元丢番图方程

$ax + by = c$ 只有无解和无穷多解两种情况

根据裴蜀定理，当 $\gcd(a,b)\mid c$ 时 $a\left(\dfrac{\gcd(a,b)}{c}x\right)+b\left(\dfrac{\gcd(a,b)}{c}x\right)=ax’+by’=\gcd(a,b)$ 有解，即 $ax + by = c$ 有解，否则无解

使用扩展欧几里得算法解 $ax’+by’=\gcd(a,b)$ 得一组解 $(x’,y’)$

则原方程得一组特解为 $x_0=\dfrac{c}{\gcd(a,b)}x’,\ y_0=\dfrac{c}{\gcd(a,b)}y’$

通解为 $x=x_0+\dfrac{b}{\gcd(a,b)}n ,\ y=y_0−\dfrac{a}{\gcd(a,b)}n$

$O(\log n)$

1
2
3
4
5
6
7
8
9
// ax + by = c
bool liEu(ll a, ll b, ll c, ll &x, ll &y) {
    int d = extgcd(a, b, x, y);
    if (c % d != 0)
        return false;
    x = x * c / d;
    y = y * c / d;
    return true;
}

x的最小和最大值

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
void minmax(ll a, ll b, ll c, ll n) {
    ll x0, y0, gcd = extgcd(a, b, x0, y0);
    if (c < 0) {
        cout << -1 << '\n';
        return;
    } else if (c == 0 && gcd == 0) {
        cout << 0 << ' ' << n << '\n';
        return;
    } else if (c == 0) {
        cout << 0 << ' ' << 0 << '\n';
        return;
    } else if (gcd == 0 || c % gcd != 0) {
        cout << -1 << '\n';
        return;
    }
    // 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) {
        cout << -1 << '\n';
        return;
    }
    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);
        }
    }
    cout << x_min << ' ' << x_max << '\n';
}

乘法逆元

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

扩展欧几里得法

$ax \equiv 1 \pmod b \iff ax+by=1$

1
2
3
4
5
int inv(int a, int b) {
    int x, y;
    extgcd(a, b, x, y);
    return x;
}

快速幂法

$ax \equiv 1 \pmod b \iff ax\equiv a^{b-1} \pmod b \iff x \equiv a^{b-2} \pmod b$

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

线性同余方程

$ax \equiv b \pmod n$

逆元法

$ax \equiv b \pmod n\iff x \equiv ba^{-1} \pmod n$

扩展欧几里得法

$ax \equiv b \pmod n \iff ax+ny=b$

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

1
2
3
4
5
6
7
8
9
10
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(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
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(\sqrt{n})$

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

$O(k\log n)$

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
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\log\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
        }
    }
}

积性函数

如果有 $\gcd(a, b) = 1$ , 那么 $\varphi(a \times b) = \varphi(a) \times \varphi(b)$

欧拉函数

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

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

$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=n\times \prod_{i=1}^{k}$

性质

  • 欧拉函数是积性函数

  • $n = \sum_{d \mid n}{\varphi(d)}$

  • 若 $n = p^k$ , 其中 $p$ 是质数，那么 $\varphi(n) = p^k - p^{k - 1}$ （根据定义可知）

  • 由唯一分解定理，设 $n = \prod_{i=1}^{s}p_i^{k_i}$ , 其中 $p_i$ 是质数，有 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$

求一个数欧拉函数的值

$O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)\left\lfloor\dfrac ni\right\rfloor$

快速计算 $\sum_{i=1}^n f(i)g(\left\lfloor\dfrac ni\right\rfloor)$ , 其中 $f(i)$ 可以预处理前缀和 $s(i)$

$O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

模意义下的运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)$ 查询

1
2
3
4
5
6
7
8
9
10
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 m, int n) { return (m < n || n < 0) ? 0 : fac[m] / fac[n] / fac[m - n]; }
    Z P(int m, int n) { return (m < n || n < 0) ? 0 : fac[m] / fac[m - n]; }
} binom;

卢卡斯定理

1
2
3
4
5
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(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using ll = long long;
using Matrix = vector<vector<int>>;
Matrix operator*(const Matrix &A, const Matrix &B) {
    Matrix C(A.size(), vector<int>(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]);
    return C;
}
Matrix pow(Matrix &A, ll n) {
    Matrix B(A.size(), vector<int>(A[0].size()));
    for (int i = 0; i < B.size(); i++)
        B[i][i] = 1;
    for (; n; n >>= 1, A = A * A)
        if (n & 1)
            B = B * A;
    return B;
}

旋转矩阵

$$\begin{bmatrix}
\cos\theta & -\sin\theta\newline
\sin\theta & \cos\theta
\end{bmatrix}$$

高斯消元

$O(n^3)$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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函数

1
2
3
4
5
6
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函数

$\operatorname{SG}(x)=0\iff x$ 对应的局面为必败态

$\operatorname{SG}(x)>0\iff x$ 对应的局面为必胜态

线性

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
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);
}

微积分

自适应辛普森积分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

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
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;
}

字符串

Tire/字典树

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
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数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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;
}

动态规划

单调队列优化

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
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}