模板整理(更新中)

数学相关

快速幂

快速幂通过二进制分解来快速求$a^b$的值,由于$a^b$的值很大,所以一般会带有模数。

快速幂可以推广到一切符合结合律的运算中(如:加法,矩阵乘法)。

欧拉筛

欧拉筛具体可以参见:这篇文章
欧拉筛保证每个合数均被其除自身以外最大的因数筛掉。能在O(n)的时间内求出1~n中所有的质数。线性筛还可用于求1~n中积性函数的值或者快速分解质因数。

辗转相除法(欧几里得算法)

欧几里得算法可用于求两个正整数的最大公约数。欧几里得算法通过等式gcd(a,b)=gcd(b,a%b)来递归求解,由于每层递归后a* b的值会至少减少一半,所以欧几里得算法的时间复杂度为$O(lg(a* b))$。

扩展欧几里得(ex_gcd)

扩展欧几里得用于求方程ax+by=gcd(a,b)的一组整数解,通常可用于求乘法在模意义下的逆元。时间复杂度与欧几里得算法相同。

欧拉定理

欧拉定理:对于a,p互质,有$a^{\varphi(p)}\equiv 1(\mod p)$其中$\varphi(p)$表示1到p中与p互质的数的个数。
不难发现,费马小定理只是欧拉定理的一个特殊情况。
我们不妨设1到p中与p互质的数从小到大分别为:$b_1,b_2,b_3,…,b_{\varphi(p)}$
【引理1】$ab_1,ab_2,ab_3,…,ab_{\varphi(p)}$在模p意义下互不相等。
证:假设该结论不成立,则可必定存在$ab_n\equiv ab_m(\mod p),1\le m\le n\le \varphi(p)$。
则$a(b_n-b_m)\equiv 0(\mod p)$
由于a与p互质,$b_n$与$b_m$均小于p且不相等,所以该式不可能成立。
引理1证毕。
【引理2】$ab_1,ab_2,ab_3,…,ab_{\varphi(p)}$均与p互质。
证:对于第i项,由于a与p互质,$b_i$与p互质,所以它们的乘积与p互质。证毕。
【引理3】$\lbrace ab_1\mod p,ab_2\mod p,…,ab_{\varphi(p)}\mod p \rbrace= \lbrace b_1,b_2,…,b_{\varphi(p)} \rbrace$
证:由引理1和引理2易得。
【欧拉定理】$a^{\varphi(p)}\equiv 1(\mod p)$
证:由引理3得,两个集合中的元素能一一对应,则它们的乘积相等,即:
$ab_1ab_2…ab_{\varphi(p)}\equiv b_1b_2…b_{\varphi(p)}(\mod p)$,将右边的除到左边去,可得:
$a^{\varphi(p)}\equiv 1(\mod p)$,即欧拉定理得证。
使用欧拉定理加上快速幂可以快速求出逆元。

合并模线性方程

合并模线性方程用于求解模线性方程组。这个方程组中每一个方程都是这种形式的:$x\equiv a_i (%b_i)$。可以通过等式$a_1+b_1y_1=a_2+b_2y_2$来求出一组$y_1,y_2$的解来进行合并。

该函数将结果存入a3和b3,返回值表示这个方程组是否有解。

组合数相关

线性求逆元

线性求逆元算法可以在O(n)时间内求出1~n中所有数在模MOD意义下的逆元。线性求逆元基于下列等式:
$i^{-1}=(MOD-MOD/i)(MOD%i)^{-1}$
证明:
令$ai+bequiv 0$
两边同乘$a^{-1}b^{-1}$有
$ab^{-1}+i^{-1} equiv 0$
因此得证。

快速求组合数

通过线性求逆元预处理出$i!$和$(i!)^{-1}$,快速求组合数。

lucas定理

lucas定理用于快速求$C_n^m %p$的值,其中n,m很大,但是p是质数并且不是很大。
lucas定理:
$$C_n^m \equiv C_{n/p}^{m/p} C_{n\%p}^{m\%p}$$
证明:
设$n=ap+b,m=cp+d$,则:

$$C_n^m \equiv \frac{(ap+b)!}{(cp+d)!((a-c)p+(b-d))!} $$

$$ \equiv \frac{a! (p!)^a b! } { c! (p!)^cd! (a-c)(p!)^{a-c}(b-d)!}$$

$$ \equiv C_{n/p}^{m/p} C_{n\% p}^{m\% p} $

离散化

离散化也是OI比赛中常用的技巧之一,这里由站长为大家写出。
由于b数组很大,但是我们不需要知道他的具体数值只要知道大小关系。这个时候我们可以对B数组进行离散化,代码见下。
input

output

code(by 劲大爷)

字符串算法

KMP算法

KMP算法通过nxt指针来进行快速匹配,可以在O(n)的时间内求出nxt数组,并在O(n)的时间内完成字符串匹配。代码中输出了所有匹配位置:

manacher算法

manacher算法用于求一个字符串中以每一个位置为中心的最大回文半径。其通过对称性进行快速求解,在摊还O(n)的时间复杂度内完成求解。模板:

数据结构

ST表

ST表可用于求解静态区间最大最小值查询问题。其预处理时间为O(nlgn),空间复杂度为O(nlgn),查询时间复杂度为O(1)。ST表也可以推广到一切可以重复计算的区间问题中(如区间gcd)。

树状数组

树状数组的本质是二项树森林,其可以快速计算1~x的区间和,可用于求解所有以1为起点的区间问题(求逆序对,求区间和等)。通过差分之类的操作可以解决更多问题。

树状数组应用——求逆序对

最近求逆序对的题目有很多,所以站长为大家整理了一下树状数组求逆序对的方法(包含离散化)

线段树

常规线段树

常规线段树可用于处理大多数区间问题。实现线段树要求维护的键值可合并并且打标记后能快速更新键值。但是时间复杂度的常数较大,而且要开4倍空间。线段树写法的变化很多,所以不建议写成template,以洛谷P3373为例贴一下我的代码:

ZKW线段树

ZKW线段树将常规线段树自顶向下的遍历方式改成了自底向上,。ZKW线段树全部通过迭代的方式进行操作,由于这种写法相对于常规线段树还可以使用更多的位运算,因此可以大大降低常数,缩减代码长度。但也带来了标记难以处理和代码细节问题增多的问题,所以个人认为主要作用还是在不做区间修改的问题中。写一个单点修改,区间求最小值的代码:

评测机上运行时间比常规线段树快了1/4左右。

动态开点线段树

动态开点线段树个人认为有两种。
第一种用于解决那些不需要初始化但是操作的下标值域范围非常大的问题。动态开点的基本思想是只把遍历到的点开出来。所以动态开点线段树需要将每个节点的两个儿子记下来,在每次down操作时开出新的节点,其它写法和常规线段树类似。
第二种类似于Trie树,用于解决一些在权值上的问题。这种写法可以理解为将每个元素二进制分解后看作一个01串然后丢入Trie树中,代码实现也和Trie树类似。可以用于插入删除,求前驱后继等,在一定程度上可代替平衡树。
动态开点线段树空间复杂度较高,容易被卡空间。

平衡树

平衡树一般指能让搜索树在较小时间界内完成其基本操作的数据结构,平衡树的应用非常广泛,C++STL中的很多东西都是使用红黑树(一种平衡树)来实现的。

Treap

可以戳这里来简单了解一下Treap。

SizeBalanceTree

普通平衡树代码:

SALT

文艺平衡树代码:

左偏树

一般的堆可以使用prioirty_queue来实现,但是如果需要涉及到合并操作就有点慢了,所以可以用左偏树来实现。

并查集

并查集可以在$O(alpha(n))$的摊还时间内完成创建一个集合,合并两个集合,判断两个元素是否属于一个集合的操作。

图论

最短路

Folyd算法

Folyd算法是动态规划,可在
$\Theta(n^3)$的时间复杂度内求出一个图所有点两两之间的最短路。

dijsktra算法

dijsktra算法是贪心,用于求解边权非负的单源最短路问题。时间复杂度是$\Theta(n^2)$加上二叉堆优化变为$O(Elgn)$,如果使用秩对堆等可优化到$O(E+nlgn)$。

Bellman-Ford算法

Bellman-Ford算法可用于求解所有单源最短路问题,时间复杂度$O(nE)$

SPFA算法

SPFA算法是Bellman-Ford算法的队列优化,玄学复杂度,可以出数据卡掉。

Tagged with:

3 thoughts on “模板整理(更新中)”

发表评论