算法板子[updating]

板子

目录

  • 输入/输出

  • STL、库函数、编译器相关

    • 常用宏定义、类型最大值
    • 位运算
    • bitset
    • 双向链表 List
    • 优先队列
    • 字符串相关
    • unique 的使用

  • 数据结构

    • 单调栈 / 单调队列
    • 并查集
    • 树状数组（权值树状数组）
    • ST表
    • 线段树、扫描线
    • 珂朵莉树

  • 动态规划

    • LIS
    • 背包 DP
    • 子集和/枚举

  • 图论

    • 存储
    • DFS / BFS
    • 最小生成树
    • 最短路
    • 树的问题 (直径、LCA、树剖、启发式合并、虚树)
    • 拓扑排序
    • 判断二分图

  • 字符串

    • KMP
    • 字典树 Trie / AC自动机
    • 字符串哈希
    • Z 函数

  • 数学

    • 高精度

    • 快速幂

    • 数论

      • 模数放大技巧
      • 斐波那契数
      • 分解质因数 & 线性筛
      • 欧拉函数、扩展欧拉定理
      • 模逆元
      • 中国剩余定理 & 裴蜀定理
      • 组合数、卢卡斯
      • 莫比乌斯反演

    • 博弈论 (Nim 游戏)

    • 组合数学

      • 康托展开、排列组合
      • 抽屉原理、错位排列
      • 卡特兰数、第二类斯特林数

    • 线性代数

      • 矩阵快速幂

输入/输出

__int128版

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
#define __int128 i128
inline i128 read() {
    i128 x = 0;
    bool f = false; 
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-') f = true;
        ch = getchar();
    }
    
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    
    return f ? -x : x;
}

void print(i128 x) {
    if (x == 0) { 
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    
    char buf[40];  //注意位数
    int len = 0;
    while (x > 0) {
        buf[len++] = x % 10 + '0'; 
        x /= 10;
    }
    
    for (int i = len - 1; i >= 0; i--) {
        putchar(buf[i]);
    }
}

STL、库函数、编译器相关

dev-c++使用c++11编译器：-std=c++11

常用宏定义

1
2
3
4
#define ALL(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define PII pair<int, int>

类型最大值

1
2
3
#include<climits>
int: INT_MAX
long long: LLONG_MAX

位运算

操作名称 代码示例 作用
判断奇偶数 x & 1 为 1 是奇数，为 0 是偶数（比 % 2 快）
判断同号 (x ^ y) >= 0 同号为 1，异号为 0
交换两数 a^=b; b^=a; a^=b; 不用中间变量交换两个整数

用整数表示集合时（1 表示选，0 表示不选）：

  • 取出第 \(i\) 位的值：(x >> i) & 1
  • 将第 \(i\) 位设为 1：x |= (1 << i)
  • 将第 \(i\) 位设为 0：x &= ~(1 << i)
  • 将第 \(i\) 位取反：x ^= (1 << i)
1
2
3
4
5
6
7
8
9
10
// 1. 提取最低位的 1 
int lowbit(int x) {
    return x & -x;
}

// 2. 消去最低位的 1 (常用于统计 1 的个数，或判断 2 的幂)
x = x & (x - 1); 

// 判断 x 是否是 2 的幂
bool is_power_of_two = (x > 0) && ((x & (x - 1)) == 0);

统计二进制中 1 的个数：__builtin_popcount(x)

返回二进制末尾连续 0 的个数：__builtin_ctz(x)

返回二进制前导连续 0 的个数：__builtin_clz(x)

返回奇偶校验位 (1 的个数是奇数返回1，偶数返回0)：__builtin_parity(x)

bitset

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
#include <iostream>
#include <bitset>
using namespace std;

int main() {
    // bitset 的大小尖括号里，必须填**编译期常量**！不能填变量 n！
    const int N = 1005;
    bitset<N> b; // 默认全部初始化为 0

    // 1. 基础读写 (跟数组一样)
    b[0] = 1;
    b[3] = 1;

    // 2. 极其好用的内置函数
    b.set();      // 把所有位都变成 1
    b.reset();    // 把所有位都清零 (变成 0)
    b.flip();     // 所有位取反 (0变1，1变0)
    b.flip(2);    // 把第 2 位取反

    cout << "一共有多少个 1: " << b.count() << '\n'; // 极其高效的统计 1 的个数
    cout << "有没有 1: " << b.any() << '\n';         // 只要有任何一位是 1，就返回 true
    cout << "是不是全 0: " << b.none() << '\n';      // 全部是 0 返回 true

    return 0;
}

双向链表List

  • front()：返回第一个元素的引用。

  • back()：返回最后一个元素的引用。

  • 支持 begin() 等迭代器

  • push_front(val) / pop_front()：在链表头部插入 / 删除元素。

  • push_back(val) / pop_back()：在链表尾部插入 / 删除元素。

  • insert(pos, val)：在迭代器 pos 指向的元素之前插入新元素，并返回新元素的迭代器。

  • erase(pos) / erase(first, last)：删除迭代器 pos 处的元素，或删除 [first, last) 区间的元素。返回指向下一个元素的迭代器。

  • sort()：对链表进行排序。默认升序（底层通常是归并排序，复杂度 \(O(N \log N)\)）。可以传入自定义比较函数。

  • reverse()：将整个链表中的元素反转。

  • remove(val)：删除链表中所有值等于 val 的元素。

  • merge(other_list)：将 other_list 合并到当前链表中。要求两个链表都必须已经排好序。合并后，other_list 会变为空。

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(int a,int b){
    return a>b; //定义小顶堆
    //注意，pq中true表示为其优先级更低
}

priority_queue<int,vector<int>,decltype(&cmp) > pq(cmp); //第三位需要函数指针类型

//或
auto cmp=[](int a,int b)->bool{
    return a>b; //定义小顶堆
    //注意，pq中true表示为其优先级更低
};

priority_queue<int,vector<int>,decltype(cmp) > pq(cmp);

字符串相关

1
2
3
4
5
6
7
8
9
s.find("love") //找到返回size_t，否则返回string::npos
s.substr(i,len) //返回截取片段
s.push_back(),s.pop_back();
s.insert(i,"str")
s.erase(i,len)
s.replace(i,len,"str")
to_string(123),stoi("123")
isalnum() //是否是字母或数字，取反可判断标点和空格
regex_replace(s,regex("s"),"str") //正则替换

unique 的使用

1
2
3
4
5
6
7
vector<int> vals;
sort(ALL(vals));
vals.erase(unique(ALL(vals)), vals.end());
//查找某个值离散化后的排名（从 1 开始记）
int get_id(int x) {
    return lower_bound(ALL(vals), x) - vals.begin() + 1;
}
  • unique_copy（不去改变原数据，直接生成去重后的新数据）

数据结构

单调栈

1
2
3
4
insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[N]; int q[N];
int n,k; //k为滑动窗口大小

void getmin(){ //得到窗口(队列)最小值
    int head = 0, tail = -1;
    for(int i=1;i<k;i++){ //预处理第一个窗口前
        while(head<=tail && a[q[tail]]>=a[i]) tail--; //维护队列递增性，求最大值反着来
        q[++tail] = i; //队尾存插入元素下标
    }
    for(int i=k;i<=n;i++){
        while(head<=tail && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;
        while(q[head]<=i-k) head++; //队列大小大于窗口，出队
        cout << a[q[head]] << ' '; //输出当前窗口最小值
    }
    cout << '\n';
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct DSU {
  std::vector<size_t> pa, size;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    pa[y] = x;
    size[x] += size[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
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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010; // 操作的总次数上限
int c[N];
int n; // 离散化后不同元素的总个数（也是树状数组的边界）

int lowbit(int x) {
    return x & -x;
}

// 树状数组：单点修改
void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

// 树状数组：求前缀和
int getsum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

// 树状数组：求第 k 小 (倍增法 O(log N))
int kth(int k) {
    int pos = 0;
    int sum = 0;
    for (int i = 20; i >= 0; i--) { // 2^20 > 10^6，根据 N 调整
        int next_pos = pos + (1 << i);
        if (next_pos <= n && sum + c[next_pos] < k) {
            pos = next_pos;
            sum += c[next_pos];
        }
    }
    return pos + 1;
}


// 离散化
vector<int> vals; // 存储所有的原始数值，用于离散化

// 通过二分查找，将真实值映射为 1-based 的离散化排名
int get_id(int x) {
    // lower_bound 找到第一个大于等于 x 的迭代器
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
}

int main() {

    // 假设我们有以下操作需要处理：
    vector<int> raw_data = {1000000000, -500, 233, -500, 99999};

    for (int x : raw_data) {
        vals.push_back(x);
    }

    // 排序并去重 (O(N log N))
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    // 此时，n 就是不同数值的种类数，也是树状数组的最大下标
    n = vals.size();

    // 使用映射后的 ID 进行树状数组操作
    
    // 将数据依次插入权值树状数组
    for (int x : raw_data) {
        int id = get_id(x); // 将真实值转为 1 到 n 的排名
        add(id, 1);         // 在对应排名上 +1
    }

    // 查询有多少个数小于等于 233
    int query_val = 233;
    int id = get_id(query_val);
    cout << "小于等于 " << query_val << " 的数字有: " << getsum(id) << " 个\n";

    // 全局第 3 小的真实数字
    int k = 3;
    int kth_id = kth(k); // 拿到的是离散化后的排名
    // 怎么转回真实值？查字典！vals 数组的下标是 0-based，所以要减 1
    int real_val = vals[kth_id - 1]; 
    cout << "第 " << k << " 小的数字是: " << real_val << "\n";

    return 0;
}

ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int st[N][(int)log2(N)+2];

int query(int l,int r){
    int k = log2(r-l+1); 
    return max(st[l][k],st[r-(1<<k)+1][k]);
}

// 预处理
for(int i=1;i<=n;i++){
    cin >> st[i][0];
}
int limit = log2(n);
for(int j=1;j<=limit;j++)
    for(int i=0;i+(1<<j)-1<=n;i++)
        st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);

线段树

动态开点可参见扫描线部分

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
// 线段树区间加法和区间求和
#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 1000000;
ll a[N];
ll tr[4*N];
vector<ll> lazy(4*N,0);

//对区间[s,t]建树，p为当前节点编号
void build(ll s,ll t,ll p){ //建树
    if(s == t){
        tr[p] = a[s];
        return;
    }
    else{
        ll m = s + ((t-s)>>1);
        build(s,m,p*2);
        build(m+1,t,p*2+1);
        tr[p] = tr[p*2] + tr[p*2+1];
    }
}

//更新区间[l,r]，[s,t]为当前节点区间，p为当前节点编号
void update(ll l, ll r, ll c, ll s,ll t,ll p){
    if(l <= s && t <= r){
        tr[p] += c*(t-s+1);
        lazy[p] += c;
        return;
    }else{
        ll m = s+((t-s)>>1);
        if(lazy[p]){
            tr[p*2] += lazy[p]*((m-s+1));
            tr[p*2+1] += lazy[p]*((t-m));
            lazy[p*2] += lazy[p];
            lazy[p*2+1] += lazy[p];
            lazy[p] = 0;
        }  
        if(l <= m) update(l,r,c,s,m,p*2);
        if(r > m) update(l,r,c,m+1,t,p*2+1);
        tr[p] = tr[p*2] + tr[p*2+1];
    }
}

//区间求和
ll getsum(ll l,ll r,ll s,ll t,ll p){
    if(l <= s && t <= r){
        return tr[p];
    }
    ll m = s + ((t-s)>>1);
    ll sum = 0;
    if(lazy[p]){
        tr[p*2] += lazy[p]*((m-s+1));
        tr[p*2+1] += lazy[p]*((t-m));
        lazy[p*2] += lazy[p];
        lazy[p*2+1] += lazy[p];
        lazy[p] = 0;
    }
    if(l <= m) sum = getsum(l,r,s,m,p*2);
    if(r > m) sum += getsum(l,r,m+1,t,p*2+1);
    return sum;
}

扫描线

矩形面积并

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

// 假设最多有 10^5 个矩形，那么有 2*10^5 条竖边，离散化后最多有 2*10^5 个不同的 y 坐标
// 线段树空间一般开 4 到 8 倍
const int N = 200010; 

// 1. 定义扫描线
struct Line {
    LL x;      // 扫描线的 x 坐标
    LL y1, y2; // 扫描线的上下端点
    int v;     // 权值：左边入边为 1，右边出边为 -1
    
    // 必须按照 x 坐标从小到大排序，保证扫描线从左向右扫
    bool operator<(const Line& other) const {
        return x < other.x;
    }
} lines[N];

vector<LL> Y; // 存储所有 y 坐标用于离散化

// 2. 线段树全局数组（不开结构体，常数更小）
int cnt[N << 3]; // 记录区间被完全覆盖的次数
LL len[N << 3];  // 记录区间内有效覆盖的物理长度

// 宏定义左右儿子，写起来更清爽
#define ls (u << 1)
#define rs (u << 1 | 1)

// 3. 核心：根据覆盖次数，更新当前区间的有效物理长度
void pushup(int u, int l, int r) {
    // 只要 cnt > 0，说明这个区间被完整覆盖了
    if (cnt[u] > 0) {
        // 【关键坑点 1】叶子节点 l 代表的物理线段是 [ Y[l], Y[l+1] ]
        // 所以整个区间 [l, r] 代表的物理总长度是 Y[r+1] - Y[l]
        len[u] = Y[r + 1] - Y[l];
    } 
    // 如果没有被完整覆盖，且到了叶子节点（一条基本线段），长度为 0
    else if (l == r) {
        len[u] = 0;
    } 
    // 如果没有被完整覆盖，且不是叶子节点，长度由左右儿子拼凑而成
    else {
        len[u] = len[ls] + len[rs];
    }
}

// 4. 区间更新
// u: 当前节点, l, r: 当前节点管辖的离散化下标范围
// L, R: 目标修改的离散化下标范围, v: 修改值(1 或 -1)
void update(int u, int l, int r, int L, int R, int v) {
    // 如果当前区间被完全包含
    if (L <= l && r <= R) {
        cnt[u] += v;
        pushup(u, l, r);
        return;
    }
    int mid = l + r >> 1;
    if (L <= mid) update(ls, l, mid, L, R, v);
    if (R > mid)  update(rs, mid + 1, r, L, R, v);
    
    // 子节点更新完毕，务必重新 pushup 维护自身长度
    pushup(u, l, r);
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 0; i < n; i++) {
        LL x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 左边：权值为 1
        lines[i * 2] = {x1, y1, y2, 1};
        // 右边：权值为 -1
        lines[i * 2 + 1] = {x2, y1, y2, -1};
        
        Y.push_back(y1);
        Y.push_back(y2);
    }
    
    // 5. 排序与离散化
    // 共有 2n 条竖边
    sort(lines, lines + 2 * n);
    
    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    
    LL ans = 0;
    // 去重后如果有 m 个不同的 Y 坐标，它们构成了 m - 1 条基本线段
    // 所以线段树的下标范围是 0 到 Y.size() - 2
    int max_idx = Y.size() - 2; 
    
    // 6. 开始扫描线
    for (int i = 0; i < 2 * n; i++) {
        // 先结算上一段的面积：底 * 高
        if (i > 0) {
            LL dx = lines[i].x - lines[i - 1].x;
            LL current_len = len[1]; // 根节点始终维护整个 y 轴的有效覆盖长度
            ans += dx * current_len;
        }
        
        // 查找当前竖边的下/上端点在离散化数组中的下标
        int L = lower_bound(Y.begin(), Y.end(), lines[i].y1) - Y.begin();
        int R = lower_bound(Y.begin(), Y.end(), lines[i].y2) - Y.begin();
        
        // 【关键坑点 2】
        // 传入线段树的右边界必须是 R - 1！
        // 因为点 R 对应的基本线段是 [ Y[R], Y[R+1] ]，这已经超出了当前矩形的上边界
        if (L <= R - 1) {
            update(1, 0, max_idx, L, R - 1, lines[i].v);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

珂朵莉树

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
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+10;
#define int int
int n,m,seed,vmax;
int a[N];
struct node{
    int l,r;
    mutable int v;
    node(const int &il,const int &ir,const int &iv):l(il),r(ir),v(iv){}; 
    bool operator <(const node &o) const {return l<o.l;}
};

set<node> odt;

auto split(int x){
    //找到区间左端点大于等于x的第一个区间
    auto it = odt.lower_bound(node(x,0,0)); 
    //判断是否刚好不用分割
    if(it!=odt.end()&&it->l == x) return it;
    --it; //得到左端点小于x的区间
    int l=it->l,r=it->r,v=it->v;
    odt.erase(it); //删去本区间
    //得到两区间
    odt.insert(node(l,x-1,v));
    //返回分割后的左端点为x的区间
    return odt.insert(node(x,r,v)).first; 
}

//区间修改
void assign(int l,int r,int v){
    auto itr=split(r+1);
    auto itl=split(l);
    odt.erase(itl,itr); //删去区间内的所有小区间
    odt.insert(node(l,r,v)); //插入大区间
}

//区间加法
void add(int l,int r,int v){ 
    auto itr=split(r+1);
    auto itl=split(l);
    for(;itl!=itr;itl++){
        itl->v += v;
    }
}

//区间第x小查询
void perform1(int l,int r,int x){
    auto itr = split(r+1);
    auto itl = split(l);
    vector<pair<int,int>> v;
    for(;itl!=itr;itl++){
        pair<int,int> pr;
        pr.first = itl->v; //区间每个元素的值
        pr.second = itl->r-itl->l+1; //区间长度
        v.push_back(pr);
    }
    sort(v.begin(),v.end()); //按值排序
    for(int i=0;i<v.size();i++){
        if(x > v[i].second){
            x -= v[i].second;
        }else{ //所找元素在区间内
            cout << v[i].first << endl;
            break;
        }
    }
}

int qpow(int v,int x,int y){
    int res = 1;
    while(x>0){
        if(x&1){
            res = res * v % y; 
        }
        v = (v%y)*(v%y) % y;
        x >>= 1;
    }
    return res;
}

//区间求a^x和，单纯求和换掉qpow
void perform2(int l,int r,int x,int y){
    auto itr = split(r+1);
    auto itl = split(l);
    int res = 0;
    for(;itl!=itr;itl++){
        int l=itl->l,r=itl->r,v=itl->v;
        res += (qpow(v,x,y)*(r-l+1))%y;
        res %= y;
    }
    cout << res << endl;
}

/* 值的种类少的情况下，接在assign 操作后
void merge(set<node>::iterator a){ //查看是否能合并周围结点，如果能就合并
    auto l = a,r = next(a);
    if(prev(a)->v == a->v){
        l = prev(a);
    }
    if(next(a)->v == a->v){
        r = next(r);
    }
    if(next(l) != r){
        int il = l->l,ir = prev(r)->r,iv = l->v;
        odt.erase(l,r);
        odt.insert(node(il,ir,iv));
    }
    
}
*/

int rnd(){ //这个是求原题的随机数组，不用管
    int ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}


signed main(){
    cin >> n >> m >> seed >> vmax;
    odt.insert(node(1,n+1,0)); //注意初始化
    for(int i=1;i<=n;i++){
        a[i] = (rnd() % vmax) + 1;
        assign(i,i,a[i]);
    }

    for(int i=1;i<=m;i++){
        int op = (rnd() % 4) + 1;
        int l = (rnd() % n) + 1;
        int r = (rnd() % n) + 1;
        int x,y;
        if (l > r)
            swap(l, r);

        if (op == 3)
            x = (rnd() % (r - l + 1)) + 1;
        else
            x = (rnd() % vmax) + 1;

        if (op == 4)
            y = (rnd() % vmax) + 1;

        if(op==1) add(l,r,x);  //区间加法
        else if(op==2) assign(l,r,x);   //区间赋值
        else if(op==3) perform1(l,r,x); //输出[l,r]中第x个最小值
        else if(op==4) perform2(l,r,x,y); //\sum a_i^x mod y
    }
}

动态规划

LIS

1
2
3
4
5
6
//d为辅助数组，需要存储要单独记录
for(int i=0;i<n;i++){
    int pos = lower_bound(d+1,d+len+1,a[i])-d;
    d[pos] = a[i];
    len = max(p,len);
}

背包DP

多重背包二进制处理

1
2
3
4
5
6
7
8
9
10
11
12
13
index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

二维费用背包

1
2
3
4
for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

分组背包

1
2
3
4
5
6
for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

树上背包

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
const int N = 310;
int s[N];
int dp[N][N];
vector<vector<int>> g(N);
int n,m;

int dfs(int u){ //返回值为以u为根子树大小
    int p = 1;
    dp[u][1] = s[u]; //选了后肯定有s[u]学分
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i]; //u是v的直接先修课
        int tmp = dfs(v); 
        p += tmp; //加上子树大小
        for(int j=min(p,m+1);j>=1;j--){ //选课肯定不能超过容量M
            for(int k=1;k<j&&k<=tmp;k++){
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]); 
            }
        }
    }
    return p;
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int k;
        cin >> k >> s[i];
        g[k].push_back(i); //k为i的直接先修课
    }
    dfs(0); //让根是0，连接森林为树
    cout << dp[0][m+1];
}

子集和/枚举

子集和dp （快速 Zeta 变换）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n; // 维度数量（即二进制的位数，表示有 n 个物品）
std::vector<int> a, ps;  // 数组大小为 1 << n (即 2^n)。a 是初始权值数组，ps 用来存子集和

void sum_of_subsets() {
  ps = a; // 初始化：每个状态目前的子集和，就是它自身原本的值

  // 外层循环：按维度逐一处理（即按二进制的每一位 i 依次处理）
  for (int i = 0; i < n; ++i) { 
    
    // 内层循环：遍历所有的二进制状态 st (从 0 到 2^n - 1)
    for (int st = 0; st < (1 << n); ++st) { 
      
      // 判断当前状态 st 的第 i 位是否为 1 
      // (也就是判断当前集合是否包含了第 i 个物品)
      if ((st >> i) & 1) { 
        
        // 如果包含，就把对应的“不包含第 i 个物品”的子集值累加到自己身上
        // 核心位运算：st ^ (1 << i) 会把 st 的第 i 位从 1 翻转成 0，
        // 从而精确找到它缺了第 i 个物品时的那个子集状态。
        ps[st] += ps[st ^ (1 << i)];
      }
    }
  }
}

状压DP可能用到对子集的枚举

1
2
3
4
5
6
//另外的，子集枚举
for (int S = 0; S < (1 << n); S++) {       // 外层：遍历所有状态
    for (int sub = S; sub > 0; sub = (sub - 1) & S) { // 内层：遍历 S 的子集
        // 状态转移...
    }
}

图论

存储

邻接矩阵注意判断重边，取最小值或者最大值

链式前向星

vec型

1
2
3
4
5
6
7
vector<int> nxt,head,to;
//初始化 head.resize(n+1,-1)
void add(int u,int v){
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
}

数组型

1
2
3
4
5
6
7
8
const int N=1e5;
int nxt[N],head[N],to[N];
int cnt = -1;
void add(int u,int v){
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

最小生成树

kruskal

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
#include<bits/stdc++.h>

using namespace std;

int fa[N]; // 并查集
int n,m;  // 顶点数与边数
int cnt; //记录当前边数

struct edge{
    int u,v,w;
    bool operator<(edge b){
        return w<b.w; //方便对边权比较
    }
};

edge g[M];

void kruskal(){
    int tot = 0; //存已选了的边数
    int ans = 0; //总代价
    for(int i=1;i<=m;i++){
        int x = find(g[i].u),y = find(g[i].v); 
        if(x!=y){ //二者不在一棵树上
            tot++;
            ans += g[i].w;
            unite(x,y);
        }
        if(tot==n-1){
            cout << ans << '\n'; //输出总代价
            return;
        }
    }
    cout << "orz" << '\n'; //不存在
}


int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    iota(fa+1,fa+n+1,1); //让[1...n]=1...n
    sort(g+1,g+m+1);
    kruskal();
}

最短路

Floyd

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

Bellman–Ford 算法

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断．

SPFA

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
struct edge {
  int v, w;
};

vector<edge> e[MAXN];
int dis[MAXN], cnt[MAXN], vis[MAXN];
queue<int> q;

bool spfa(int n, int s) { //s是单源最短路径
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

Dijkstra 算法

用于求解 非负权图 上单源最短路径的算法。

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
struct edge {
  int v, w;
};

struct node {
  int dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

树的问题

树的直径

两次 \(dfs\) ，第二次为距离最远的边，答案为 \(len[r]\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int u,int fa){
    for(int p=head[u];~p;p=nxt[p]){
        int v = to[p];
        if(v!=fa){ //非父节点
            len[v] = len[u]+1;
            if(len[v]>len[r]){
                r = v;
            }
            dfs(v,u);
        }
    }
}
dfs(1,0);
len[r] = 0; //由于结点为父结点加1，只用置根节点为0即可
dfs(r,0);
cout << len[r];

最近公共祖先LCA

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
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
vector<int> adj[N];
int fa[N][21]; // fa[i][j] 表示节点 i 向上跳 2^j 步到达的祖先
int dep[N];    // 深度

// 1. 预处理：通过一次 DFS 计算深度和 2^0 的祖先（即父亲）
void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    // 关键：在这里直接预处理出当前节点的所有 2^k 倍祖先
    for (int i = 1; i <= 20; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; 
    }
    for (int v : adj[u]) {
        if (v != f) dfs(v, u);
    }
}


int get_lca(int u, int v) {
    // 保证 u 是更深的那一个
    if (dep[u] < dep[v]) swap(u, v);
    
    // 先跳到同一高度
    for (int i = 20; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    
    if (u == v) return u;

    // 一起向上跳，直到跳到 LCA 的下一层
    for (int i = 20; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0]; // 返回它们的父亲即为 LCA
}

树链剖分

  • \(son(x)\) 表示结点 \(x\) 的 重儿子。
  • \(top(x)\) 表示结点 \(x\) 所在 重链 的顶部结点（深度最小）。
  • \(dfn(x)\) 表示结点 \(x\) 的 DFS 序，也是其在线段树中的编号。
  • \(rnk(x)\) 表示 DFS 序所对应的结点编号，有 \(rnk(dfn(x)) = x\)。

我们进行两遍 DFS 预处理出这些值，其中第一次 DFS 求出 \(fa(x)\)，\(dep(x)\)，\(siz(x)\)，\(son(x)\)，第二次 DFS 求出 \(top(x)\)，\(dfn(x)\)，\(rnk(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
// 第一次 DFS：收集信息，找出每个节点的“重儿子”
void dfs1(int u, int f) {
  // 记录父节点、深度、初始化子树大小为 1（包含自己）
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  
  for (auto v : G[u]) {
    if (v == f) continue; 
    dfs1(v, u);           
    siz[u] += siz[v];     // 回溯时，累加子节点的体积
    
    // 如果当前子节点的体积比记录的重儿子大，就更新重儿子
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

// 第二次 DFS：连结重链，分配连续的 DFS 序（数组下标）
void dfs2(int u, int ftop) {
  // 记录所在重链的链头、分配唯一的 DFS 序(dfn)、记录序号对应的真实节点(rnk)
  top[u] = ftop, dfn[u] = ++idx, rnk[idx] = u;
  
  // 优先遍历重儿子！这样能保证同一条重链上的节点 dfn 序号是连续的
  if (son[u]) dfs2(son[u], ftop); 
  
  // 遍历其他轻儿子
  for (auto v : G[u]) {
    // 避开重儿子和父节点
    if (v != son[u] && v != fa[u]) {
      // 每一个轻儿子，都是一条全新重链的开始（链头是它自己 v）
      dfs2(v, v); 
    }
  }
}

树上启发式合并

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
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 2e5 + 5;

int n, m;

// g[u]: 存储与 u 相邻的结点
vector<int> g[N];

// sz: 子树大小
// big: 重儿子
// col: 结点颜色
// L[u]: 结点 u 的 DFS 序
// R[u]: 结点 u 子树中结点的 DFS 序的最大值
// Node[i]: DFS 序为 i 的结点
// totdfn: 节点计数器，也是当前遍历过节点的 DFS 序最大值
// ans: 存答案
// cnt[i]: 颜色为 i 的结点个数
// totColor: 目前出现过的颜色个数
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}

void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}

int getAns() { return totColor; }

void dfs0(int u, int p) {
  L[u] = ++totdfn;
  Node[totdfn] = u;
  sz[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
  R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
  // 计算轻儿子的答案
  for (int v : g[u])
    if (v != p && v != big[u]) {
      dfs1(v, u, false);
    }
  // 计算重儿子答案并保留计算过程中的数据（用于继承）
  if (big[u]) {
    dfs1(big[u], u, true);
  }
  for (int v : g[u])
    if (v != p && v != big[u]) {
      // 子树结点的 DFS 序构成一段连续区间，可以直接遍历
      for (int i = L[v]; i <= R[v]; i++) {
        add(Node[i]);
      }
    }
  add(u);
  ans[u] = getAns();
  if (!keep) {
    for (int i = L[u]; i <= R[u]; i++) {
      del(Node[i]);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  dfs0(1, 0);
  dfs1(1, 0, false);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int q;
    scanf("%d", &q);
    printf("%d\n", ans[q]);
  }
  return 0;
}

虚树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dfn[MAXN];
int h[MAXN], m, a[MAXN], len;  // 存储关键点

bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // 按照 dfs 序排序
}

void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // 把关键点按照 dfs 序排序
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // 插入 lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // 把所有虚树上的点按照 dfs 序排序
  len = unique(a + 1, a + len + 1) - a - 1;  // 去重
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // 连边，如有边权 就是 distance(lc,a[i+1])
  }
}

拓扑排序

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
const int N = 1e5 + 10;
vector<int> g;   // 邻接表存图
int din;         // 记录每个点的入度
vector<int> tp;     // 存储最终的拓扑序列
int n, m;           // n个点，m条边

// 拓扑排序核心函数
bool topsort() {
    queue<int> q;
    tp.clear(); // 多组数据时注意清空
    // 1. 将所有入度为 0 的点入队
    for (int i = 1; i <= n; i++) {
        if (din == 0) {
            q.push(i);
        }
    }
    // 2. BFS 剥洋葱
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        tp.push_back(u); // 放入拓扑序列

        // 遍历当前节点的所有出边
        for (int v : g) {
            // 将相连节点的入度减 1（相当于删掉这条边）
            if (--din == 0) { 
                q.push(v); // 入度减为 0 了，说明它的前置节点都访问过了，入队
            }
        }
    }
    // 3. 判环：如果加入拓扑序列的点数等于总点数，说明无环（是 DAG）
    // 返回 true 表示无环，返回 false 表示有环
    return tp.size() == 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
bool ans = true;
vector<int> visited;
void dfs(vector<vector<int>>& graph,int u){
    for(int i=0;i<graph[u].size();i++){
        int v = graph[u][i];
        if(!visited[v]){
            visited[v] = -1*visited[u];
            dfs(graph,v);
        }else{
            if(visited[u]+visited[v]!=0){
                ans = false;
                return;
            }
        }
    }

}
bool isBipartite(vector<vector<int>>& graph) {
    visited.assign(graph.size()+1,0);
    for(int i=0;i<graph.size();i++){
        if(!visited[i]){
            visited[i] = 1;
            dfs(graph,i);
        }
    }
    return ans;
}

字符串

KMP

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
#include<bits/stdc++.h>

using namespace std;

vector<int> prefix_function(string s){
    int n = s.length();
    vector<int> pi(n, 0);
    for(int i=1;i<n;i++){
        int j = pi[i-1];
        
        while(j > 0 && s[i] != s[j]){
            j = pi[j-1];
        }
        if(s[j] == s[i]){
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

vector<int> KMP(string s, string t){
    vector<int> pi = prefix_function(t);
    vector<int> ans;
    int j = 0;
    for(int i=0;i<s.length();i++){
        while(j > 0 && s[i] != t[j]){
            j = pi[j-1];
        }
        if(s[i] == t[j]){
            j++;
        }
        if(j == t.length()){
            ans.push_back(i - t.length() + 1); //如果只要第一个匹配答案，break即可
            j = pi[j-1];
        }
    }
    return ans;
}

//另一种实现方法，有一定局限性，但很好用
vector<int> KMP2(string s, string t){
    string cur = t + '#' + s;  //'#'是分隔符，是不能出现在s和t中的字符串
    int sz1 = s.length();
    int sz2 = t.length();
    vector<int> pi = prefix_function(cur);
    vector<int> ans;
    for(int i = sz2 + 1; i <= sz1+sz2; i++){
        if(pi[i] == sz2){
            ans.push_back(i - 2 * sz2);
        }
    }
    return ans;
}
int main(){
    string s,t;
    cin >> s >> t;
    vector<int> ans = KMP(s,t);
    for(auto i: ans) cout<<i+1<<endl;
    vector<int> ans2 = prefix_function(t);
    for(auto i: ans2) cout<<i<<' ';
}

字典树Tire/AC自动机

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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010; // 节点总数

struct AC_Automaton {
    // 【上半区：Trie 树部分】
    int nex[N][26];
    int cnt[N]; // 记录该节点结尾的单词数量
    int idx;    // 节点分配器

    void clear() {
        for (int i = 0; i <= idx; i++) {
            memset(nex[i], 0, sizeof(nex[i]));
            cnt[i] = 0;
            fail[i] = 0; 
        }
        idx = 0;
    }

    // 插入模式串
    void insert(const string& s) {
        int p = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!nex[p][c]) nex[p][c] = ++idx;
            p = nex[p][c];
        }
        cnt[p]++; 
    }
    
    // 精准查找某一个模式串是否完整存在
    bool find(const string& s) { 
        int p = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!nex[p][c]) {
                return false;
            }
            p = nex[p][c];
        }
        // AC自动机中用 cnt 数组代替了 exist
        // 如果查找前缀包含s的串是否存在，只要循环顺利结束就行(return true)
        return cnt[p] > 0; 
    }

    // 【下半区：AC 自动机专属部分】
    int fail[N]; // 失配指针

    // 构建 fail 指针 (BFS 遍历字典树)
    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (nex[0][i]) {
                q.push(nex[0][i]);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                int v = nex[u][i];
                if (v) {
                    fail[v] = nex[fail[u]][i];
                    q.push(v);
                } else {
                    nex[u][i] = nex[fail[u]][i];
                }
            }
        }
    }

    // 多模式串匹配主逻辑
    int query(const string& s) {
        int ans = 0;
        int p = 0;
        for (char ch : s) {
            p = nex[p][ch - 'a']; 
            int temp = p;
            while (temp && cnt[temp] != -1) {
                ans += cnt[temp];
                // 注意：这里会破坏原有的 cnt！
                // 如果题目要求多次调用 query，请去掉这行，或使用额外的 vis 数组打标记
                cnt[temp] = -1; 
                temp = fail[temp];
            }
        }
        return ans;
    }
};

字符串哈希

单哈希的板子

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 <iostream>
#include <string>

using namespace std;

typedef unsigned long long ULL;

const int N = 1000010; // 根据题目最大长度调整
const int P = 131;     // 经验进制数，也可以用 13331

ULL h[N]; // h[i] 存储前 i 个字符的哈希值
ULL p[N]; // p[i] 存储 P 的 i 次方

// 初始化预处理哈希数组和次幂数组
void init_hash(const string& s) {
    int n = s.length();
    p[0] = 1; 
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i - 1]; 
    }
}

// O(1) 查询子串哈希值
ULL query(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

Z函数

把模式串 \(T\) 放在主串 \(S\) 前面，中间加一个绝对不会出现的特殊字符（比如 #），构造出一个新字符串，在 “#” 之后，如果发现某个位置的 z[i] == T.length() ，说明在这个位置匹配成功

求字符串的周期 / Border：如果对于某个 \(i\)，满足 i + z[i] == n，并且 \(n\) 能够整除 \(i\)，那么长度为 \(i\) 的前缀就是整个字符串的循环节。

回文串预处理：在一些复杂的字符串题目中，结合正反跑两遍 Z 函数，可以快速判断各种前缀回文拼接问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

数学

高精度

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
vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0; // 进位
    for (int i = 0; i < A.size() || i < B.size() || t != 0; i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

// 比较 A 是否大于等于 B
bool cmp(vector<int>& A, vector<int>& B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

// 高精度减法 (前提：保证 A >= B)
vector<int> sub(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0; // 借位
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // 巧妙处理：如果 t < 0，加上 10 就是借位后的值；如果 t >= 0，加 10 模 10 依然不变
        if (t < 0) t = 1; // 产生了借位
        else t = 0;
    }
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> mul(vector<int>& A, vector<int>& B) {
    // 结果的最大长度为 A.size() + B.size()
    vector<int> C(A.size() + B.size(), 0);
    
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    // 统一处理进位
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// A 是高精度，b 是普通整数。r 用来返回余数
vector<int> div(vector<int>& A, int b, int& r) {
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--) { // 从最高位开始算
        r = r * 10 + A[i];
        C.push_back(r / b); // 存入商
        r %= b;
    }
    // 因为除法是从高位开始除的，C 里面的顺序是正序（高位在低索引），为了统一格式需要 reverse
    reverse(C.begin(), C.end());
    
    // 去除前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

快速幂

若无需模，请无视 \(p\)

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

数论

模数放大技巧

\[\frac{A}{B} \pmod m = \frac{A \pmod{B \times m}}{B}\]

其中，\(A\) 不能被 \(m\) 模过

斐波那契数

\[ F_n = \frac{\left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n}{\sqrt{5}} \]

  1. 卡西尼性质（Cassini’s identity）：\(F_{n-1}F_{n+1} - F_n^2 = (-1)^n\)
  2. 附加性质：\(F_{n+k} = F_k F_{n+1} + F_{k-1} F_n\)
  3. 取上一条性质中 \(k = n\)，我们得到：\(F_{2n} = F_n(F_{n+1} + F_{n-1})\)
  4. 由上一条性质可以归纳证明，\(\forall k \in \mathbb{N},\ F_n \mid F_{nk}\)
  5. 上述性质可逆，即 \(\forall F_a \mid F_b,\ a \mid b\)
  6. GCD 性质：\(\gcd(F_m, F_n) = F_{\gcd(m,n)}\)

矩阵快速幂的求法

\[\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}\]

通项递推公式（约定 \(F_0 = 0, F_1 = 1\)）： \[\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1 \\ F_0 \end{bmatrix}\]

分解质因数

朴素做法

1
2
3
4
5
6
7
8
9
10
11
vector<int> breakdown(int n){
    vector<int> res;
    for(int i=2;i*i<=n;i++){
        while(n%i==0){
            n/=i;
            res.push_back(i);
        }
    }
    if(n!=1) res.push_back(n); //经过操作后留下了一个素数
    return res;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<bool> isPrime;
vector<int> prime;
int n,q;
void seive(){
    isPrime.assign(n+1,true);
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            prime.push_back(i);
        }
        for(auto j:prime){
            if(i*j > n) break;
            isPrime[i*j] = false;
            if(i % j == 0) break;
        }
    }
}

欧拉函数

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
#include<iostream>
#include<vector>
using namespace std;

//求单个欧拉函数
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;
}

//利用筛法求解多个欧拉函数
vector<int> euler_phis(int n){
    vector<int> phi(n+1); //注意phi[0] 无意义
    vector<int> pri;
    vector<bool> isPrime(n+1,true);
    phi[1] = 1;
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            pri.push_back(i);
            phi[i] = i-1;
        }
        for(auto p:pri){
            if(p*i > n) break;
            isPrime[i*p] = false;
            if(i%p == 0){ //找到最小质因数
                phi[i*p] = phi[i]*p;
                break;
            }
            //否则i和p互质
            phi[i*p] = phi[i] * phi[p];
        }
    }
    return phi;
}


int main(){
    vector<int> t = euler_phis((int)1e8);
}

扩展欧拉定理

用于处理一般的 \(a\) 和 \(m\) 的情形 \[ a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, & \gcd(a,m)=1 \\ a^{b}, & \gcd(a,m)\neq1,\ b<\varphi(m) \\ a^{b \bmod \varphi(m)+\varphi(m)}, & \gcd(a,m)\neq1,\ b\ge\varphi(m) \end{cases} \pmod{m} \]

模逆元

当模数是素数 \(p\) 时

单个乘法逆元使用快速幂 \(qpow(a,p-2,p)\) 即可 （ \(a^{p-1} \equiv1 \pmod p\)）

模数普遍情况下：

采用扩展欧几里得的乘法逆元求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ex_gcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;  //a为(a,b)
    }else{
        int d = ex_gcd(b,a%b,y,x); //如果需要记录(a,b)
        y -= a/b*x;
        return d;
    }
}

int inverse(int a,int p){
    int x,y;
    ex_gcd(a,p,x,y);
    return (x%p+p)%p;
}

求 \(n\) 个逆元，模数为 \(p\) 的情况下

时间复杂度为 \(O(n+\log p)\)

这里需用快速幂，否则扩展欧几里得可能数值溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
signed main(){
    int n,p,k; //n为总数，p为模数
    cin >> n >> p >> k;
    pre[0] = 1; 
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pre[i] = (a[i]*pre[i-1])%p; //前缀积
    }
    ipre[n] = inverse(pre[n],p); //得到初始逆元的总积
    for(int i=n;i>=1;i--){
        ipre[i-1] = a[i]*ipre[i]%p; //遍历得到逆元的前缀积
    }
    for(int i=1;i<=n;i++){
        int m = ipre[i]*pre[i-1]%p; //得到逆元，可用数组存储
    }
}

中国剩余定理

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

const int N = 12;
int p[N], a[N];
int n; 

int crt() {
    int x = 0;
    int pp = 1; // 所有模数的乘积
    for (int i = 0; i < n; i++) pp *= p[i];
    
    for (int i = 0; i < n; i++) {
        int m = pp / p[i];
        int inv = inverse(m, p[i]); // 用ex_gcd求模逆元
        int c = (m * inv) % pp;
        x = (x + (a[i] % pp) * c) % pp;
    }
    return (x + pp) % pp;
}

裴蜀定理

设 \(a,b\) 是不全为零的整数。那么，对于任意整数 \(x,y\) 都用 \(\gcd(a,b)\mid ax+by\) 成立；而且，存在整数 \(x,y\) 使得 \(ax+by = \gcd(a,b)\) 成立。

推论：整数 \(a,b\) 互素，当且仅当存在整数 \(x,y\) ，使得 \(ax+by=1\) 成立。

可推广到多个整数的情形。

Sylvester 定理

对于互素的正整数 \(a_1,a_2\) ，不能够写作（存在等于） \(a_1x_1+a_2x_2\,(x_1,x_2\in N)\) 的最大整数是 \(C=a_1a_2-a_1-a_2\) 。而且，对于所有 \(k\in Z\) 整数 \(k\) 和 \(C-k\) 中有且只有一个可以写作该形式。

组合数计算预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int MOD = 1e9 + 7;
const int MAXN = 200005;
long long fac[MAXN], inv[MAXN];

// 预处理阶乘和逆元
void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2); //qpow为快速幂
    for (int i = MAXN - 2; i >= 1; i--) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

// O(1) 求组合数 C(n, m)
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

卢卡斯定理

对于素数 \(p\)，有: \[ \binom{n}{k} \equiv \binom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{k}{p} \right\rfloor} \binom{n \bmod p}{k \bmod p} \pmod p \] 其中，当 \(n < k\) 时，二项式系数 \(\binom{n}{k}\) 规定为 \(0\)。

1
2
3
4
int Lucas(int n, int k, int p) {
  if (k == 0) return 1;
  return (C(n % p, k % p, p) * Lucas(n / p, k / p, p)) % p;
}

莫比乌斯反演

莫比乌斯函数（Möbius 函数）定义为 \[ \mu(n) = \cases{ 1,&n=1 \\ 0,&n is divisible by a square > 1 \\ (-1)^k,&n is the product of k distinct primes. } \] 对正整数 \(n\) ，有： \[ \sum_{d\mid n} \mu(n)=[n=1] \] 利用 Dirichlet 卷积： \[ [i \perp j]=[\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d)=\sum_d[d\mid i][d\mid j]\mu(d) \]

设 \(f(n),g(n)\) 是两个数论函数。那么，有 \[ f(n)=\sum_{d\mid n}g(d) \Leftrightarrow g(n)=\sum_{d\mid n} \mu(\frac{n}{d})f(d) \] 它的倍数和形式： \[ f(n)=\sum_{n|d}g(d) \iff g(n)=\sum_{n|d}\mu\left(\frac{d}{n}\right)f(d) \] 适用于任何 Abel 群 中的运算都成立，例如，除了加法形式，还有如下乘法形式 \[ f(n)=\prod_{d\mid n} g(d) \Leftrightarrow g(n)=\prod_{d\mid n}f(d)^{\mu(\frac{n}{d})} \]

欧拉函数 \(\varphi(n)\) 满足关系式 \(n=\sum_{d|n}\varphi(d)\)，亦即 \(\text{id}=1*\varphi\)。对它进行反演，就得到 \(\varphi=\mu*\text{id}\)，亦即 \[ \varphi(n)=\sum_{d\mid n}d \mu(\frac{n}{d}) \]

博弈论

Nim 游戏

必败状态为石子堆的石头数异或和为 \(0\)

线性代数

矩阵快速幂

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
const int MOD = 1e9 + 7;
const int MAT_SIZE = 5; // 根据题目修改矩阵大小

struct Matrix {
    long long mat[MAT_SIZE][MAT_SIZE];
    Matrix() { memset(mat, 0, sizeof(mat)); }
    
    // 重载乘法
    Matrix operator*(const Matrix& b) const {
        Matrix res;
        for (int i = 0; i < MAT_SIZE; i++) {
            for (int k = 0; k < MAT_SIZE; k++) {
                if (!mat[i][k]) continue; // 常数优化
                for (int j = 0; j < MAT_SIZE; j++) {
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * b.mat[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

// 矩阵快速幂
Matrix mat_qpow(Matrix a, long long b) {
    Matrix res;
    for (int i = 0; i < MAT_SIZE; i++) res.mat[i][i] = 1; // 初始化为单位阵
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

组合数学

排列的排名/康托展开

要求一个排列在所有排列中的排名，我们需要用到 「康托展开」。

具体地，有 \[ rank = 1+L_\sigma(1)n!+L_\sigma(2)(n-1)!+\cdots+L_\sigma(n)0! \] 其中，\(L_\sigma(i)\) 表示排列中的第 \(i\) 个数，在 \(i+1\) 以后数的排名（按升序）减 \(1\) ，也就是后面未出现的数有多少个小于它。其值可用权值树状数组维护。

排列组合

组合数性质

  • \(\binom{n}{m} = \frac{\text{A}_n^m}{m!} = \frac{n!}{m!(n - m)!}\)

  • \(\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\)

插板法

问题一：现有 \(n\) 个 完全相同 的元素，要求将其分为 \(k\) 组，保证每组至少有一个元素，一共有多少种分法?

答案是 \(\binom{n-1}{k-1}\).

本质是求 \(x_1+x_2+\cdots+x_k=n\) 的正整数解的组数.

问题二：如果每组允许为空呢？

答案为\(\binom{n+k-1}{k-1}=\binom{n+k-1}{n}\)

本质是求 \(x_1+x_2+\cdots+x_k=n\) 的非负整数解的组数（即要求 \(x_i \ge 0\)）.

问题三：如果再扩展一步，要求对于第 \(i\) 组，至少要分到 \(a_i, \sum a_i \le n\) 个元素呢？

直接用插板法公式得到答案为

\[ \binom{n-\sum a_i+k-1}{n-\sum a_i} \]

不相邻的排列

\(1 \sim n\) 这 \(n\) 个自然数中选 \(k\) 个，这 \(k\) 个数中任何两个数都不相邻的组合有 \(\binom{n-k+1}{k}\) 种。

二项式定理 \[ (a + b)^n = \sum_{i=0}^{n} \binom{n}{i} a^{n-i} b^i \]

\[ (x_1 + x_2 + \cdots + x_t)^n = \sum_{\text{满足} n_1 + \cdots + n_t = n \text{的非负整数解}} \binom{n}{n_1, n_2, \dots, n_t} x_1^{n_1} x_2^{n_2} \cdots x_t^{n_t} \]

在代码实现或计算时，\(\binom{n}{n_1, n_2, \dots, n_t}\) 等价于 \(\frac{n!}{n_1! n_2! \dots n_t!}\)。

抽屉原理/鸽巢原理

推广

若将 \(n\) 个物体，划分为 \(k\) 组，那么至少存在一个分组，含有大于或等于 \(\lceil \frac{n}{k} \rceil\) 。

错位排列

递归计算有（\(D_0=D_1=0,D_2=1\)） \[ D_n = (n-1)(D_{n-1}+D_{n-2}) \] 或 \[ D_n = nD_{n-1}+(-1)^n \]

依据容斥原理，\(n\) 个元素的错位排列数为： \[ D_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!} \]

卡特兰数

通项公式：

\[ H_n = \frac{\binom{2n}{n}}{n+1} = \binom{2n}{n} - \binom{2n}{n-1}\]

递推公式：

\[ H_n = \sum_{i=0}^{n-1} H_i H_{n-i-1} \quad (n \ge 2, H_0=1, H_1=1)\]

\(n\) 个元素的进栈出栈顺序有多少种。

\(n\) 对括号的合法匹配序列有多少种。

\(n\) 个节点的二叉树有多少种不同的形态。

凸 \(n+2\) 边形划分为三角形的方法数。

在 \(n \times n\) 的网格中，从左下角走到右上角，且不穿过对角线的路径数。

第二类斯特林数

\(n\) 个不同的元素划分成 \(m\) 个相同且非空的集合的方案数，记为 \(S(n, m)\) 或 \(\begin{Bmatrix} n \\ m \end{Bmatrix}\)。

递推公式：

\[ S(n, m) = m \cdot S(n-1, m) + S(n-1, m-1)\]