Ender's Blog

Miller-Rabin 素性测试代码 之前的笔记中讲过这个算法，所以在这里把代码贴一下。 12345678910111213141516171819202122232425int prime[8] = {2, 3, 5, 7, 11, 13, 17, 37};bool miller_rabin(int n, int a) { int d = n - 1, r = 0; while(d % 2 == 0) d = d >> 1, r++; int z = fastPower(a, d, n); if(z == 1) return true; for(int i = 0; i < r; i++) { if(z == n - 1) return true; z = 1ll * z * z % n; } return false;}bool check(int n) { if(n < 2) return ...

OI中的数论学习笔记 素数的定义和判定 定义 如果 ppp 只有 1 和 ppp 两个印子，则 ppp 为素数。 Miller-Rabin 素性测试 如果 nnn 为素数，取 a<na < na<n ，设 n−1=d×2rn - 1 = d \times 2^rn−1=d×2r ，则要么 ad≡1(modn)a^d \equiv 1 \pmod nad≡1(modn) ，要么 ∃0≤i<r,s.t.ad×2i≡−1(modn)\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n∃0≤i<r,s.t.ad×2i≡−1(modn) 。（费马小定理的推广形式） 意思是：如果有一个素数 nnn ，任取 1≤a<n1 \leq a < n1≤a<n ，将 n−1n - 1n−1 分解为 n−1=d×2rn - 1 = d \times 2^rn−1=d×2r ，其中 ddd 为奇数， 则有如下两条性质至少有一条满足： ad≡1(modn)a^d \equiv 1 \pm ...

矩阵快速幂学习笔记 快速幂 对于计算 xyx^yxy 只需要计算 xy2×xy2x^{\frac{y}{2}} \times x^{\frac{y}{2}}x2y​×x2y​ ，如果 yyy 是奇数只需要再乘 xxx ，这样就可以把 O(n)O(n)O(n) 的时间复杂度降为 O(logn)O(logn)O(logn) 。 递归版： 12345678int fastPower(int x, int y, int p) { if(y == 0) return 1; int z = fastPower(x, y >> 1, p); z = 1ll * z * z % p; if(y % 2 == 1) z = 1ll * z * x % p; return z;} 迭代版： 1234567891011int fastPower(int x,int y,int p){ int ans = 1; while(y) { if(y & 1) ans = 1ll * ans * x % ...

高斯消元 基本高斯消元法 对于行列式： ∣a11a12a13...a1na21a22a23...a2na31a32a33...a3n...............an1an2an3...ann∣\left | \begin{array}{cccc} a_{1 1} & a_{1 2} & a_{1 3} & ... & a_{1 n} \\ a_{2 1} & a_{2 2} & a_{2 3} & ... & a_{2 n} \\ a_{3 1} & a_{3 2} & a_{3 3} & ... & a_{3 n} \\ ... & ... & ... & ... & ... \\ a_{n 1} & a_{n 2} & a_{n 3} & ... & a_{n n} \end{array} \right | ​a11​a21​a31​...an1​​a12​a22​a32​...an2​​a13​a23​a33​...an ...

OI中的线代学习笔记 排列和逆序对 定义 以任意一种顺序将相异的 nnn 个数重排，每个顺序都称作一个排列。 在排列 a1a2..ana_1 a_2 .. a_na1​a2​..an​ 中，如果每有一个二元组 (i,j)(i, j)(i,j) 满足 i<ji < ji<j 且 ai>aja_i > a_jai​>aj​ ，则称 ai,aja_i, a_jai​,aj​ 组成了一个逆序对。 排列 a1a2...ana_1 a_2 ... a_na1​a2​...an​ 的逆序数表示为 τ(a1a2...an)\tau(a_1 a_2 ... a_n)τ(a1​a2​...an​) 。 定义：如果一个排列的逆序数为偶数，则称此排列为偶排列，否则称为奇排列。 定义：在一个排列中，对换其中某两个数，其余的数不动，得到另一个排列，这种操作称为一个对换。 定理 对换改变排列的奇偶性。 证明： 对于排列 aiai+1...aj−1aja_i a_{i+1} ... a_{j-1} a_jai​ai+1​...aj−1​aj​ 将 ai ...

线段树学习笔记 概述 假设要从数组arr[0 ... n - 1]查找某个数组某段区间的最小值，其中数组大小固定，但是数组中的元素可以随时更新。一个简单的解法是遍历数组区间寻找最小值，时间复杂度是O(n)O(n)O(n)，额外空间复杂度O(1)O(1)O(1)，当数据量特别大，查询操作很频繁时，耗时可能不能够满足要求。 另一种做法是通过二维数组求出任意两个点为端点组成的区间的最小值，显然这样的预处理时间复杂度是O(n2)O(n^2)O(n2)，查询时间复杂度是O(1)O(1)O(1)，而额外的空间复杂度则是O(n2)O(n^2)O(n2)的，当数据量很大时， 这个空间消耗是庞大的。而如果我们想对这段区间内的任意点进行修改，或对某段子区间进行整体修改，再重新求出最小值，这样的操作十分麻烦，而且这个时间复杂度是不能接受的，所以我们可以使用一种数据结构来解决这类问题。 线段树，它在各个区间保存一条线段（数组中的一段子数组），主要用于高效解决连续区间动态查询问题（只要查询运算符合结合律都可以），它将每一段区间[L, R]都分解为[L, M]与[M + 1, R]左右两个子区间（其中M等于(L+ ...

SPFA学习笔记 介绍 SPFA(Shortest Path Faster Algorithm)就是队列优化的Bellman-Ford，时间复杂度声称可以优化到O(km)O(km)O(km)，实际很容易卡到最坏的情况O(nm)O(nm)O(nm)，可以处理负权边，判定负权环。建议除非有负权边，否则不要用SPFA。 Bellman-Ford的思想是对整张图进行n−1n-1n−1次松弛，每次枚举每条边进行松弛，最后一定能得出最优解，而SPFA使得在上述过程中避免了无意义的松弛。只有成功的松弛操作才会对那个点产生影响，所以使用队列维护等待松弛的点，每次取出一个点进行松弛，对于所有松弛成功的点加入队列。 如果某个点松弛了nnn次，则说明图中一定有负环。 实现 存图代码请看文末链接文章中的Dij笔记。 1234567891011121314151617181920212223242526const int MAXN = 100010;const int MAXM = 200010;bool inq[MAXN]; //inq[i]标记点i是否入队queue<int> ...

Dijkstra学习笔记 介绍 这个算法适用于非负权图中求单源最短路（一个顶点到其他所有顶点的最短路），有着稳定优秀的时间复杂度，暴力Dij时间复杂度为O(n2)O(n^2)O(n2)，堆优后为O(mlogn)O(mlogn)O(mlogn)。事实上mmm和n2n^2n2是同阶的，不过一般情况下mmm远小于n2n^2n2，这种图被称为稀疏图；而mmm相对较大的图则被称为稠密图，这种情况下暴力Dij可能要比堆优Dij更优。 该算法主要思想是将所有结点分为两个集合：已确定最短路径长度d[x]\rm d[x]d[x]的与没确定的。最开始前面的集合中只有起点sss。然后将前一个集合中的所有出边进行松弛，在后面的集合中选出最短路d[x]\rm d[x]d[x]最小的结点并标记访问，加入前面的集合中。直到所有节点都访问过即后一个集合没有元素，算法结束。 可以通过反向建图（将每条有向边的起点与终点互换）来求所有点到达一个固定点的最短路，只需要反向建图之后以到达的点为起点进行Dij。 实现 存图 这里使用邻接表进行存图 1234567891011121314151617const int MAXN = ...

线性代数学习笔记(2) 行列式 定义 线性变换对区域面积产生缩放的比例被称为这个变换的行列式(Determinant) 。记为：det([abcd])\rm{det}(\begin{bmatrix} a & b \\ c & d \end{bmatrix})det([ac​bd​]) 例如若行列式为3，就是说一个区域的面积被放大为原来面积的三倍；若行列式为12\frac 1 221​，就是说一个区域的面积被缩小为原来面积的一半。 性质 完整概念中的行列式是允许出现负值的，负值表示反转了空间取向，如果i^\hat ii^原来在j^\hat jj^​右边，变换后到了j^\hat jj^​左边，则这个空间取向被反转了。此时行列式的绝对值仍然表示区域面积的缩放比例。 在三维空间中，行列式表示体积的缩放比例。三维变换中，可以用右手定则判断空间取向：右手食指指向i^\hat ii^方向，右手中指指向j^\hat jj^​方向，则大拇指指向为k^\hat kk^方向。如果变换后仍然可以这么做，则空间取向没有反转，行列式为正；否则，只能用左手做，空间取向发生反转，行列式为负。 计算 对 ...

Floyd 学习笔记 最短路 性质 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。 对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过nnn ，边数不会超过 n−1n - 1n−1 。 （以上引自OI-Wikii） Floyd 算法 介绍 Floyd算法是用来求任意两个结点之间的最短路的。 时间复杂度O(n3)O(n^3)O(n3)，空间复杂度O(n2)O(n^2)O(n2)，算法复杂度较高，不过常数较少，容易实现。 实现 定义一个数组f[k][x][y]\rm{f[k][x][y]}f[k][x][y]表示只允许经过结点1到k，结点x到结点y的最短路长度。f[n][x][y]\rm{f[n][x][y]}f[n][x][y]就是结点x到结点y的最短路径长度。我们对每一个结点思考另外两个结点目前的距离与经过这个节点后的距离哪个更近，如果加入这个结点后更近，则将两个结点的距离更新为加入这个结点之后的距离。则状态转移方程为： f[k][x][y]=min( f[k−1][x][y],f ...