Ender's Blog

Tarjan学习笔记 有向图强连通分量 定义 在有向图中，如果存在极大子图中从任意一点出发均能到达其他所有点，则称这个子图为有向图的强连通分量。 Tarjan求强连通分量 如果将这个有向图dfs成一棵树，当其加入一条边使得有向树中形成环时，这个环上的所有点都属于同一个强连通分量。当且仅当，加入的边从当前节点指向该节点的祖宗节点时，才有可能出现环；而且当存在当前节点指向该节点的祖宗节点时，若有加入一条起点终点深度相同的边，并且从终点可以走到连向祖宗节点的边的点，该祖宗节点也能走到加入的边的起点，图中也能形成新的环。 dfn[i] 用来记录第 i 个点的dfs序， low[i] 表示第 i 个点加边之后可以走到最靠上的点的dfs序。 dfs的起点为图中所有入度为零的点，枚举以当前节点 now 为起点的所有边的终点，如果该终点还没有被dfs过，则先dfs这个点，再用该终点的 low 值更新 low[now] 的值 ，如果该终点已经被dfs过了，该终点有可能是祖宗节点，则用该终点的dfs序更新 low[now] 的值。 如果某个点所连向的其他点没有dfs完成，或者该节点不知道处于哪个确定的强连 ...

2-SAT 问题学习笔记 问题 给定 nnn 个变量与 mmm 个等式，每个变量只能为 falsefalsefalse 或是 truetruetrue ，每个等式都至多有两个变量 xi,xjx_i , x_jxi​,xj​ ，并且等式右边给出这两个变量通过至多一个位运算符运算得到的结果，形如： x1 and x2=falsex2 or x3=truex3 xor x1=falsex2=truex_1\ and\ x_ 2 = false \\ x_2\ or\ x_3 = true \\ x_3\ xor\ x_1 = false \\ x_2 = true x1​ and x2​=falsex2​ or x3​=truex3​ xor x1​=falsex2​=true 判断是否有解 可以将这个问题转化为求强连通分量问题，首先这张图的点为每个 xix_ixi​ 的两种状态，如果根据第 kkk 个等式， 知道 xix_ixi​ 一定能够推出 xjx_jxj​ 的值，例如 x1andx2=falsex_1 and x_2 = falsex1​andx2​=false ，当 x1=tru ...

差分约束学习笔记 问题 给定 nnn 个变量和 mmm 个不等式，形为： xi−xj≤akx_i - x_j \leq a_k xi​−xj​≤ak​ 其中 aka_kak​ 为给定常数 求 xn−x1x_n - x _1xn​−x1​ 的最大值 求解 对于一个 xi−xj≤ax_i - x_j \leq axi​−xj​≤a ，可以将其转化为 xi≤xj+ax_i \leq x_j + axi​≤xj​+a 当有 xi−xj/leqa1x_i - x_j /leq a_1xi​−xj​/leqa1​ 、 xj−xk≤a2x_j - x_k \leq a_2xj​−xk​≤a2​ 时， 则可以转化为 xi≤xk+a1+a2x_i \leq x_k + a_1 + a_ 2xi​≤xk​+a1​+a2​ 令 yry_ryr​ 为从 111 号点出发到 rrr 号点的最短路径，从 jjj 向 iii 连一条长度为 aaa 的边，则有： yi≤yj+ay_i \leq y_j + a yi​≤yj​+a 再从 kkk 向 jjj 连一条长度为 bbb 的边，则有： yi≤yk+a+by_i ...

OI中的概率学习笔记 容斥原理 现有 {A1,A2,⋯ ,An}\{A_1, A_2, \cdots, A_n\}{A1​,A2​,⋯,An​} 总共 nnn 个集合，一直任意多个子集交集的大小，则所有集合并集的大小为： ∑B⊂{A1,A2,⋯ ,An}(−1)∣B∣+1⋅∣∩Ai∈BAi∣\sum_{B\subset\{A_1, A_2, \cdots, A_n\}} (-1)^{|B| + 1} \cdot |\cap_{A_i \in B}A_i| B⊂{A1​,A2​,⋯,An​}∑​(−1)∣B∣+1⋅∣∩Ai​∈B​Ai​∣ 随机试验 不能预先确知结果 实验之前可以预测所有可能结果或范围 可以在相同条件下重复实验 样本空间：随机试验所有可能结果组成的集合 连续性样本空间（不要求掌握）、离散样本空间、无穷样本空间 随机事件 样本空间的任意一个子集称之为事件 事件发生：在一次试验中，事件的一个样本点发生 必然事件：样本空间全集 不可能事件：空集 事件本身是样本空间的子集，所以事件的运算本质上是集合的运算。 概率 定义：为样本空间的 ...

BSGS代码 在OI数学笔记三中，我写过BSGS算法，这里是代码。 12345678910111213141516171819int z[1005];void bsgs(int a, int b, int p) { int sp = int(sqrt(p)); z[0] = 1; for(int i = 1; i < sp; i++) z[i] = 1ll * z[i - 1] * a % p; for(int i = 0; i < sp; i++) if(z[i] % p == b) return i; sort(z, z + sp); int asp = fastPower(a, sp, p); for(int i = 2, l = sp, r = sp + sp - 1; l <= n; l += sp, r += sp, i++) { int div = fastPower(asp, i - 1, p); div = fastPower(div ...

组合数学习笔记 定义: 排列：从 nnn 个元素中选取 rrr 个元素，当考虑顺序时，所有可能的方案一共有： Anr=n!(n−m)!A_n^r = \frac{n!}{(n - m)!} Anr​=(n−m)!n!​ 组合：从 nnn 个元素中选取 rrr 个元素，当不计顺序时，所有可能的方案一共有： Cnr=(nr)=n!m!(n−m)!=AnmAmmC_n^r = \left ( n \\ r \right ) = \frac{n!}{m!(n - m)!} = \frac{A_n^m}{A_m^m} Cnr​=(nr)=m!(n−m)!n!​=Amm​Anm​​ 组合数递推公式 如果将杨辉三角形写出来的话： 111121133114641⋯⋯⋯⋯⋯⋯\begin{array}{l} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ \cdots & \cdots & \cdots & \cdots ...

高精度加减乘模板 这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。 其中要注意的是高精度减法需要均为正数，且大数减小数。如何比较大小？模板里面重载了 <<< 运算符，可以直接比较大小。 修改结构体中的 WIDTH 与 BASE 可以达到修改压位的位数的目的。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192struct BigInt { static const int BASE = 10000; static const int WIDTH = 4; int s[10005], n; BigInt(long long num = 0) {*this = num;} ...

素数筛法及线性筛求积性函数值学习笔记 定义 快速求出 1 n1 ~ n1 n 中所有素数的方法。 埃氏筛 12345678bool not_prime[1005];memset(not_prime, 0, sizeof(not_prime));not_prime[1] = true;for(int i = 2; i <= n; i++) if(!not_prime[i]) for(int j = i + i; j <= n; j += i) not_prime[j] = true; 枚举每一个质数的倍数，并将其打上标记，时间复杂度为 OnloglognO{nloglogn}Onloglogn 。 欧拉筛 为了达到线性筛 O(n)O(n)O(n) 的复杂度，每个数都只能被筛掉一次。 将 xxx 质因数分解，写为 x=p1r1⋅p2r2⋯pkrkx = p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}x=p1r1​​⋅p2r2​​⋯pkrk​​ ，假设 p1<p2<⋯<pkp_1 ...

快速乘法 快速乘的名字是从快速幂抄过来的，事实上它比直接乘要慢。 思路和快速幂一样，对于 k×xk \times xk×x ，可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x2k​×x+2k​×x ，若 kkk 为奇数，则再加个 xxx 。 12345678int fastTimes(int x, int k, int p) { if(k == 0) return 0; int z = fastTimes(x, k >> 1, p); z = (z + z) % p; if(k % 2 == 1) z = (z + x) % p; return z;}

扩展欧几里得算法（ExGCD）代码 之前的数学笔记中讲过这个算法，所以这里把代码贴一下。 12345678910111213int exgcd(int a, int b, int& x, int& y) { if(b == 0) { x = 1; y = 0; return a; } int xp, yp; int g = exgcd(b, a % b, xp, yp); x = yp; y = xp - a / b * yp; return g;}