Tricks#

取整#

通用#

\lceil f(x) \rceil = -\lfloor -f(x) \rfloor

离散加小步长#

需要单调

\lceil f(x) \rceil = \lfloor f(x-1) \rfloor +1 \quad (\text{当 } 0 < f(x)-f(x-1) \le 1)

向下取整和向上取整#

向下取整是闭开

向上取整是开闭

$1 + \lfloor log_2(x)\rfloor$ 和 $\lceil log_2(x + 1) \rceil$ 在整数域上由于向下取整和向上取整对应的区间中总是在同一直线，同时向下取整的左端点总是小于向上取整的左端点，向下取整的右端点总是大于向上取整的右端点，故两者在整数域上等效，同时 $1 + \lfloor log_2(x)\rfloor \Leftrightarrow bit\_width(x)$

中点#

中点m取n的时候，偶数n，m在偏右，如遍历左边取到m的话，奇偶都是左边偏大，取n - 1的时候，奇数左偏大，偶数左右相等

中点m由n时，

偶数n，m偏右中点，遍历左边取m的话，左偏大，不取的话，一样大。
奇数n，m不偏不倚，遍历左边取m的话，左偏大，不取的话，右偏大

取的话

左[l, m]，右[m + 1, r]

不取的话

左[l, m - 1], 右[m, r]

中点m由n-1时

偶数n，m偏左中点，遍历左边取m的话，一样大，不取的话，右偏大
奇数n，m不偏不倚，遍历左边取m的话，左偏大，不取的话，右偏大

取的话

左[l, m]，右[m + 1, r]

不取的话

左[l, m - 1]，右[m, r]

和中点m由n时的取不取情况是镜像的，但是表达式只取决于左边取不取中点

$\lfloor \frac{n-1}{2} \rfloor$ 能把 $1,2,3,4,5,6,\ldots$ 映射到 $0,0,1,1,2,2,\ldots$

杂项#

区间合并#

1
using pii = pair<int, int>;
2
vector<pii> a, res;
3

4
sort(a.begin(), a.end());
5
auto [st, ed] = a[0];
6
for (int i = 1; i < a.size(); ++i) {
7
    auto [st1, ed1] = a[i];
8
    if (st1 <= ed) {
9
        ed = max(ed, ed1);
10
    } else {
11
        res.push_back({st, ed});
12
        st = st1;
13
        ed = ed1;
14
    }
15
}
16
res.push_back({st, ed});

离散化#

哈希#

1
struct discretization {
2
  unordered_map<string, int> m;
3

4
  discretization(const vector<string>& a) {
5
    for (int i = 0; i < a.size(); ++i) {
6
      m[a[i]] = i;
7
    }
8
  }
9

10
  int operator[](string x) {
11
    return m[x];
12
  }
13
} dt;

二分#

1
struct discretization {
2
  vector<int> help;
3

4
  discretization(const vector<int>& a) : help(a) {
5
    sort(help.begin(), help.end());
6
    help.erase(unique(help.begin(), help.end()));
7
  }
8

9
  int operator[](int x) {
10
    return ( lower_bound(help.begin(), help.end(), x) - help.begin() );
11
  }
12
}

排序#

归并排序

1
#define N 1000
2

3
int tmp[N];
4
void ms(int q[], int l, int r) {
5
    if (l >= r) return;
6

7
  int m = l + r >> 1;
8

9
    ms(q, l, m), ms(q, m + 1, r);
10

11
    int i = l, j = m + 1, k = 0;
12
    while (i <= m && j <= r) {
13
        if (q[i] <= q[j]) tmp[k++] = q[i++];
14
        else tmp[k++] = q[j++];// 这里可以统计以q[j]为结尾的逆序对数量，全部加起来就是逆序对数量
15
    }
16

17
    while (i <= m) tmp[k++] = q[i++];
18
    while (j <= r) tmp[k++] = q[j++];
19

20
    for (int i = l, j = 0; i <= r; ++i) q[i] = tmp[j++];
21
}

查找#

大小序	条件	位置	过程
升序+	>= target+ \|\| > target+	第一个数	(0n, j取等，中点偏左)
升序+	<= target- \|\| < target-	最后一个数	(-1n-1, i取等，中点偏右)
降序-	<= target- \|\| < target-	第一个数	(0n, j取等，中点偏左)
降序-	>= target+ \|\| > target+	最后一个数	(-1n-1, i取等，中点偏右)

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
int binarySearch(vector<int> arr, int target) {
7
    int i = 0, j = arr.size();
8

9
    while (i < j) {
10
        int m = (i + j) >> 1;
11

12
        if (arr[m] > target) {
13
            j = m;
14
        }
15
        else {
16
            i = m + 1;
17
        }
18
    }
19

20
    return j;
21
}

抽象代数#

结构	结构性质	逆运算
$\oplus$ ,Z	阿贝尔群	$\oplus$
$\odot$ ,Z	阿贝尔群	$\odot$
$+$ ,R	阿贝尔群	-
$\times$ ,R/{0}	阿贝尔群	/
&	半格（无逆元的交换群）	$\varnothing$
\|	半格（无逆元的交换群）	$\varnothing$
max	半格（无逆元的交换群）	$\varnothing$
min	半格（无逆元的交换群）	$\varnothing$
$+$ ,所有矩阵，即矩阵加法	阿贝尔群	-
$\times$ ,所有矩阵，即矩阵乘法	幺半群	$\varnothing$

$\oplus$ #

和同或有 $a \odot b = a \oplus b \oplus 1$ 的关系

& 和 |和max和min#

a | b = a + b\leftrightarrow a \& b == 0

&

单位元：-1

性质

$0 \le a\space \& \space b \le min(a,b)当且仅当a=b时取等，全存在0时最小$

|#

单位元：0

性质

$max(a,b) \le a\space | \space b \le a + b当且仅当a和b相加无进位时取等$

max#

单位元：LLONG_MAX

min#

单位元：LLONG_MIN

高精度#

高 + 高#

1
// 高 + 高
2
vector<int> add(vector<int> a, vector<int> b) {
3
    if (a.size() < b.size()) return add(b, a);
4

5
    vector<int> c;
6

7
    int t = 0;
8
    for (int i = 0; i < a.size(); ++i) {
9
        t += a[i];
10
        if (i < b.size()) t += b[i];
11
        c.emplace_back(t % 10);
12
        t /= 10;
13
    }
14

15
    if (t) c.emplace_back(t);
16
    return c;
17
}

高 - 高#

1
// 高 - 高
2
vector<int> sub(vector<int> a, vector<int> b) {
3
    vector<int> c;
4

5
    int t = 0;
6
    for (int i = 0; i < a.size(); ++i) {
7
        t += a[i];
8
        if (i < b.size()) t -= b[i];
9
        c.emplace_back((t + 10) % 10);
10
        if (t < 0) t = -1;
11
    }
12

13
    while (c.size() > 1 && c.back() == 0) c.pop_back();
14

15
    return c;
16
}

高 * 低#

1
// 高 * 低
2
vector<int> mul(vector<int> a, int b) {
3
    vector<int> c;
4

5
    int t = 0;
6
    for (int i = 0; i < a.size() || t; ++i) {
7
        if (i < a.size()) t += a[i] * b;
8
        c.emplace_back(t % 10);
9
        t /= 10;
10
    }
11

12
    while (c.size() > 1 && c.back() == 0) c.pop_back();
13
    return c;
14
}

高 / 低#

1
// 高 / 低
2
vector<int> div(vector<int> a, int b) {
3
    vector<int> c;
4

5
    int r = 0;
6
    for (int i = a.size() - 1; i >= 0; --i) {
7
        r = r * 10 + a[i];
8
        c.emplace_back(r / b);
9
        r %= b;
10
    }
11

12
    reverse(c.begin(), c.end());
13
    while (c.size() > 1 && c.back() == 0) c.pop_back();
14
    return c;
15
}

高 * 高#

1
vector<int> mul(vector<int>& a, vector<int>& b) {
2
    vector<int> c(a.size() + b.size(), 0);
3

4
    for (int i = 0; i < a.size(); ++i) {
5
        for (int j = 0; j < b.size(); ++j) {
6
            c[i + j] += a[i] * b[j];
7
        }
8
    }
9

10
    int t = 0;
11
    for (int i = 0; i < c.size(); ++i) {
12
        t += c[i];
13
        c[i] = t % 10;
14
        t /= 10;
15
    }
16

17
    while (c.size() > 1 && c.back() == 0) c.pop_back();
18
    return c;
19
}

高 / 高#

仅仅适合小数据

1
bool cmp(vector<int>& a, vector<int>& b) {
2
    if (a.size() != b.size()) return a.size() > b.size();
3
    for (int i = a.size() - 1; i >= 0; --i)
4
        if (a[i] != b[i]) return a[i] > b[i];
5
    return true;
6
}
7

8
vector<int> div(vector<int>& a, vector<int>& b, vector<int>& r) {
9
    vector<int> c;
10
    r.clear();
11

12
    for (int i = a.size() - 1; i >= 0; --i) {
13
        r.insert(r.begin(), a[i]);
14

15
        while (r.size() > 1 && r.back() == 0) r.pop_back();
16

17
        int x = 0;
18
        while (cmp(r, b)) {
19
            r = sub(r, b);
20
            x++;
21
        }
22

23
        c.push_back(x);
24
    }
25

26
    reverse(c.begin(), c.end());
27
    while (c.size() > 1 && c.back() == 0) c.pop_back();
28

29
    return c;
30
}

多项式#

基础约定#

1
// a[i] 表示 x^i 的系数（低位在前）
2
using poly = vector<int>;
3

4
const int mod = 998244353;
5
const int G = 3;

加法#

1
poly add(poly a, poly b) {
2
    if (a.size() < b.size()) swap(a, b);
3
    for (int i = 0; i < b.size(); ++i)
4
        a[i] = (a[i] + b[i]) % mod;
5
    return a;
6
}

减法#

1
poly sub(poly a, poly b) {
2
    if (a.size() < b.size()) a.resize(b.size());
3
    for (int i = 0; i < b.size(); ++i)
4
        a[i] = (a[i] - b[i] + mod) % mod;
5

6
    while (a.size() > 1 && a.back() == 0) a.pop_back();
7
    return a;
8
}

朴素乘法#

1
poly mul(poly a, poly b) {
2
    poly c(a.size() + b.size() - 1);
3

4
    for (int i = 0; i < a.size(); ++i)
5
        for (int j = 0; j < b.size(); ++j)
6
            c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % mod;
7

8
    return c;
9
}

NTT乘除法#

快速幂#

1
int qpow(int a, int b) {
2
    int res = 1;
3
    while (b) {
4
        if (b & 1) res = 1LL * res * a % mod;
5
        a = 1LL * a * a % mod;
6
        b >>= 1;
7
    }
8
    return res;
9
}
10

11
int inv(int x) {
12
    return qpow(x, mod - 2);
13
}

核心#

1
void ntt(poly &a, bool invert) {
2
    int n = a.size();
3
    static vector<int> rev;
4
    static vector<int> roots{0, 1};
5

6
    if ((int)rev.size() != n) {
7
        int k = __builtin_ctz(n);
8
        rev.resize(n);
9
        for (int i = 0; i < n; ++i)
10
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
11
    }
12

13
    if ((int)roots.size() < n) {
14
        int k = __builtin_ctz(roots.size());
15
        roots.resize(n);
16
        while ((1 << k) < n) {
17
            int e = qpow(G, (mod - 1) >> (k + 1));
18
            for (int i = 1 << (k - 1); i < (1 << k); ++i) {
19
                roots[2 * i] = roots[i];
20
                roots[2 * i + 1] = 1LL * roots[i] * e % mod;
21
            }
22
            k++;
23
        }
24
    }
25

26
    for (int i = 0; i < n; ++i)
27
        if (i < rev[i]) swap(a[i], a[rev[i]]);
28

29
    for (int len = 1; len < n; len <<= 1) {
30
        for (int i = 0; i < n; i += 2 * len) {
31
            for (int j = 0; j < len; ++j) {
32
                int u = a[i + j];
33
                int v = 1LL * a[i + j + len] * roots[len + j] % mod;
34
                a[i + j] = (u + v) % mod;
35
                a[i + j + len] = (u - v + mod) % mod;
36
            }
37
        }
38
    }
39

40
    if (invert) {
41
        reverse(a.begin() + 1, a.end());
42
        int inv_n = inv(n);
43
        for (int &x : a) x = 1LL * x * inv_n % mod;
44
    }
45
}

NTT乘法#

1
poly mul_ntt(poly a, poly b) {
2
    int n = 1;
3
    while (n < a.size() + b.size()) n <<= 1;
4

5
    a.resize(n);
6
    b.resize(n);
7

8
    ntt(a, false);
9
    ntt(b, false);
10

11
    for (int i = 0; i < n; ++i)
12
        a[i] = 1LL * a[i] * b[i] % mod;
13

14
    ntt(a, true);
15

16
    return a;
17
}

NTT带余除法#

1
poly rev(poly a) {
2
    reverse(a.begin(), a.end());
3
    return a;
4
}
5

6
poly poly_div(poly a, poly b) {
7
    int n = a.size() - 1;
8
    int m = b.size() - 1;
9

10
    if (n < m) return {0};
11

12
    int k = n - m + 1;
13

14
    poly ra = rev(a);
15
    poly rb = rev(b);
16

17
    rb.resize(k);
18

19
    poly inv_rb = poly_inv(rb, k);
20

21
    poly rq = mul_ntt(ra, inv_rb);
22
    rq.resize(k);
23

24
    poly q = rev(rq);
25
    return q;
26
}
27

28
poly poly_mod(poly a, poly b) {
29
    poly q = poly_div(a, b);
30
    poly prod = mul_ntt(b, q);
31

32
    poly r = sub(a, prod);
33

34
    r.resize(b.size() - 1);
35

36
    while (r.size() > 1 && r.back() == 0) r.pop_back();
37
    return r;
38
}
39

40
pair<poly, poly> poly_divmod(poly a, poly b) {
41
    poly q = poly_div(a, b);
42
    poly r = poly_mod(a, b);
43
    return {q, r};
44
}

乘法逆元#

a[0] != 0

1
poly poly_inv(poly a, int n) {
2
    if (n == 1) return {inv(a[0])};
3

4
    poly b = poly_inv(a, (n + 1) >> 1);
5

6
    int size = 1;
7
    while (size < 2 * n) size <<= 1;
8

9
    poly tmp = a;
10
    tmp.resize(size);
11
    b.resize(size);
12

13
    ntt(tmp, false);
14
    ntt(b, false);
15

16
    for (int i = 0; i < size; ++i)
17
        b[i] = 1LL * b[i] * (2 - 1LL * tmp[i] * b[i] % mod + mod) % mod;
18

19
    ntt(b, true);
20
    b.resize(n);
21

22
    return b;
23
}

导数#

1
poly deriv(poly a) {
2
    if (a.size() == 1) return {0};
3
    for (int i = 1; i < a.size(); ++i)
4
        a[i - 1] = 1LL * a[i] * i % mod;
5
    a.pop_back();
6
    return a;
7
}

积分#

1
poly integ(poly a) {
2
    a.push_back(0);
3
    for (int i = a.size() - 1; i > 0; --i)
4
        a[i] = 1LL * a[i - 1] * inv(i) % mod;
5
    a[0] = 0;
6
    return a;
7
}

多项式ln#

1
poly poly_ln(poly a, int n) {
2
    poly da = deriv(a);
3
    poly inva = poly_inv(a, n);
4

5
    poly res = mul_ntt(da, inva);
6
    res.resize(n - 1);
7

8
    return integ(res);
9
}

多项式exp#

1
poly poly_exp(poly a, int n) {
2
    if (n == 1) return {1};
3

4
    poly b = poly_exp(a, (n + 1) >> 1);
5

6
    poly ln_b = poly_ln(b, n);
7

8
    poly diff = sub(a, ln_b);
9
    diff[0] = (diff[0] + 1) % mod;
10

11
    b = mul_ntt(b, diff);
12
    b.resize(n);
13

14
    return b;
15
}

多项式快速幂#

1
poly poly_pow(poly a, int k, int n) {
2
    poly ln_a = poly_ln(a, n);
3

4
    for (int &x : ln_a)
5
        x = 1LL * x * k % mod;
6

7
    return poly_exp(ln_a, n);
8
}

线性基#

普通#

1
struct LinearBasis {
2
    static const int LOG = 60; // long long
3

4
    long long d[LOG + 1]{};
5

6
    // 插入一个数
7
    void insert(long long x) {
8
        for (int i = LOG; i >= 0; --i) {
9
            if (!(x >> i & 1)) continue;
10

11
            if (!d[i]) {
12
                d[i] = x;
13
                return;
14
            }
15

16
            x ^= d[i];
17
        }
18
    }
19

20
    // 查询最大异或值
21
    long long query_max() {
22
        long long res = 0;
23
        for (int i = LOG; i >= 0; --i)
24
            res = max(res, res ^ d[i]);
25
        return res;
26
    }
27
};

可求第k小#

1
struct LinearBasis {
2
    static const int LOG = 60;
3
    long long d[LOG + 1]{};
4
    vector<long long> p; // 重构后的基
5

6
    void insert(long long x) {
7
        for (int i = LOG; i >= 0; --i) {
8
            if (!(x >> i & 1)) continue;
9
            if (!d[i]) {
10
                d[i] = x;
11
                return;
12
            }
13
            x ^= d[i];
14
        }
15
    }
16

17
    // 重构（变成上三角）
18
    void rebuild() {
19
        for (int i = 0; i <= LOG; ++i)
20
            for (int j = 0; j < i; ++j)
21
                if (d[i] >> j & 1)
22
                    d[i] ^= d[j];
23

24
        for (int i = 0; i <= LOG; ++i)
25
            if (d[i]) p.push_back(d[i]);
26
    }
27

28
    // 第 k 小（0-based）
29
    long long kth(long long k) {
30
        if (k >= (1LL << p.size())) return -1;
31

32
        long long res = 0;
33
        for (int i = 0; i < p.size(); ++i)
34
            if (k >> i & 1)
35
                res ^= p[i];
36
        return res;
37
    }
38
};

高斯消元#

浮点数#

1
const int N = 110;
2
const double eps = 1e-8;
3

4
double a[N][N]; // 增广矩阵 n 行 n+1 列
5

6
// 返回值：
7
// 0 = 无解
8
// 1 = 唯一解
9
// 2 = 无穷多解
10
int gauss(int n) {
11
    int r = 0, c = 0;
12

13
    while (c < n) {
14
        // 1️ 找主元（绝对值最大）
15
        int t = r;
16
        for (int i = r; i < n; ++i)
17
            if (fabs(a[i][c]) > fabs(a[t][c]))
18
                t = i;
19

20
        // 2️ 这一列全是0 → 自由变量
21
        if (fabs(a[t][c]) < eps) {
22
            c++;
23
            continue;
24
        }
25

26
        // 3️ 换行
27
        for (int j = c; j <= n; ++j)
28
            swap(a[t][j], a[r][j]);
29

30
        // 4️ 归一化
31
        double div = a[r][c];
32
        for (int j = c; j <= n; ++j)
33
            a[r][j] /= div;
34

35
        // 5️ 消元（上下都消）
36
        for (int i = 0; i < n; ++i) {
37
            if (i != r && fabs(a[i][c]) > eps) {
38
                double factor = a[i][c];
39
                for (int j = c; j <= n; ++j)
40
                    a[i][j] -= factor * a[r][j];
41
            }
42
        }
43

44
        r++, c++;
45
    }
46

47
    // 6️ 判断解的情况
48
    for (int i = r; i < n; ++i)
49
        if (fabs(a[i][n]) > eps)
50
            return 0; // 无解
51

52
    return r < n ? 2 : 1;
53
}

模2高斯消元#

1
const int N = 110;
2

3
int a[N][N]; // n 行 n+1 列，值为 0/1
4

5
// 返回：0无解，1唯一解，2多解
6
int gauss_xor(int n) {
7
    int r = 0;
8

9
    for (int c = 0; c < n; ++c) {
10
        int t = r;
11
        for (int i = r; i < n; ++i)
12
            if (a[i][c]) {
13
                t = i;
14
                break;
15
            }
16

17
        if (!a[t][c]) continue;
18

19
        for (int j = c; j <= n; ++j)
20
            swap(a[t][j], a[r][j]);
21

22
        for (int i = 0; i < n; ++i)
23
            if (i != r && a[i][c])
24
                for (int j = c; j <= n; ++j)
25
                    a[i][j] ^= a[r][j];
26

27
        r++;
28
    }
29

30
    for (int i = r; i < n; ++i)
31
        if (a[i][n]) return 0;
32

33
    return r < n ? 2 : 1;
34
}

位运算#

格雷码#

正变换#

1
int get(int x) {
2
  return x ^ (x >> 1);
3
}

逆变换#

1
int x = g;
2
for (; g; g >>= 1) x ^= g;
3
return x;

常用函数#

bit_width(x) = 1 + floor(log2(x))#

1
int bit_width(unsigned x) {
2
  int res = 0;
3
  while (x) {
4
    ++res;
5
    x >>= 1;
6
  }
7
  return res;
8
}

countr_zero(x) = bit_width(lowbit(x)) - 1#

1
int countr_zero(unsigned x) {
2
  if (x == 0) return 32;
3
  return bit_width(x & -x) - 1;
4
}

组合数学#

组合#

1
class Solution {
2
public:
3
    vector<vector<int>> combine(int n, int k) {
4
        vector<vector<int>> ans;
5

6
        vector<int> unit;
7
        auto dfs = [&](auto&& dfs, int elem) {
8
            int limit = k - unit.size();
9
            if (limit == 0) {
10
                return;
11
            }
12

13
            unit.push_back(elem);
14

15
            if (limit == 1) {
16
                ans.push_back(unit);
17
            }
18

19
            for (int index = elem + 1; index <= n; ++index) {
20
                dfs(dfs, index);
21
            }
22

23
            unit.pop_back();
24
        };
25

26
        for (int i = 1; i <= n; ++i) {
27
            dfs(dfs, i);
28
        }
29

30
        return ans;
31
    }
32
};

排列#

负数组合#

C^k_{-n} = (-1)^k \cdot C^k_{n+k-1}

Lucas定理#

p为素数，其余为自然数

\begin{pmatrix} m \\ n \end{pmatrix} \space mod\space p = \begin{pmatrix} \lfloor \frac{m}{p} \rfloor \\ \lfloor \frac{n}{p} \rfloor \\ \end{pmatrix} \cdot \begin{pmatrix} m\space mod\space p\\ n\space mod\space p\\ \end{pmatrix} \space mod\space p

实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
const mod N = 1e5;
5
const ll mod = 998244353;//其实没什么用，lucas只能用于小质数模数
6
ll fact[N], ifact[N];
7

8
ll qp(ll a, ll b, ll p) {
9
    ll res = 1;
10
    while (b) {
11
        if (b & 1) res = res * a % p;
12
        a = a * a % p;
13
        b >>= 1;
14
    }
15
    return res;
16
}
17

18
void init(int n) {
19
    fact[0] = 1;
20
    for (int i = 1; i <= n; ++i) fact[i] = i * fact[i - 1] % mod;
21
    for (int i = 0; i <= n; ++i) ifact[i] = qp(fact[i], mod - 2, mod);
22
}
23

24
ll c(ll n, ll k) {
25
    if (k > n) return 0;
26
    return fact[n] % mod * ifact[k] % mod * ifact[n - k] % mod;
27
}
28

29
ll lucas(ll n, ll k) {
30
    if (!k) return 1;
31
    return c(n % mod, k % mod) * lucas(n / mod, k / mod) % mod;
32
}

矩阵快速幂#

将快速幂思想迁移到递推式

以斐波那契数列为例

\begin{bmatrix} F[k] \\ F[k-1] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^{k-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} =A^{k-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} ,\quad k=1 \ldots n

使用矩阵快速幂的前提是所求值可化为上一列各元素的线性组合，需要是常数，以 $F[i]=(ai+b)\times q^i$ 为例有

\begin{bmatrix} F[k] \\ a^k \end{bmatrix} = \begin{bmatrix} q & q \\ 0 & q \end{bmatrix} ^{k-1} \begin{bmatrix} b\\ a \end{bmatrix} ,\quad k = 1\ldots n

1
using ll = long long;
2

3
vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>> b, ll mod) {
4
    int n = a.size(), mid = a[0].size(), m = b[0].size();
5

6
    vector<vector<ll>> res(n, vector<ll>(m, 0));
7

8
    for (int i = 0; i < n; ++i) {
9
        for (int j = 0; j < m; ++j) {
10
            for (int k = 0; k < mid; ++k) {
11
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
12
            }
13
        }
14
    }
15

16
    return res;
17
}
18

19
vector<vector<ll>> mmi(vector<vector<ll>> A, ll b, ll mod) {
20
    vector<vector<ll>> res = {{1 % mod, 0}, {0, 1 % mod}};
21
    while (b) {
22
        if (b & 1) res = mul(res, A, mod);
23
        A = mul(A, A, mod);
24
        b >>= 1;
25
    }
26
    return res;
27
}

对于特殊的前缀和，也可以用矩阵快速幂进行计算，以

F[n] = \sum_{i = 1}^{n}{(ai+b) \times q^i}

为例，相对于 $F[i]=(ai+b)\times q^i$ 需要多留一行给求和积累效果

\begin{bmatrix} F[k - 1] \\ f[k] \\ a^k \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 \\ 0 & q & q \\ 0 & 0 & q \end{bmatrix} ^{k-1} \begin{bmatrix} 0\\ b \\ a \end{bmatrix} ,\quad k = 1\ldots n

总结来说，矩阵快速幂有以下几个值得注意的点

前缀和只有其本身和组成单位有关，权为1
等比数列只和其所在列有关，权为q
$iq^i$ 和其所在列和对应和等比数列有关，权都为q
等差数列可看作常数C的前缀和

可见，矩阵快速幂对若干个等差数列和等比数列的线性组合和前缀和都适用，其他并不适用

矩阵快速幂如果用二维vector或者struct自行实现会被卡常，需要转化为维护变换的几个值和ans的几个值，

这里上三角矩阵的幂仍然是上三角矩阵，故变换可等价为右上角的6个值的递归，由于对角线独立幂化，故最左上角的1为定值1

下三角矩阵和上三角矩阵性质相同，而反上下三角矩阵性质则大有不同

数论#

中国剩余定理(CRT)#

m_2 \cdot m_3 \cdot x \equiv 1 \pmod{m_1}

a_1 \cdot (m_2 \cdot m_3 \cdot x) \equiv a_1 \pmod{m_1}

扩展CRT#

1
using ll = long long;
2

3
// 扩展gcd
4
ll exgcd(ll a, ll b, ll &x, ll &y) {
5
    if (!b) {
6
        x = 1; y = 0;
7
        return a;
8
    }
9
    ll x1, y1;
10
    ll g = exgcd(b, a % b, x1, y1);
11
    x = y1;
12
    y = x1 - a / b * y1;
13
    return g;
14
}
15

16
// 扩展CRT
17
// a[i] ≡ x (mod m[i])
18
// 返回 (x, lcm) 或 (-1, -1) 表示无解
19
pair<ll, ll> excrt(vector<ll>& a, vector<ll>& m) {
20
    ll A = a[0], M = m[0];
21

22
    for (int i = 1; i < a.size(); ++i) {
23
        ll a2 = a[i], m2 = m[i];
24

25
        ll x, y;
26
        ll g = exgcd(M, m2, x, y);
27

28
        ll c = a2 - A;
29
        if (c % g != 0) return {-1, -1}; // 无解
30

31
        // 防溢出写法
32
        ll mod = m2 / g;
33
        x = (__int128)x * (c / g) % mod;
34

35
        A = A + x * M;
36
        M = M / g * m2;
37

38
        A = (A % M + M) % M;
39
    }
40

41
    return {A, M};
42
}

快速乘#

1
ll qmul(ll a, ll b, ll p) {
2
  ll q = (ld)a / p * b;
3
  ll res = (ull)a * b - (ull)q * p;
4
    return (res + p) % p;
5
}

扩展欧几里得#

1
pair<int, int> extgcd(int a, int b) {
2
  if (!b) return make_pair(1, 0);
3
  auto [s, t] = extgcd(b, a % b);
4
    return make_pair(t, s - a / b * t);//t * (1,s/t-a/b)
5
}

质数#

筛法#

线性筛法

1
int primes[N], idx;
2
bool vis[N];
3
void getp(int n) {
4
    memset(primes, 0, sizeof primes);
5
    primes[1] = 0;
6
    for (int i = 2; i <= n; ++i) {
7
        if (!vis[i]) primes[++idx] = i;
8
    for (int j = 1; i * primes[j] <= n; ++j) {
9
      vis[i * primes[j]] = 1;
10
            if (i % primes[j] == 0) break;
11
        }
12
    }
13
}

埃筛

1
int primes[N], idx;
2
bool vis[N];
3
void getp(int n) {
4
    for (int i = 2; i <= n; ++i) {
5
        if (vis[i]) continue;
6
        primes[idx++] = i;
7
        for (int j = i; j <= n / j; ++j) {
8
            vis[j * i] = 1;
9
        }
10
    }
11
}

约数#

质因数分解#

纯暴力

1
unordered_map<int, int> pcnt;
2

3
void getfactor(int n) {
4
    for (int i = 2; i <= n / i; ++i) {
5
        while (n % i == 0) {
6
            ++pcnt[i];
7
            n /= i;
8
        }
9
    }
10
}

阶乘的质因数分解

p指数的数量=\sum_{k = 0}^{\infty}{\lfloor \frac{N}{p^k} \rfloor}

约数计算#

质因数分解p_0^{c_0} p_1^{c_1} \cdots p_k^{c_k}

约数之和=\sum_{i = 0}^{k}\sum_{j=0}^{c_i}{p_i^j}

约数的数量=\prod_{i=0}^{k}{(c_i + 1)}

欧拉函数#

\varphi(p) = [1,p - 1]内与p互质的数的数量

性质#

gcd(m,n) = 1 \Rightarrow \varphi(mn) = \varphi(m) \cdot \varphi(n)

图论#

基础约定#

1
using PII = pair<int, int>;
2

3
const int INF = 0x3f3f3f3f;
4
const int N = 1e3;
5

6
int h[N], e[N], ne[N], idx, w[N];
7
int g[N][N];
8
int d[N][N];
9
void initGraph() {
10
    memset(h, -1, sizeof h);
11
    idx = 0;
12
}
13

14
// 无向图
15
struct Edge {
16
    int a, b, w;
17
    bool operator < (const Edge &W) const { return w < W.w; }
18
} edges[N];
19

20
// 最短路
21
int dist[N];
22
bool st[N];

最短路#

单源最短路#

Dijkstra#

朴素

1
// 朴素Dijkstra
2
int dijkstra(int s, int n) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    for (int k = 0; k < n - 1; ++k) {
7
        int t = 0;
8
        for (int i = 1; i <= n; ++i) if (!st[i] && (!t || dist[i] < dist[t])) t = i;
9
        for (int i = 1; i <= n; ++i) dist[i] = min(dist[i], dist[t] + g[t][i]);
10
        st[t] = 1;
11
    }
12

13
    return dist[n] == INF ? -1 : dist[n];
14
}

堆优化

1
// 堆优化Dijkstra
2
int Dijkstra(int s, int n) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    priority_queue<PII, vector<PII>, greater<PII>> q;
7
    q.push({0, s});
8

9
    while(q.size()) {
10
        PII t = q.top();
11
        int ver = t.second, dis = t.first;
12
        if (st[ver]) continue;st[ver] = 1;
13

14
        for (int i = h[ver]; i != -1; i = ne[i]) {
15
            int j = e[i];
16
            if (dist[j] > dist[ver] + w[i]) {
17
                dist[j] = dist[ver] + w[i];
18
                q.push({dist[j], j});
19
            }
20
        }
21
    }
22

23
    return dist[n] == INF ? -1 : dist[n];
24
}

Bellmanford#

朴素

1
// Bellmanford
2
int Bellmanford(int s, int n, int m) {
3
    memset(dist, 0x3f, sizeof dist);
4
    dist[s] = 0;
5

6
    for (int k = 0; k < n; ++k) {
7
        for (int i = 1; i <= n; ++i) {
8
            int a = i;
9
            for (int j = h[i]; j != -1; j = ne[j]) {
10
                int b = e[j];
11
                dist[b] = min(dist[b], dist[a] + w[j]);
12
            }
13
        }
14
    }
15

16
    return dist[n] > dist[n] >> 1 ? -1 : dist[n];
17
}

SPFA

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

4
using pii = pair<int, int>;
5
const int INF = 0x3f3f3f3f;
6
const int N = 100005;
7

8
vector<pii> g[N]; // {to, weight}
9
int dist[N];
10
bool inq[N];      // 是否在队列中
11
int cnt[N];       // 入队次数（用于判负环）
12

13
// 返回：true 表示无负环，false 表示存在负环
14
bool spfa(int n, int s) {
15
    memset(dist, 0x3f, sizeof dist);
16
    memset(inq, 0, sizeof inq);
17
    memset(cnt, 0, sizeof cnt);
18

19
    queue<int> q;
20
    dist[s] = 0;
21

22
    q.push(s);
23
    inq[s] = true;
24
    cnt[s] = 1;
25

26
    while (!q.empty()) {
27
        int u = q.front(); q.pop();
28
        inq[u] = false;
29

30
        for (auto [v, w] : g[u]) {
31
            if (dist[v] > dist[u] + w) {
32
                dist[v] = dist[u] + w;
33

34
                if (!inq[v]) {
35
                    q.push(v);
36
                    inq[v] = true;
37
                    cnt[v]++;
38

39
                    // 🚨 负环判断
40
                    if (cnt[v] >= n) return false;
41
                }
42
            }
43
        }
44
    }
45

46
    return true;
47
}

多源最短路#

Floyd#

1
// Floyd
2
void floyd(int n) {
3
    for (int k = 1; k <= n; ++k) {
4
        for (int i = 1; i <= n; ++i) {
5
            for (int j = 1; j <= n; ++j) {
6
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
7
            }
8
        }
9
    }
10
}

最小生成树#

Prim#

1
int prim() {
2
    memset(dist, 0x3f, sizeof dist);
3
    memset(st, 0, sizeof st);
4

5
    dist[1] = 0;
6
    int res = 0;
7

8
    for (int i = 0; i < n; ++i) {
9
        int t = -1;
10
        for (int j = 1; j <= n; ++j)
11
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
12
                t = j;
13

14
        if (dist[t] == INF) return INF;
15

16
        res += dist[t];
17
        st[t] = 1;
18

19
        for (int j = 1; j <= n; ++j)
20
            dist[j] = min(dist[j], g[t][j]);
21
    }
22

23
    return res;
24
}

Kruscal#

1
struct Edge {
2
    int a, b, w;
3
    bool operator<(const Edge& other) const {
4
        return w < other.w;
5
    }
6
};
7

8
int p[N];
9

10
int find(int x) {
11
    if (p[x] != x) p[x] = find(p[x]);
12
    return p[x];
13
}
14

15
int kruskal() {
16
    for (int i = 1; i <= n; ++i) p[i] = i;
17

18
    sort(ed, ed + m);
19

20
    int res = 0, cnt = 0;
21

22
    for (int i = 0; i < m; ++i) {
23
        int a = ed[i].a, b = ed[i].b, w = ed[i].w;
24

25
        int pa = find(a), pb = find(b);
26

27
        if (pa != pb) {
28
            p[pa] = pb;
29
            res += w;
30
            cnt++;
31
        }
32
    }
33

34
    return cnt == n - 1 ? res : INF;
35
}

Tarjan#

求强连通分量#

1
const int N = 100005;
2

3
vector<int> g[N];
4

5
int dfn[N], low[N], timestamp;
6
int stk[N], top;
7
bool in_stk[N];
8

9
int scc_id[N], scc_cnt;
10

11
void tarjan(int u) {
12
    dfn[u] = low[u] = ++timestamp;
13
    stk[++top] = u;
14
    in_stk[u] = true;
15

16
    for (int v : g[u]) {
17
        if (!dfn[v]) {
18
            tarjan(v);
19
            low[u] = min(low[u], low[v]);
20
        }
21
        else if (in_stk[v]) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25

26
    // 找到一个 SCC
27
    if (dfn[u] == low[u]) {
28
        ++scc_cnt;
29
        int y;
30
        do {
31
            y = stk[top--];
32
            in_stk[y] = false;
33
            scc_id[y] = scc_cnt;
34
        } while (y != u);
35
    }
36
}

Tarjan 求割点（无向图）#

1
vector<int> g[N];
2
int dfn[N], low[N], timestamp;
3
bool is_cut[N];
4

5
void tarjan(int u, int parent) {
6
    dfn[u] = low[u] = ++timestamp;
7

8
    int child = 0;
9

10
    for (int v : g[u]) {
11
        if (!dfn[v]) {
12
            tarjan(v, u);
13
            low[u] = min(low[u], low[v]);
14

15
            // 割点判断
16
            if (parent != -1 && low[v] >= dfn[u])
17
                is_cut[u] = true;
18

19
            child++;
20
        }
21
        else if (v != parent) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25

26
    // 根节点特殊判断
27
    if (parent == -1 && child > 1)
28
        is_cut[u] = true;
29
}

求桥#

1
struct Edge {
2
    int to, id;
3
};
4

5
vector<Edge> g[N];
6
int dfn[N], low[N], timestamp;
7
bool is_bridge[N];
8

9
void tarjan(int u, int in_edge) {
10
    dfn[u] = low[u] = ++timestamp;
11

12
    for (auto [v, id] : g[u]) {
13
        if (!dfn[v]) {
14
            tarjan(v, id);
15
            low[u] = min(low[u], low[v]);
16

17
            //  桥判断
18
            if (low[v] > dfn[u])
19
                is_bridge[id] = true;
20
        }
21
        else if (id != in_edge) {
22
            low[u] = min(low[u], dfn[v]);
23
        }
24
    }
25
}

动态规划#

线性DP#

有两种，最大子数组和这种求连续区间的，和最长上升子序列和最长公共子序列这种求序列的

最长公共子序列#

对于字符串s，t

假如s[i] == s[j], 有

都不选 = dfs(i - 1, j - 1)

不选s = dfs(i - 1, j)，t是不确定的

不选t = dfs(i, j - 1)，s是不确定的

不选s，假如后续也不选t了则应有dfs(i - 1, j) =dfs(i - 1, j - 1) < 都选，假如后续选了t则dfs(i - 1, j ) = dfs(i - k, j - 1) + 1,由于子串i - k,j - 1是i - 1, j -1的子串，故dfs(i - k, j - 1) <= x,dfs(i - 1, j) <= x + 1，故不需考虑不选其中1个的情况

背包DP#

01背包#

类型	求最大值	求最小值
至多 (≤ C)	f[0..C] = 0	一般不常见（不选就是0，已最小）
恰好 (= C)	f[0] = 0，其余 -∞	f[0] = 0，其余 +∞
至少 (≥ C)	不常见	f[0] = 0，其余 +∞

数位DP#

单上界数位dp#

一般用于计数算1-n，若是区间[l, r]则通过下列公式计算

总数 = S(r) - S(l - 1)

区间数位dp#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
using ld = long double;
7

8
ll p10[16];
9
ll memo[20][20];
10
bool vis[20][20];
11
string lowS, highS;
12
int n;
13

14
ll dfs(int i, bool tl, bool tr, int k) {
15
    if (i == n) return 0;
16
    if (!tl && !tr && vis[i][k]) return memo[i][k];
17

18
    int lo = tl ? (lowS[i] - '0') : 0;
19
    int hi = tr ? (highS[i] - '0') : 9;
20

21
    ll best  = -1;
22
    for (int d = lo; d <= hi; ++d) {
23
        bool ntl = tl && (d == lowS[i] - '0');
24
        bool ntr = tr && (d == highS[i] - '0');
25
        ll cur;
26
        if (!k && !d) {
27
            cur = dfs(i + 1, ntl, ntr, 0);
28
        }
29
        else cur = 1LL * d * p10[k] + dfs(i + 1, ntl, ntr, k + 1);
30

31
        best = max(best, cur);
32
    }
33

34
    if (!tl && !tr) {
35
        vis[i][k] = 1;
36
        memo[i][k] = best;
37
    }
38
    return best;
39
}
40

41
int main() {
42
    ios::sync_with_stdio(false);cin.tie(nullptr);
43
    int t;cin>>t;
44
    p10[0] = 1;
45
    for (int i = 1; i < 15; ++i) p10[i] = 10 * p10[i - 1];
46

47
    while(t--) {
48
        ll l,r;cin>>l>>r;
49
        highS = to_string(r);
50
        string tmp = to_string(l);
51
        lowS = string(highS.size() - tmp.size(), '0') + tmp;
52
        memset(vis, 0, sizeof vis);
53
        n = highS.size();
54

55
        ll ans = dfs(0, 1, 1, 0);
56
        cout << ans << '\n';
57
    }
58
}

对于tl = 1, tr = 1的状态只有一条路径转移路径通往该状态，所以不用缓存，tl = 0, tr = 0的状态有多条路径，所以需要缓存避免重复计算。

情况	is_num 放不放进 memo？
有 mask/k 等变量能区分开没开始	不用放（已被隐含编码）
没有其他变量区分，且两种都缓存	必须放（否则值混淆）
没有其他变量区分，但只缓存 is_num=true	不用放（false 只走一次，不缓存）

问题类型	前导零有害？	需要 is_num？
数位之和	无害（贡献 0）	不需要
是否含某数字	无害（0 不碍事）	不需要
数位互不相同	有害（假装用了 0）	需要
相邻/递增/递减	有害（假装有前一位）	需要
首位特殊约束	有害（谁是首位？）	需要
位权/翻转相关	有害（位权偏移）	需要（甚至要 k）

数据结构#

单调栈#

找左右第一个小于的是递增栈，小于号朝向欲push的元素，大于的是递减栈，大于号朝向欲push的元素

左边第一个，从左到右top幸存者是淘汰者的答案，意味着下一层是其上一层的答案，从右到左淘汰者是top被淘汰者的答案，
右边第一个，从右到左top幸存者是淘汰者的答案，意味着下一层是其上一层的答案，从左到右淘汰者是top被淘汰者的答案

同向幸存者，反向淘汰者

Manacher#

预处理后的串索引中心idx映射到原串的字符串区间:

[\frac{idx - halfLen[idx]}{2}, \frac{idx + halfLen[idx] - 4}{2}]

原回文串长度 = 回文半径 - 1

1
void solve(string s) {
2
  int n = s.size();
3

4
    string str(2 * n + 3, '#');
5
    str[0] = '$';
6
    for (int i = 0; i < n; ++i) {
7
        str[2 * i + 2]  = s[i];
8
    }
9
    str[2 * n + 2] = '^';
10

11
    vector<int> plen(2 * n + 3);
12
    int boxR = 0, boxM = 0;
13
    for (int i = 2; i < 2 * n + 1; ++i) {
14
        int pl = 1;
15

16
        if (i < boxR) {
17
            pl = min(plen[2 * boxM - i], boxR - i);
18
        }
19

20
        while (str[i - pl] == str[i + pl]) {
21
            ++pl;
22
        }
23

24
        if (i + pl > boxR) {
25
            boxR = i + pl;
26
            boxM = i;
27
        }
28

29
        // 求最长回文子串，或者回文子串数量
30

31
        plen[i] = pl;
32
    }
33
}

莫队#

参考

1
```cpp
2
#include <bits/stdc++.h>
3

4
using namespace std;
5
using ll = long long;
6

7
const int N = 50000 + 1;
8

9
int n, m;
10
int col[N];
11
int block;
12
int cnt[N];
13
ll ans1[N], ans2[N];
14
ll sum;
15

16
struct query {
17
    ll l, r, id;
18

19
    bool operator<(const query& q) const {
20
        int bl = l / block;
21
        int br = q.l / block;
22
        if (bl != br) return bl < br;
23
        if (bl & 1) return r < q.r;
24
        return r > q.r;
25
    }
26

27
} a[N];
28

29
ll gcd(ll a, ll b) {
30
    return b ? gcd(b, a % b) : a;
31
}
32

33
void add(int x) {
34
    sum += cnt[col[x]];
35
    ++cnt[col[x]];
36
}
37

38
void del(int x) {
39
    sum -= (cnt[col[x]] - 1);
40
    --cnt[col[x]];
41
}
42

43
void solve() {
44
    cin >> n >> m;
45
    if (m == 0) return;
46

47
    block = int(n / sqrt(m)) + 1;
48

49
    for (int i = 1; i <= n; ++i) cin >> col[i];
50

51
    for (int i = 0; i < m; ++i) {
52
        cin >> a[i].l >> a[i].r;
53
        a[i].id = i;
54
    }
55
    sort(a, a + m);
56

57
    for (ll i = 0, l = 1, r = 0; i < m; ++i) {
58
        query& q = a[i];
59
        while (l > q.l) add(--l);
60
        while (r < q.r) add(++r);
61
        while (l < q.l) del(l++);
62
        while (r > q.r) del(r--);
63
        ans1[q.id] = sum;
64
        ans2[q.id] = (r - l + 1) * (r - l) / 2;
65
    }
66

67
    for (int i = 0; i < m; ++i) {
68
        if (ans1[i] && ans2[i]) {
69
            ll d = gcd(ans1[i], ans2[i]);
70
            cout << ans1[i] / d << '/' << ans2[i] / d << '\n';
71
        } else {
72
            cout << 0 << '/' << 1 << '\n';
73
        }
74
    }
75
}
76

77
int main() {
78
    cin.tie(nullptr)->sync_with_stdio(false);
79
    solve();
80
}

普通线段树#

1
```c++
2
class SegmentTree {
3
    int n;
4
    vector<int> tr;
5

6
    // 区间业务
7
    int merge_val(int a, int b) const {
8
        return max(a, b);
9
    }
10

11
    // 维护结点
12
    void maintain(int node) {
13
        tr[node] = merge_val(tr[node * 2], tr[node * 2 + 1]);
14
    }
15

16
    // 建树
17
    void build(int node, int l, int r, const vector<int>& a) {
18
        if (l == r) {
19
            tr[node] = a[l];
20
            return;
21
        }
22

23
        int m = l + r >> 1;
24
        build(node * 2, l, m, a);
25
        build(node * 2 + 1, m + 1, r, a);
26
        maintain(node);
27
    }
28

29
    // 单点更新
30
    void update(int node, int l, int r, int i, int val) {
31
        if (l == r) {
32
            tr[node] = merge_val(tr[node], val);
33
            return;
34
        }
35

36
        int m = l + r >> 1;
37
        if (i <= m) {
38
            update(node * 2, l, m, i, val);
39
        } else {
40
            update(node * 2 + 1, m + 1, r, i, val);
41
        }
42
        maintain(node);
43
    }
44

45
    // 区间查询
46
    int query(int node, int l, int r, int ql, int qr) const {
47
        if (ql <= l && r <= qr) {
48
            return tr[node];
49
        }
50

51
        int m = l + r >> 1;
52
        if (qr <= m) {
53
            return query(node * 2, l, m, ql, qr);
54
        }
55
        if (ql > m) {
56
            return query(node * 2 + 1, m + 1, r, ql, qr);
57
        }
58
        int l_res = query(node * 2, l, m, ql, qr);
59
        int r_res = query(node * 2 + 1, m + 1, r, ql, qr);
60
        return merge_val(l_res, r_res);
61
    }
62

63
    // 查找查找区间最左边的某值
64
    int find(int node, int l, int r, int ql, int qr, int val) const {
65
        if (ql > r || qr < l) return -1;
66
        // if (业务剪枝) return -1;
67
        if (l == r && tr[node] == val) return l;
68

69
        int m = l + r >> 1;
70
        int l_res = find(node * 2, l, m, ql, qr, val);
71
        if (l_res != -1) return l_res;
72
        return find(node * 2 + 1, m + 1, r, ql, qr, val);
73
    }
74

75
public:
76

77
    SegmentTree(const vector<int>& a) : n(a.size()), tr(2 << bit_width(n - 1)) {
78
        build(1, 0, n - 1, a);
79
    }
80

81
    void update(int i, int val) {
82
        update(1, 0, n - 1, i, val);
83
    }
84

85
    int query(int ql, int qr) {
86
        return query(1, 0, n - 1, ql, qr);
87
    }
88

89
    int find(int ql, int qr, int val) const {
90
        return find(1, 0, n - 1, ql, qr, val);
91
    }
92
};

树状数组#

1
class FenwickTree {
2
public:
3
  int n;
4
    vector<int> tree;
5

6
    FenwickTree(const vector<int>& a) : n((int)a.size() - 1) {
7
        tree = a;
8
        for (int i = 1; i <= n; ++i) {
9
          // 更新父结点的值
10
          int j = i + (i & -i);
11
          if (j <= n) tree[j] += tree[i];
12
        }
13
    }
14

15
    // 前缀和
16
    int presum(int i) {
17
        int s = 0;
18
        while (i > 0) {
19
            s += tree[i];
20
            i &= i - 1;
21
        }
22
        return s;
23
    }
24

25
    // 单点更新
26
    void update(int i, int delta) {
27
      while (i <= n) {
28
        tree[i] += delta;
29
        i += i & -i;
30
      }
31
    }
32

33
    // 区间和
34
    int query(int l, int r) {
35
        return presum(r) - presum(l - 1);
36
    }
37
};

Trie树#

普通Trie#

1
int son[N][26], cnt[N], idx = 0;
2

3
void insert(char *str) {
4
    int p = 0;
5
    for (int i = 0; str[i]; ++i) {
6
        int e = str[i] - 'a';
7
        if (!son[p][e]) son[p][e] = ++idx;
8
        p = son[p][e];
9
    }
10
    ++cnt[p];
11
}
12

13
int search(char *str) {
14
    int p = 0;
15
    for (int i = 0; str[i]; ++i) {
16
        int e = str[i] - 'a';
17
        if (!son[p][e]) return 0;
18
        p = son[p][e];
19
    }
20

21
    return cnt[p];
22
}

0-1Trie#

1
class Trie {
2
public:
3
    static const int MAXN = 1e4;
4
  int tr[MAXN][2];
5
    int ptr = 0;
6

7
    void insert(int x) {
8
        int p = 0;
9
        for (int i = 31; i >= 0; --i) {
10
      bool c = x >> i & 1;
11
            if (!tr[p][c]) tr[p][c] = ++ptr;
12
            p = tr[p][c];
13
        }
14
    }
15

16
    int find(int x) {
17
        int p = 0, ans = 0;
18
        for (int i = 31; i >= 0; --i) {
19
            bool c = x >> i & 1;
20
            bool b = !c;
21
            if (tr[p][b]) {
22
                ans |= 1 << i;
23
                p = tr[p][b];
24
            } else {
25
                p = tr[p][c];
26
            }
27
        }
28
        return ans;
29
    }
30
};

并查集#

普通并查集#

1
class UnionFind {
2
public:
3
    vector<int> f;
4
    vector<int> sz;
5
    int cc;
6

7
    UnionFind(int n) : f(n), sz(n), cc(n) {
8
        iota(f.begin(), f.end(), 0);
9
    }
10

11
    int find(int x) {
12
        if (f[x] != x) f[x] = find(f[x]);
13
        return f[x];
14
    }
15

16
    bool merge(int from, int to) {
17
        int x = find(from), y = find(to);
18
        if (x == y) return 0;
19
        f[x] = y;
20
        sz[y] += sz[x];
21
        --cc;
22
        return 1;
23
    }
24
};

前缀和#

二维前缀和#

1
int s[N][N];
2

3
// 构建
4
for (int i = 1; i <= n; ++i)
5
    for (int j = 1; j <= m; ++j)
6
        s[i][j] = s[i-1][j] + s[i][j-1]
7
                - s[i-1][j-1] + a[i][j];
8

9
// 查询
10
int get(int x1, int y1, int x2, int y2) {
11
    return s[x2][y2]
12
         - s[x1-1][y2]
13
         - s[x2][y1-1]
14
         + s[x1-1][y1-1];
15
}

二维差分#

1
int a[N][N], b[N][N];
2

3
// 区间加
4
void add(int x1, int y1, int x2, int y2, int k) {
5
    b[x1][y1] += k;
6
    b[x2+1][y1] -= k;
7
    b[x1][y2+1] -= k;
8
    b[x2+1][y2+1] += k;
9
}
10

11
// 还原
12
for (int i = 1; i <= n; ++i) {
13
    for (int j = 1; j <= m; ++j) {
14
        a[i][j] = b[i][j]
15
                + a[i-1][j]
16
                + a[i][j-1]
17
                - a[i-1][j-1];
18
    }
19
}

带权并查集#

1
// 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
2
// 根据题目用 UnionFind<int> uf(n) 或者 UnionFind<long long> uf(n) 初始化
3
template<typename T>
4
class UnionFind {
5
public:
6
    vector<int> fa; // 代表元
7
    vector<T> dis; // dis[x] 表示 x 到（x 所在集合的）代表元的距离
8

9
    UnionFind(int n) : fa(n), dis(n) {
10
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
11
        // 集合 i 的代表元是自己，自己到自己的距离是 0
12
        ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
13
    }
14

15
    // 返回 x 所在集合的代表元
16
    // 同时做路径压缩
17
    int find(int x) {
18
        if (fa[x] != x) {
19
            int root = find(fa[x]);
20
            dis[x] += dis[fa[x]]; // 递归更新 x 到其代表元的距离
21
            fa[x] = root;
22
        }
23
        return fa[x];
24
    }
25

26
    // 判断 x 和 y 是否在同一个集合（同普通并查集）
27
    bool same(int x, int y) {
28
        return find(x) == find(y);
29
    }
30

31
    // 计算从 from 到 to 的相对距离
32
    // 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
33
    T get_relative_distance(int from, int to) {
34
        find(from);
35
        find(to);
36
        // to-from = (x-from) - (x-to) = dis[from] - dis[to]
37
        return dis[from] - dis[to];
38
    }
39

40
    // 合并 from 和 to，新增信息 to - from = value
41
    // 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
42
    // 如果 from 和 to 不在同一个集合，返回 true，否则返回是否与已知信息矛盾
43
    bool merge(int from, int to, T value) {
44
        int x = find(from), y = find(to);
45
        if (x == y) { // from 和 to 在同一个集合，不做合并
46
            // to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
47
            return dis[from] - dis[to] == value;
48
        }
49
        //    x --------- y
50
        //   /           /
51
        // from ------- to
52
        // 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
53
        // 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
54
        // 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
55
        dis[x] = value + dis[to] - dis[from]; // 计算 x 到其代表元 y 的距离
56
        fa[x] = y;
57
        return true;
58
    }
59
};

哈希#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ull = unsigned long long;
4
using ll = long long;
5

6
namespace hash_util {
7
inline void hash_combine(ull& seed, ull value) {
8
    seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
9
}
10

11
template <class T>
12
inline void hash_combine(ull& seed, const T& value) {
13
    hash_combine(seed, hash<T>{}(value));
14
}

pair哈希#

1
struct pair_hash {
2
    template <class T1, class T2>
3
    ull operator()(const pair<T1, T2>& p) const {
4
        ull seed = 0;
5
        hash_combine(seed, p.first);
6
        hash_combine(seed, p.second);
7
        return seed;
8
    }
9
};

tuple哈希#

1
struct tuple_hash {
2
    template <class... Ts>
3
    ull operator()(const tuple<Ts...>& t) const {
4
        ull seed = 0;
5
        apply([&seed](const auto&... args) {
6
            (hash_combine(seed, args), ...);
7
        }, t);
8
        return seed;
9
    }
10
};
11
}

树#

LCA#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using pii = pair<int, int>;
6

7
class lca {
8
    vector<int> depth;
9
    vector<ll> dis;
10
    vector<vector<int>> pa;// 本质为步长为2^i的父亲数组
11

12
public:
13
    lca(const vector<vector<int>>& edges) {
14
        int n = edges.size() + 1;
15
        int m = bit_width((unsigned) n);
16
        vector<vector<pii>> g(n);
17
        depth.resize(n);
18
        dis.resize(n);
19
        pa.resize(n, vector<int>(m, -1));
20

21
        for (auto& e : edges) {
22
            int x = e[0], y = e[1], w = e[2];
23
            g[x].emplace_back(y, w);
24
            g[y].emplace_back(x, w);
25
        }
26

27
        auto dfs = [&](auto&& dfs, int x, int fa) -> void {
28
            pa[x][0] = fa;
29
            for (auto& [y, w] : g[x]) {
30
                if (y != fa) {
31
                    depth[y] = depth[x] + 1;
32
                    dis[y] = dis[x] + w;
33
                    pa[y][0] = x;
34
                    dfs(dfs, y, x);
35
                }
36
            }
37
        };
38
        dfs(dfs, 0, -1);
39

40
        for (int i = 0; i < m - 1; ++i) {
41
            for (int x = 0; x < n; ++x) {
42
                int p = pa[x][i];
43
                if (p != -1) {
44
                    pa[x][i + 1] = pa[p][i];
45
                }
46
            }
47
        }
48
    }
49

50
    int get_kth_anc(int node, int k) {
51
        for (; k > 0 && node >= 0; k &= k - 1) {
52
            node = pa[node][countr_zero((unsigned) k)];
53
        }
54
        return node;
55
    }
56

57
    int get_lca(int x, int y) {
58
        if (depth[x] > depth[y]) swap(x, y);
59

60
        y = get_kth_anc(y, depth[y] - depth[x]);
61
        if (y == x) return x;
62

63
        for (int i = pa.size() - 1; i >= 0; --i) {
64
            int px = pa[x][i], py = pa[y][i];
65
            if (px != py) {
66
                x = px;
67
                y = py;
68
            }
69
        }
70
        return pa[x][0];
71
    }
72
};

串#

KMP#

1
vector<int> prefix_function(const string& s) {
2
    int n = s.size();
3
    vector<int> pi(n);
4
    for (int i = 1; i < n; ++i) {
5
        int j = pi[i - 1];
6
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
7
        if (s[i] == s[j]) j++;
8
        pi[i] = j;
9
    }
10
    return pi;
11
}
12

13
vector<int> kmp_match(const string& text, const string& pattern) {
14
    string s = pattern + "#" + text;
15
    vector<int> pi = prefix_function(s);
16
    vector<int> res;
17

18
    int m = pattern.size();
19
    for (int i = m + 1; i < s.size(); ++i) {
20
        if (pi[i] == m)
21
            res.push_back(i - 2 * m);
22
    }
23
    return res;
24
}

Z函数#

1
vector<int> z_function(const string& s) {
2
    int n = s.size();
3
    vector<int> z(n);
4
    int l = 0, r = 0;
5

6
    for (int i = 1; i < n; ++i) {
7
        if (i <= r)
8
            z[i] = min(r - i + 1, z[i - l]);
9

10
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
11
            z[i]++;
12

13
        if (i + z[i] - 1 > r) {
14
            l = i;
15
            r = i + z[i] - 1;
16
        }
17
    }
18

19
    return z;
20
}
21

22
vector<int> z_match(const string& text, const string& pattern) {
23
    string s = pattern + "#" + text;
24
    vector<int> z = z_function(s);
25
    vector<int> res;
26

27
    int m = pattern.size();
28
    for (int i = m + 1; i < s.size(); ++i)
29
        if (z[i] == m)
30
            res.push_back(i - m - 1);
31

32
    return res;
33
}

AC自动机#

1
struct AC {
2
    static const int N = 1000005;
3
    int tr[N][26], fail[N], cnt[N];
4
    int idx = 0;
5

6
    void insert(const string& s) {
7
        int p = 0;
8
        for (char c : s) {
9
            int u = c - 'a';
10
            if (!tr[p][u]) tr[p][u] = ++idx;
11
            p = tr[p][u];
12
        }
13
        cnt[p]++;
14
    }
15

16
    void build() {
17
        queue<int> q;
18
        for (int i = 0; i < 26; ++i)
19
            if (tr[0][i]) q.push(tr[0][i]);
20

21
        while (!q.empty()) {
22
            int u = q.front(); q.pop();
23
            for (int i = 0; i < 26; ++i) {
24
                int v = tr[u][i];
25
                if (v) {
26
                    fail[v] = tr[fail[u]][i];
27
                    q.push(v);
28
                } else {
29
                    tr[u][i] = tr[fail[u]][i];
30
                }
31
            }
32
        }
33
    }
34

35
    int query(const string& text) {
36
        int p = 0, res = 0;
37
        for (char c : text) {
38
            int u = c - 'a';
39
            p = tr[p][u];
40

41
            for (int j = p; j && cnt[j] != -1; j = fail[j]) {
42
                res += cnt[j];
43
                cnt[j] = -1; // 防止重复计数
44
            }
45
        }
46
        return res;
47
    }
48
};

SAM#

1
struct SAM {
2
    static const int N = 200005;
3

4
    struct State {
5
        int next[26];
6
        int link, len;
7
    } st[N * 2];
8

9
    int last, sz;
10

11
    void init() {
12
        st[0].len = 0;
13
        st[0].link = -1;
14
        sz = 1;
15
        last = 0;
16
    }
17

18
    void extend(char ch) {
19
        int c = ch - 'a';
20
        int cur = sz++;
21
        st[cur].len = st[last].len + 1;
22

23
        int p = last;
24
        while (p != -1 && !st[p].next[c]) {
25
            st[p].next[c] = cur;
26
            p = st[p].link;
27
        }
28

29
        if (p == -1) {
30
            st[cur].link = 0;
31
        } else {
32
            int q = st[p].next[c];
33
            if (st[p].len + 1 == st[q].len) {
34
                st[cur].link = q;
35
            } else {
36
                int clone = sz++;
37
                st[clone] = st[q];
38
                st[clone].len = st[p].len + 1;
39

40
                while (p != -1 && st[p].next[c] == q) {
41
                    st[p].next[c] = clone;
42
                    p = st[p].link;
43
                }
44

45
                st[q].link = st[cur].link = clone;
46
            }
47
        }
48

49
        last = cur;
50
    }
51

52
    // 不同子串数量
53
    long long count_distinct() {
54
        long long res = 0;
55
        for (int i = 1; i < sz; ++i)
56
            res += st[i].len - st[st[i].link].len;
57
        return res;
58
    }
59
};

音乐

音乐

0-板子合集

Tricks#

取整#

通用#

离散加小步长#

向下取整和向上取整#

中点#

杂项#

区间合并#

离散化#

哈希#

二分#

排序#

查找#

抽象代数#

⊕\oplus⊕#

& 和 |和max和min#

&

|#

max#

min#

高精度#

高 + 高#

高 - 高#

高 * 低#

高 / 低#

高 * 高#

高 / 高#

多项式#

基础约定#

加法#

减法#

朴素乘法#

NTT乘除法#

快速幂#

核心#

NTT乘法#

NTT带余除法#

乘法逆元#

导数#

积分#

多项式ln#

多项式exp#

多项式快速幂#

线性基#

普通#

可求第k小#

高斯消元#

浮点数#

模2高斯消元#

位运算#

格雷码#

正变换#

逆变换#

常用函数#

bit_width(x) = 1 + floor(log2(x))#

countr_zero(x) = bit_width(lowbit(x)) - 1#

组合数学#

组合#

排列#

负数组合#

Lucas定理#

矩阵快速幂#

数论#

中国剩余定理(CRT)#

扩展CRT#

快速乘#

扩展欧几里得#

质数#

筛法#

约数#

质因数分解#

约数计算#

欧拉函数#

性质#

图论#

基础约定#

最短路#

$\oplus$ #