一、基础操作

1.a<<b
将二进制a左移b位,不够的地方用0补位
例如100<<2 == 10000
2.a>>b
将二进制a右移b位
例如100>>2 == 1
3.a|b
或操作（按位或），相同位中只要有一个1或者两个1则结果为1，全0则结果为0
4.a&b
与操作（按位与），相同位中只要都是1，则结果为1，如果一个为0一个为1或者都是0则结果为0。
5.a^b
异或，相同位只要一个1一个0，则结果为1；相同位二进制相同则结果为0 。

二、进阶操作

1.快速求2^n
1<<n == pow(2,n)
原理：1<<n的意思是1的二进制向左移动n位，则此数二进制形式变成了 100000...000(n个0)，恰好是2^n
2.判断奇数偶数
n&1 == 1则为奇数
n&1 == 0则为偶数
原理：n&1的意思是n与1，那么n与1中，1除了右端位为1其他位都是0，则由与运算得到的结果中其他位必定都是0 。
所以最后得到的结果只与1的右端位和n的右端位有关，我们知道1的右端位为1，那么n的右端位只有为1的时候与1进行与运算的结果是1；n的右端位只有为0的时候与1进行与运算的结果是0 。
显然二进制右端位为1的时候该数为奇数，为0时该数为偶数，所以得证。
3.lowbit
a&(-a) 代表着a的二进制的最后一位。
原理：涉及到二进制的补码知识

三、高阶操作

1.a >> b & 1 代表着如果a的第b位为1则为真
用来判断二进制的某一位
原理：a左移b位，则a的右端位就是原来a的第b位，这时与1做与运算(1左边的0由与运算性质得没有影响)就可以得知这一位是1还是0（1&1 == 1,0|1 == 0 ）
2.a|(1<<n) 代表着将a的二进制的第n位设为1
原理：1<<n可以看作由一个1和n个0组成的二进制数，其中0的部分由或的性质(0|00,1|01)可以知道不会对二进制位产生影响。
而1的部分由或的性质(1|1==1,0|1=1)可以得出一定是1。

四、图论

x表示要判断的点，S表示集合
(1 << x) & S == true 即x在S集合里，如果为false则x不在S集合里
S = S | (1 << x) 表示S集合中加入了x点

五、原码、反码、补码

原码：是最简单的机器数表示法。用最高位表示符号位，‘1’表示负号，‘0’表示正号。其他位存放该数的二进制的绝对值。
反码：正数的反码还是等于原码，负数的反码就是他的原码除符号位外，按位取反。
若以带符号位的四位二进制数为例：

1. 3是正数，反码与原码相同，则可以表示为0011
2. -3的原码是1011，符号位保持不变，低三位（011）按位取反得（100）
3. 所以-3的反码为1100

补码：正数的补码等于他的原码，负数的补码等于反码+1。

0原码是00000000
-0原码是10000000
0反码是00000000
-0反码是11111111
0补码是00000000

六、运算顺序

括号>非>算术运算（×，/，div，mod，and）>逻辑运算（与>或、异或）>（=、<>,>=,<=）
例题：

2 排列组合

递推数

Catalan 数列

以下问题属于 Catalan 数列：

1. 有 (2n) 个人排成一行进入剧场。入场费 5 元。其中只有 (n) 个人有一张 5 元钞票，另外 (n) 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
2. 一位大城市的律师在她住所以北 (n) 个街区和以东 (n) 个街区处工作。每天她走 (2n) 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3. 在圆上选择 (2n) 个点，将这些点成对连接起来使得所得到的 (n) 条线段不相交的方法数？
4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
5. 一个栈（无穷大）的进栈序列为 (1,2,3, cdots ,n) 有多少个不同的出栈序列？
6. (n) 个结点可够造多少个不同的二叉树？
7. (n) 个不同的数依次进栈，求不同A的出栈结果的种数？
8. (n) 个 (+1) 和 (n) 个 (-1) 构成 (2n) 项 (a_1,a_2, cdots ,a_{2n}) ，其部分和满足 (a_1+a_2+ cdots +a_k geq 0(k=1,2,3, cdots ,2n)) 对与 (n) 该数列为？

其对应的序列为：

(Catalan 数列）

递推式

该递推关系的解为：

关于 Catalan 数的常见公式：

例题洛谷 P1044 栈"
题目大意：入栈顺序为 (1,2,ldots ,n) ，求所有可能的出栈顺序的总数。

#include <iostream>
using namespace std;
int n;
long long f[25];
int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见公式2
  cout << f[n] << endl;
  return 0;
}

路径计数问题

非降路径是指只能向上或向右走的路径。

1. 从 ((0,0)) 到 ((m,n)) 的非降路径数等于 (m) 个 (x) 和 (n) 个 (y) 的排列数，即 (dbinom{n + m}{m}) 。

2. 从 ((0,0)) 到 ((n,n)) 的除端点外不接触直线 (y=x) 的非降路径数：

   先考虑 (y=x) 下方的路径，都是从 ((0, 0)) 出发，经过 ((1, 0)) 及 ((n, n-1)) 到 ((n,n)) ，可以看做是 ((1,0)) 到 ((n,n-1)) 不接触 (y=x) 的非降路径数。

   所有的的非降路径有 (dbinom{2n-2}{n-1}) 条。对于这里面任意一条接触了 (y=x) 的路径，可以把它最后离开这条线的点到 ((1,0)) 之间的部分关于 (y=x) 对称变换，就得到从 ((0,1)) 到 ((n,n-1)) 的一条非降路径。反之也成立。从而 (y=x) 下方的非降路径数是 (dbinom{2n-2}{n-1} - dbinom{2n-2}{n}) 。根据对称性可知所求答案为 (2dbinom{2n-2}{n-1} - 2dbinom{2n-2}{n}) 。

3. 从 ((0,0)) 到 ((n,n)) 的除端点外不穿过直线 (y=x) 的非降路径数：

   用类似的方法可以得到： (dfrac{2}{n+1}dbinom{2n}{n})

第一类斯特林数（Stirling Number）

第一类斯特林数 （斯特林轮换数） (egin{bmatrix}n\ kend{bmatrix}) 表示将 (n) 个两两不同的元素，划分为 (k) 个非空圆排列的方案数。

递推式

边界是 (egin{bmatrix}n\ 0end{bmatrix}=[n=0]) 。

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

• 将该新元素置于一个单独的圆排列中，共有 (egin{bmatrix}n-1\ k-1end{bmatrix}) 种方案；
• 将该元素插入到任何一个现有的圆排列中，共有 ((n-1)egin{bmatrix}n-1\ kend{bmatrix}) 种方案。

根据加法原理，将两式相加即可得到递推式。

第二类斯特林数（Stirling Number）

第二类斯特林数 （斯特林子集数） (egin{Bmatrix}n\ kend{Bmatrix}) 表示将 (n) 个两两不同的元素，划分为 (k) 个非空子集的方案数。

递推式

边界是 (egin{Bmatrix}n\ 0end{Bmatrix}=[n=0]) 。

还是考虑组合意义来证明。

我们插入一个新元素时，有两种方案：

• 将新元素单独放入一个子集，有 (egin{Bmatrix}n-1\ k-1end{Bmatrix}) 种方案；
• 将新元素放入一个现有的非空子集，有 (kegin{Bmatrix}n-1\ kend{Bmatrix}) 种方案。

根据加法原理，将两式相加即可得到递推式。

应用

上升幂与普通幂的相互转化

我们记上升阶乘幂 (x^{overline{n}}=prod_{k=0}^{n-1} (x+k)) 。

则可以利用下面的恒等式将上升幂转化为普通幂：

如果将普通幂转化为上升幂，则有下面的恒等式：

下降幂与普通幂的相互转化

我们记下降阶乘幂 (x^{underline{n}}=dfrac{x!}{(x-n)!}=prod_{k=0}^n-1 (x-k)) 。

则可以利用下面的恒等式将普通幂转化为下降幂：

如果将下降幂转化为普通幂，则有下面的恒等式：

贝尔数

贝尔数以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是 ( OEIS A000110 )：

(B_n) 是基数为 (n) 的集合的划分方法的数目。集合 (S) 的一个划分是定义为 (S) 的两两不相交的非空子集的族，它们的并是 (S) 。例如 (B_3 = 5) 因为 3 个元素的集合 ({a, b, c}) 有 5 种不同的划分方法：

(B_0) 是 1 因为空集正好有 1 种划分方法。

公式

贝尔数适合递推公式：

证明：

(B_{n+1}) 是含有 (n+1) 个元素集合的划分个数，设 (D_n) 的集合为 ({b_1,b_2,b_3,dots,b_n}) ， (D_{n+1}) 的集合为 ({b_1,b_2,b_3,dots,b_n,b_{n+1}}) ，那么可以认为 (D_{n+1}) 是有 (D_{n}) 增添了一个 (b_{n+1}) 而产生的，考虑元素 (b_{n+1}) 。

假如它被单独分到一类，那么还剩下 (n) 个元素，这种情况下划分数为 (inom{n}{n}B_{n}) ;

假如它和某 1 个元素分到一类，那么还剩下 (n-1) 个元素，这种情况下划分数为 (inom{n}{n-1}B_{n-1}) ；

假如它和某 2 个元素分到一类，那么还剩下 (n-2) 个元素，这种情况下划分数为 (inom{n}{n-2}B_{n-2}) ；

以此类推就得到了上面的公式。

每个贝尔数都是相应的第二类 斯特林数 的和。
因为第二类斯特林数是把基数为 (n) 的集合划分为正好 (k) 个非空集的方法数目。

贝尔三角形

用以下方法构造一个三角矩阵（形式类似杨辉三角形）：

• 第一行第一项为 1 ((a_{1,1}=1)) ；
• 对于 (n>1) ，第 (n) 行第一项等于第 (n-1) 行的第一项 ((a_{n,1}=a_{n-1,n-1})) ；
• 对于 (m,n>1) ，第 (n) 行的第 (m) 项等于它左边和左上角两个数之和 ((a_{n,m}=a_{n,m-1}+a_{n-1,m-1}))

部分结果如下：

每行的首项是贝尔数。可以利用这个三角形来递推求出 Bell 数。

"参考实现"

const int maxn = 2000 + 5;
int bell[maxn][maxn];
void f(int n) {
   bell[1][1] = 1;
  for (int i = 2; i <= n; i++) {
   bell[i][1] = bell[i - 1][i - 1];
    for (int j = 2; j <= i; j++)
    bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1];
  }
 }

抽屉原理

就比如说，你有 (n+1) 个苹果，想要放到 (n) 个抽屉里，那么必然会有至少一个抽屉里有两个（或以上）的苹果。

这个定理看起来比较显然，证明方法考虑反证法：假如所有抽屉都至多放了一个苹果，那么 (n) 个抽屉至多只能放 (n) 个苹果，矛盾。

排列组合

排列数

从(n)个不同元素中，任取(m)个元素按照一定顺序排成一列，叫做(n)个不同元素取出(m)个元素的一个排列。排列的个数叫做排列数，表达式是:

全排列：(A_n^n=n!)

组合数

不考虑顺序的排列数
从(n)个不同元素中取出(m)个元素组成一个集合，叫做一个组合，组合的个数叫组合数。

组合数也常用 (displaystyle inom{n}{m}) 表示，读作「 (n) 选 (m) 」，即 (displaystyle mathrm C_n^m=inom{n}{m}) 。实际上，后者表意清晰明了，美观简洁，因此现在数学界普遍采用 (displaystyle inom{n}{m}) 的记号而非 (mathrm C_n^m) 。

组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。

特别地，规定当 (m>n) 时， (mathrm A_n^m=mathrm C_n^m=0) 。

错位排列

我们把错位排列问题具体化，考虑这样一个问题：

(n) 封不同的信，编号分别是 (1,2,3,4,5) ，现在要把这 5 封信放在编号 (1,2,3,4,5) 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设我们考虑到第 (n) 个信封，初始时我们暂时把第 n 封信放在第 n 个信封中，然后考虑两种情况的递推：

• 前面 (n-1) 个信封全部装错；
• 前面 (n-1) 个信封有一个没有装错其余全部装错。

对于第一种情况，前面 (n-1) 个信封全部装错：因为前面 (n-1) 个已经全部装错了，所以第 n 封只需要与前面任一一个位置交换即可，总共有 (f(n-1) imes (n-1)) 种情况。

对于第二种情况，前面 (n-1) 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 (n-1) 个信封中如果有一个没装错，那么我们把那个没装错的与 (n) 交换，即可得到一个全错位排列情况。

其他情况，我们不可能通过一次操作来把它变成一个长度为 n 的错排。

于是可得错位排列的递推式为 (f(n)=(n-1)(f(n-1)+f(n-2))) 。

错位排列数列的前几项为 (0,1,2,9,44,265) 。

圆排列

(n) 个人全部来围成一圈，所有的排列数记为 (mathrm Q_n^n) 。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有

由此可知部分圆排列的公式：

3 数据结构

a Splay树

给定一颗二叉树，每一个节点有一个权值，叫做“关键码”。其性质是，对于树中任何一个节点：

1. 这个节点的关键码不小于它左子树上任意一个节点的关键码
2. 这个节点的关键码不大于它右子树上任意一个节点的关键码

我们可以发现这棵树的中序遍历，就是一个关键码单调递增的节点序列。

对于这样一棵树，我们可以做一些特殊的操作，来让它变换树的形态结构，但是最后的答案却是正确的，平衡树的精髓就是这个，改变树的结构形态，但是不改变最后的中序遍历，也就是答案数组。

现在我们的目标是让x节点向上爬，爬到原本的父亲节点y，并让y下降
首先我们知道，右子树上的点都比父亲节点大，仙子我们x节点是y节点的父亲节点，所以x<y，为了不改变答案顺序，我们可以让y节点成为x节点的右儿子，也就是y节点仍然大于x节点
之后又有问题了，x节点的右子树本来是B，那么如果说现在y节点以及它的右子树（没有左子树，因为曾经x节点是它的左子树），放到了x节点的右子树上，那就会多了一些东西。
我们知道x节点的右子树必然是大于x节点的，y节点必然是大于x节点的右子树和x节点的，因为x节点和它的右子树都是在y节点的左子树，都比他小
既然如此的话，我们为什么不把x节点原来的右子树，放在节点y的左子树上面呢？这样的话，我们就巧妙地避开了冲突，达成了x节点上移，y节点下移

以下是通解
若节点x为y节点的位置z（z=0则为左节点，z=1为右节点）

1. 那么y节点就放到x节点的z^1的位置（也就是x节点为y节点的右子树，那么y节点就放到左子树，x节点为y节点左子树，那么y节点就放到右子树位置，完美满足条件）
2. 如果说x节点的z^{1的位置上已经有节点或者是一棵子树，那么我们就将原来x节点z}1位置上的子树，放到y节点的位置z上面
3. 移动完毕

void update(int x)
{
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;//左子树+右子树+本身多少个,cnt记录重复个数.
}
void rotate(int x)//X是要旋转的节点
{
    int y=t[x].ff;//X的父亲
    int z=t[y].ff;//X的祖父
    int k=t[y].ch[1]==x;//X是Y的哪一个儿子 0是左儿子 1是右儿子
    t[z].ch[t[z].ch[1]==y]=x;//Z的原来的Y的位置变为X
    t[x].ff=z;//X的父亲变成Z
    t[y].ch[k]=t[x].ch[k^1];//X的与X原来在Y的相对的那个儿子变成Y的儿子
    t[t[x].ch[k^1]].ff=y;//更新父节点
    t[x].ch[k^1]=y;//X的 与X原来相对位置的儿子变成 Y
    t[y].ff=x;//更新父节点
    update(y);update(x);//yyb大佬忘记写了,这里是上传修改.
}

这里用到了t[y].ch[1]==x，t[y].ch[1]是y的右儿子，如果x是右儿子，那么这个式子是1，否则是0，也正好对应着左右儿子，同样的k^{1，表示相对的儿子，左儿子0}1=1右儿子1^1=0

(operatorname{Splay})函数

如果说x,y,z三个节点共线，也就是x和它的父亲节点y和它的祖先节点在同一条线段上的话，那么我们就需要再来一些特殊处理了，其实就是一些操作。

这张图片中最长链为Z->Y->X->A
如果我们一直都是x旋转的话，就会得到：

一直旋转X的最长链是X->Z->y->B
旋转和不旋转似乎没有区别
解决方法：

1. 如果当前处于共线状态的话，那么先旋转y，再旋转x，这样可以强行让他们不处于共线状态，然后平衡这棵树。
2. 如果当前不是共线状态的话，只要旋转x

这就是splay的双旋操作

void splay(int x,int goal)//将x旋转为goal的儿子，如果goal是0则旋转到根
{
    while(t[x].ff!=goal)//一直旋转到x成为goal的儿子
    {
        int y=t[x].ff,z=t[y].ff;//父节点祖父节点
        if(z!=goal)//如果Y不是根节点，则分为上面两类来旋转
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);//判断共线还是不共线
            //这就是之前对于x和y是哪个儿子的讨论
        rotate(x);//无论怎么样最后的一个操作都是旋转x
    }
    if(goal==0)root=x;//如果goal是0，则将根节点更新为x
}

b 替罪羊树

c 红黑树

4 图论知识

概念

染色

5 康拓展开

康托展开可以用来求一个 (1sim n) 的任意排列的排名。

什么是排列的排名？

把 (1sim n) 的所有排列按字典序排序，这个排列的位次就是它的排名。

时间复杂度？

康托展开可以在 (O(n^2)) 的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到 (O(nlog n)) 。

怎么实现？

因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。

比如 (4) 的排列， ([2,3,1,4]<[2,3,4,1]) ，因为在第 (3) 位出现不同，则 ([2,3,1,4]) 的排名在 ([2,3,4,1]) 前面。

举个栗子

我们知道长为 (5) 的排列 ([2,5,3,4,1]) 大于以 (1) 为第一位的任何排列，以 (1) 为第一位的 (5) 的排列有 (4!) 种。这是非常好理解的。但是我们对第二位的 (5) 而言，它大于 第一位与这个排列相同的，而这一位比 (5) 小的 所有排列。不过我们要注意的是，这一位不仅要比 (5) 小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为 (1,3) 或 (4) ，第一位为 (2) 的所有排列都比它要小，数量为 (3 imes 3!) 。

按照这样统计下去，答案就是 (1+4!+3 imes 3!+2!+1=46) 。注意我们统计的是排名，因此最前面要 (+1) 。

注意到我们每次要用到 当前有多少个小于它的数还没有出现 ，这里用树状数组统计比它小的数出现过的次数就可以了。

逆康托展开

因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。

如果我们知道一个排列的排名，就可以推出这个排列。因为 (4!) 是严格大于 (3 imes 3!+2 imes 2!+1 imes 1!) 的，所以可以认为对于长度为 (5) 的排列，排名 (x) 除以 (4!) 向下取整就是有多少个数小于这个排列的第一位。

引用上面展开的例子

首先让 (46-1=45) ， (45) 代表着有多少个排列比这个排列小。 (lfloorfrac {45}{4!} floor=1) ，有一个数小于它，所以第一位是 (2) 。

此时让排名减去 (1 imes 4!) 得到 (21) ， (lfloorfrac {21}{3!} floor=3) ，有 (3) 个数小于它，去掉已经存在的 (2) ，这一位是 (5) 。

(21-3 imes 3!=3) ， (lfloorfrac {3}{2!} floor=1) ，有一个数小于它，那么这一位就是 (3) 。

让 (3-1 imes 2!=1) ，有一个数小于它，这一位是剩下来的第二位， (4) ，剩下一位就是 (1) 。即 ([2,5,3,4,1]) 。

实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第 (3) 个没有被选上的数，这里也可以用线段树维护，时间复杂度为 (O(nlog n)) 。