OI数学专题笔记 - 3

扩展欧几里得算法（ExGCD）代码

之前的数学笔记中讲过这个算法，所以这里把代码贴一下。

1
2
3
4
5
6
7
8
9
10
11
12

int 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;
}

Miller-Rabin 素性测试代码

• 之前的笔记中讲过这个算法，所以在这里把代码贴一下。

OI数学专题笔记 - 2

素数的定义和判定

定义

如果 $p$ 只有 1 和 $p$ 两个印子，则 $p$ 为负数。

Miller-Rabin 素性测试

如果 $n$ 为素数，取 $a < n$ ，设 $n - 1 = d \times 2^r$ ，则要么 $a^d \equiv 1 \pmod n$ ，要么 $\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n$ 。（费马小定理的推广形式）

矩阵快速幂学习笔记

快速幂

对于计算 $x^y$ 只需要计算 $x^{\frac{y}{2}} \times x^{\frac{y}{2}}$ ，如果 $y$ 是奇数只需要再乘 $x$ ，这样就可以把 $O(n)$ 的时间复杂度降为 $O(logn)$ 。

高斯消元

基本高斯消元法

对于行列式：

$\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 |$

OI数学专题笔记 - 1

排列和逆序对

定义

• 以任意一种顺序将相异的 $n$ 个数重排，每个顺序都称作一个排列。

• 在排列 $a_1 a_2 .. a_n$ 中，如果每有一个二元组 $(i, j)$ 满足 $i < j$ 且 $a_i > a_j$ ，则称 $a_i, a_j$ 组成了一个逆序对。

• 排列 $a_1 a_2 ... a_n$ 的逆序数表示为 $\tau(a_1 a_2 ... a_n)$ 。

• 定义：如果一个排列的逆序数为偶数，则称此排列为偶排列，否则称为奇排列。

• 定义：在一个排列中，对换其中某两个数，其余的数不动，得到另一个排列，这种操作称为一个对换。

线段树学习笔记

概述

假设要从数组arr[0 ... n - 1]查找某个数组某段区间的最小值，其中数组大小固定，但是数组中的元素可以随时更新。一个简单的解法是遍历数组区间寻找最小值，时间复杂度是$O(n)$，额外空间复杂度$O(1)$，当数据量特别大，查询操作很频繁时，耗时可能不能够满足要求。

SPFA学习笔记

介绍

SPFA(Shortest Path Faster Algorithm)就是队列优化的Bellman-Ford，时间复杂度声称可以优化到$O(km)$，实际很容易卡到最坏的情况$O(nm)$，可以处理负权边，判定负权环。建议除非有负权边，否则不要用SPFA。

Dijkstra学习笔记

介绍

这个算法适用于非负权图中求单源最短路（一个顶点到其他所有顶点的最短路），有着稳定优秀的时间复杂度，暴力Dij时间复杂度为$O(n^2)$，堆优后为$O(mlogn)$。事实上$m$和$n^2$是同阶的，不过一般情况下$m$远小于$n^2$，这种图被称为稀疏图；而$m$相对较大的图则被称为稠密图，这种情况下暴力Dij可能要比堆优Dij更优。