拓扑排序
拓扑排序的定义 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列…
Category: 笔记
Acwing – 1497. 树的遍历
题目链接 题目链接 solution 由于给出的是后序遍历与中序遍历，后续遍历的遍历顺序是左右根，中序遍历的顺序是根左右，所以我们先用后序遍历确定根节点，然后再在中序遍历里面找到该节点，然后该节点左边就是左子树，右边就是右子树，左子树的数量就是k - bl +…
并查集
(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n …
高精度加法
vector<int> add(vector<int> A, vector<int> B) { // A: 4 3 2 1 // B: 6 5 vector<int> C(max(A.size(), B.size…
高精度乘法
vector<int> mul(vector<int> A, vector<int> B) { // A: 4 3 2 1 // B: 6 5 vector<int> C(A.size() + B.size() …
树状数组
树状数组笔记 树状数组功能 快速求前缀和O(long) 修改某一个数O(logn) 原理 基于二进制，$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$ $i_k >= i_{k-1} >= ....i_1， …
lowbit-计算整数在二进制最低位的位置
int lowbit(int x) { return x & (-x); } //返回最低位1的的位置的2^k，例如lowbit(8) = 2^3 == 8, lowbit(16) = 2 ^ 4 == 16
C++ biset用法
C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种，如下 bitset<4> bitset1; //无参构造，…
求余规则
模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b …
分数取模——费马小定理
费马小定理:对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)于是可以拆成：b*b^(M-2)=1(mod M)a / b = a * (b ^ (M - 2)) (mod M)