隔板法 至少每个盒子有1个小球
隔板法 2 盒子可以没有小球
杨辉三角求小范围组合数学
分水果
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
考试T10
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
考试T11
值域树状数组 + 离散化
树状数组求逆序对
1. 逆序对
满足：
则 (i,j) 是一对逆序对。
暴力做法：
复杂度 O(n²)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 核心思想
从左往右枚举 a[i]。
此时前面共有：
只需要知道：
这些数都能和 a[i] 组成逆序对。
树状数组维护：
> 前面每个数值出现的次数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 离散化
数据值可能很大，所以先排序去重，把数值变成排名。
例如：
变成：
代码：
查排名：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 树状数组维护什么
表示：
因此：
表示：
而前面总共有：
所以：
就是：
也就是当前新增的逆序对。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 核心代码
一定要：
因为我们统计的是前面的数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 记忆
核心两句：
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树状数组 + 差分：区间修改，单点查询
1. 差分数组
原数组：
定义差分数组：
那么原数组可以通过差分数组的前缀和还原：
所以：
> 查询 a[x]，等价于查询差分数组 d 的前缀和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 区间修改
如果要让：
差分数组只需要修改两个位置：
对应树状数组：
例如：
只需要：
这样从位置 2 开始多出 3，到位置 5 再把这个影响取消。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 为什么树状数组存差分
初始化：
说明树状数组维护的是：
查询：
实际上求：
根据差分：
所以：
就是查询修改后的 a[x]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 核心代码
区间增加：
单点查询：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 一句话记忆
> 树状数组维护差分 = 区间修改 + 单点查询。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
差分
树状数组
树状数组：修改与查询思想
1. 树状数组解决什么问题
树状数组适合处理：
* 单点修改
* 前缀和查询
* 区间和查询
核心目标：
> 不一个一个修改、不一个一个累加，而是利用 lowbit 快速跳到需要处理的结点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. LOWBIT 是什么
lowbit(x) 表示：
> x 的二进制中，最低位的 1 所代表的值。
例如：
树状数组中：
管理的区间长度就是：
所以 tr[x] 管理：
例如：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 修改操作
代码：
修改的核心思想
如果：
那么所有管理区间中包含 x 的结点都必须增加 k。
例如修改：
访问路径：
因为：
它们管理的区间都包含位置 3。
所以修改时不断：
可以理解成：
> 从当前结点不断跳到父亲结点。
修改记忆
时间复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 前缀和查询
代码：
query(x) 求的是：
也就是：
查询的核心思想
不是从 1 加到 x，而是把：
拆成几个树状数组已经保存好的区间。
例如：
访问：
对应：
所以：
因此：
查询时不断：
相当于：
> 每次拿走当前结点管理的一整块，再继续处理前面的部分。
查询记忆
时间复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 区间和查询
因为：
所以：
代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 修改和查询对比
操作 跳法 思想 修改 x += lowbit(x) 找所有包含 x 的父结点 查询 x -= lowbit(x) 把前缀拆成几个完整区间
最重要的两句话：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
乘法逆元入门
1. 什么是逆元？
如果：
那么 x 就叫做 a 在模 p 意义下的逆元。
数学写法：
例如模 13：
所以：
可以把逆元理解为：
> 模运算世界里的倒数。
普通数学：
模 13：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 逆元有什么用？
主要用来做模意义下的除法。
普通数学：
模运算：
代码：
例如：
因为：
所以：
验证：
因此模 13 意义下：
这里不是说普通数学中 7/2=10，而是说：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 逆元一定存在吗？
不一定。
例如模 6，找 2 的逆元：
永远得不到 1，所以 2 没有逆元。
一般：
时 a 才有逆元。
如果 p 是质数，那么：
全部都有逆元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 快速幂求逆元
当 p 是质数时，根据费马小定理：
所以：
因此：
记忆
一句话：
> 逆元就是模运算中的倒数，用来把除法变成乘法。
快速幂
C(N,K)
