【算法】Tricks of Algorithm

Tricks of Algorithm

---

>> 非常好的汇总博客 <<

https://www.cnblogs.com/Appleblue17/p/14295686.html

https://www.cnblogs.com/Appleblue17/p/14318717.html

https://www.cnblogs.com/Appleblue17/p/15314982.html

---

鞅与停时定理

https://www.cnblogs.com/Appleblue17/p/15659128.html

https://www.luogu.com.cn/blog/littleZ-meow-0v0/gai-shuai-lun-ke-ji-yang-yu-ting-shi-ding-li

多项式

https://www.cnblogs.com/Appleblue17/p/14360752.html

二项式反演与容斥

https://www.cnblogs.com/Appleblue17/p/14192176.html

拉格朗日插值

https://www.luogu.com.cn/problem/P4781

Matrix-Tree 定理

https://www.luogu.com.cn/problem/P6178

Berlekamp–Massey 算法

https://www.luogu.com.cn/problem/P5487Berlekamp-Massey

简称BM算法，是用来求解一个数列最短线性递推式的算法，时间复杂度为 \(O(n^2)\)。

子集卷积

https://www.luogu.com.cn/problem/P6097

快速莫比乌斯/沃尔什变换 (FMT/FWT)

https://www.luogu.com.cn/problem/P4717

常系数齐次线性递推

https://www.luogu.com.cn/problem/P4723

常系数非齐次线性递推

https://www.luogu.com.cn/problem/P5808

扩展欧几里德算法（exgcd）

https://www.luogu.com.cn/problem/P5656

扩展中国剩余定理（exCRT）

https://www.luogu.com.cn/problem/P4777

BSGS：大步小步算法

https://www.luogu.com.cn/problem/P3846

扩展 BSGS（exBSGS）

https://www.luogu.com.cn/problem/P4195

线性基

https://www.luogu.com.cn/problem/P4869

https://www.luogu.com.cn/problem/P3812

类欧几里得算法

https://www.luogu.com.cn/problem/P5170

具体数学

https://www.cnblogs.com/Appleblue17/p/16653961.html#!comments

生成函数（母函数）

https://blog.csdn.net/dragonylee/article/details/107660418

wqs 带权二分

https://www.cnblogs.com/Appleblue17/p/14219912.html

https://blog.csdn.net/corsica6/article/details/88040699

https://www.cnblogs.com/wxywxywxy/p/15640693.html

Garsia–Wachs 算法

用于石子合并、最优二叉搜索树。

时间复杂度：\(O(n\log{n})\)

显著优于使用四边形不等式优化后的 \(O(n^2)\)

CDQ 分治

https://oi-wiki.org/misc/cdq-divide/

https://zhuanlan.zhihu.com/p/260683793

三维偏序：CDQ 分治

https://www.luogu.com.cn/problem/P3810

线段树合并

https://www.luogu.com.cn/problem/P4556

zkw线段树

https://blog.csdn.net/weixin_43960287/article/details/108246164

重口味线段树不仅比普通线段树速度快、空间小，而且码量小得多，循环结构思路也很清晰，很适合用来优化Dijkstra和套在树剖以及树套树上。

其中最重要的一点是，zkw的常数很小，仅次于树状数组。一个打得很烂的zkw，常数也不会劣于卡常卡得最好的普通线段树。（拿LOJ132为例，我的zkw和树状数组的码量差不多，跑得比所有普通线段树做法和部分树状数组做法快）

杜教筛

https://www.luogu.com.cn/problem/P4213

https://www.cnblogs.com/yaoxi-std/p/16558980.html

时间复杂度： \[ O(n^\frac23) \]

PN筛

https://www.cnblogs.com/yaoxi-std/p/16558980.html

Powerful Number 筛 (PN 筛)

时间复杂度：\[ O(\sqrt n \log{n}) \]

min25筛

https://zhuanlan.zhihu.com/p/60378354

https://www.cnblogs.com/Appleblue17/p/14185584.html

求一类积性函数的和

时间复杂度： \[ O(\frac{n^\frac34}{\log{n}}) \]

朱震霆筛法

时间复杂度： \[ O(\frac{n^\frac23}{\log{n}}) \]

洲阁筛

求一类积性函数的和

时间复杂度： \[ O(\frac{n^\frac34}{\log{n}}) \]

最小树形图：朱刘算法

https://blog.csdn.net/txl199106/article/details/62045479

https://www.luogu.com.cn/discuss/752758

https://oi-wiki.org/graph/dmst/

模拟退火

圆方树：仙人掌

https://oi-wiki.org/graph/block-forest/

动态仙人掌

后缀平衡树

https://oi-wiki.org/string/suffix-bst/

SBT

https://www.cnblogs.com/chenhuan001/p/5788272.html

Prufer 序列

https://www.luogu.com.cn/problem/P6086

树上启发式合并（DSU on Tree）

https://www.luogu.com.cn/problem/CF600E

后缀自动机（SAM）

https://www.luogu.com.cn/problem/P3804

https://www.luogu.com.cn/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie

Runs

https://www.luogu.com.cn/problem/P6656

一个字符串 \(s\) 中的一个 runs 是一个循环子串，例如 aabcabcabb 中 abcabcab 这个子串就是一个 runs。

Lyndon 分解：Duval算法

https://www.luogu.com.cn/problem/P6114

https://zhuanlan.zhihu.com/p/664357638

一个串是 Lyndon 串，当且仅当这个串的最小后缀就是这个串本身。

回文自动机（PAM）

https://www.luogu.com.cn/problem/P5496

笛卡尔树

https://www.luogu.com.cn/problem/P5854

文艺平衡树

https://www.luogu.com.cn/problem/P3391

珂朵莉树

https://www.luogu.com.cn/blog/602632/ke-duo-li-shi-quan-shi-jie-zui-xing-fu-di-ru-hai

https://www.cnblogs.com/lyp-Bird/p/10310609.html

旧称 ODT（Old Driver Tree）

动态树（Link Cut Tree，LCT）

https://www.luogu.com.cn/problem/P3690

树上 K 级祖先

https://www.luogu.com.cn/problem/P5903

虚树

https://www.luogu.com.cn/problem/P2495

重链剖分/树链剖分

https://www.luogu.com.cn/problem/P3384

缩点

https://www.luogu.com.cn/problem/P3387