模方程

基础性质

模的等价关系

自反性
$$ a\equiv a \mod m $$
对称性
$$ a\equiv b \mod m\Leftrightarrow b\equiv a \mod m$$

组合游戏

1. 两个游戏者轮流操作
2. 游戏的状态集有限，每种状态最多出现一次（游戏可以结束）
3. 无法操作的输，另一个获胜（游戏必有胜负）
4. 公平游戏。两个游戏者面对相同的状态允许有相同的操作。

本文的编撰仅面向作者本人

1.6 Rules of Inference

1. Modus ponens 假言推理 p & p->q => q
2. Modus tollens 取拒式 !q & p->q => !p
3. Hypothetical syllogism /,haɪpə'θɛtɪk, 'sɪlə,dʒɪz(ə)m/ 假言三段论 p->q & q->r => p->r
4. Disjunctive syllogism 析取三段论 pVq & !p = p
5. Addtion 附加律 p => pVq （附加在析取式中）
6. Simplification 化简律 p&&q => p （合取条件的拆分）
7. Resolution 消解律 pVq & !pVr => qVr 条件相斥必有一T
8. ? Logical equivalence
   Read more »

换底公式

$\log_ab = \frac{\ln b}{\ln a}$

证明：
$e^{\ln a * \log_an} = b$ 两边取对数，移项。

$A^{\log_bC} = C^{\log_bA}$

证明：两边取对数，得$\log_bC \ln A = \frac{\ln C}{\ln b}*\ln A$

分治的时间复杂度

$T(N) = aT(N/b) + \Theta(N^k \log_p N)$

$$
T(N) = \begin{cases}
O(N^{\log_b a})& \text{if }a > b^k \
O(N^k \log_{p+1} N)& \text{if }a = b^k \
O(N^k \log_{p} N)& \text{if }a < b^k \
\end{cases}
$$

三角函数

sin,cos,tan知一求二

试试$(\tan^2x)^{(-1)^k}+1 = ?$

Treap

• 每个结点有随机的优先级，使树满足优先级树（堆）的性质，其余是普通排序二叉树
• 旋转：
  • 参数是子树根(引用子树根的儿子指针，否则要改一系列父子指针) ，旋转 即是 沉降，另一边的孩子上升，但该孩子可能丢失一个子树。
  • 引用原子树根可方便修改父亲指向自己的指针。
  • 总是因为查找才会引发旋转，所以旋转参数总是引用。
  • 没有返回值，因为新子树根就是父亲的儿子指针。
  • 记得维护其他数据域。
• 插入：
  • 自带查找
  • 新结点分配随机优先级，像排序二叉树一样插到一个叶子上（每个结点有计数器，可节省插入相同结点），然后旋转维护优先级树。
  • 递归地写，insert()后判断一下是否需要leftRotate() / rightRotate()。
• 删除：
  • 自带查找
  • 找到待删除结点，修改计数器（当且仅当计数器大于1！）。如果计数器就是1，就要将自己旋到外结点（没有儿子或有一个儿子），轻松自杀。
  • 引用root可以方便删掉父亲指向自己的指针。
  • 另一种删除方法：参考普通排序二叉树的删除，但优先级不能被拷贝。非递归地写能优化时间。
• 查找：
  • 和一般的二叉排序树一样。
  • 返回值可以写成地址引用？
• 分离：
  • 依赖于size，将树分离为两个指定大小的树。
  • 先找到割边，强行加入一个虚拟结点（优先级为无限大），旋转到根，这时左右子树已经被分离。
• 合并：
  • 合并和分离相反。要求其中一棵treap的所有结点小于另一棵。
  • 强行加入一个虚拟结点作为根（优先级为无限小），连接两棵treap，然后删除虚拟结点。

Splay

• 拥有将某一个结点旋转到根的操作Splay(&root, const x)，并在大多数操作中主动调用splay()
• 新建结点newNode(const v, const father = 0)
  • 返回地址
• 旋转：
  • 因为splay()旋转涉及很多代结点，不能用引用简化代码，必须存父亲指针。对应的孩子指针、父亲指针必须成对修改。
  • 参数是被旋转子树根的孩子，先处理祖先的孩子指针，再处理孩子的父亲指针，最后处理被旋转的两个结点的指针。“上有老 下有小 求放过...”
  • 可能会导致splay树根的改变，但是只有splay()导致旋转，splay()中自带根的记录。
  • 没有返回值，因为地址对应的内容没有变。
• Splay(&root, const x)：
  • 参数root是splay树根，x是结点地址。root必须引用，因为splay操作会更改树根。
  • 所有包含splay()的函数都要引用root
  • 依赖于祖先两代。若x仅有父亲而没有祖父，相应地旋转就好了。如果x有祖父，而且三点“共线”，就要先旋转父亲，后旋转x；如果三点不“共线”，正常地做就好。
• 插入(&root, const v)
  • 自带查找
  • 先判根，然后开始循环
  • 保存父亲y，引用孩子x，若x==0 则 x=newNode
  • 因为插入包含了splay()，所以要带引用root。
• 删除(&root, const v)：
  • 自带查找
  • 因为删除包含了splay()，所以要带引用root。
  • 如果被删结点是外结点，轻松自杀，splay()替身或者splay()父亲。
  • 如果被删结点不是外结点，那么被删结点肯定有前驱和后继在子树上，任取一个代替自己，然后splay()自己
• 前驱后继(&root const v) / (&root const x)
  • 将x旋到根，前驱就是左子树的最右结点，后继就是右子树的最左结点。
  • 因为包含了splay()，所以要带引用root。
• 有序合并join(&s1, s2)：
  • 将s1的最大元素splay到根，然后将s2设为s1的右子树
  • 因为含有splay()，所以要带引用root。
• 无序合并Merge(s1, s2)：
  • 依赖于额外数据域size
  • 遍历size小的splay树，逐个插入到另一颗splay树上
• 划分split(&root, const v)
  • 自带查找
  • 将关键字为v的结点splay到根，左右子树分开即可。
  • 因为含有splay()，所以要带引用root。
• splay树应用区间操作
  • 关键字将是下标，或者没有关键字。在一些下标可能集体移动的场合，宜不设关键字。
  • 结点记录子树的总体信息，类似线段树，可包含延迟标记。
  • 对区间[a,b]操作：将a-1旋到根，切掉右子树(b+1在其中)，再将b+1旋转到根，重新连接两棵树。这时b+1的左子树就是[a,b] 。
  • 在[a,a+1]中间插入一些数：将被插入的数构建成splay树。将a旋到根，a+1旋到根的右孩子。将新建的splay树挂成a+1的左孩子。
  • 重要的事情说n遍也不嫌多：小心root被更改。具体地说就是splay()要换根，只有splay()才能使用旋转。

普通排序二叉树

• 重点是前驱和后继
• 前驱(const v)
  • 必须自带查找
  • 在查找成功之前，记录最后一个往右走的结点，因为它可能是前驱
  • 查找成功之后，如果结点有左子树，那么左子树的最大结点一定是前驱
  • 如果一个结点是整棵树的最左（最小）结点，那么它没有前驱。
• 后继(const v)
  • 同前驱

对于询问网络图中每个点对的最大流（最小割容量），总是可以将图简化成n个点n-1条边的树型图，边上标有一些容量，使得在树上询问每个点对的最大流等价于原问题。

树链剖分的名字非常高大上， 其实不难， 本质是将树分解成几条链， 映射在线段树（树状数组、Splay等）上， 当我们需要在树上的路径（题目通常给定两个结点，在他们的路径上操作）进行操作时， 就能转化成在线段树（等数据结构）上进行操作， 接下来以树转线段树为例。

[toc]