2020-2021:teams:legal_string:王智彪:数理知识
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/10 16:43] 王智彪 |
2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/10 23:17] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 54: | 行 54: | ||
| ==== 模拟集合操作 ==== | ==== 模拟集合操作 ==== | ||
| - | 差集是 $a\&(~b)$ 对称差是 $a^b$ | + | 差集是 $a\&(~b)$ 对称差是 $a$ ^ $b$ |
| ==== 子集遍历 ==== | ==== 子集遍历 ==== | ||
| 行 62: | 行 62: | ||
| 这个复杂度为 $O(2^{popcount(u)})$ 的复杂度遍历 $u$ 的子集 | 这个复杂度为 $O(2^{popcount(u)})$ 的复杂度遍历 $u$ 的子集 | ||
| - | 进而可以在O(3^{n})的时间复杂度内遍历大小为n的集合的每个子集的子集 | + | 进而可以在 $O(3^{n})$ 的时间复杂度内遍历大小为n的集合的每个子集的子集 |
| <code cpp> | <code cpp> | ||
| 行 74: | 行 74: | ||
| </code> | </code> | ||
| + | |||
| + | ==== GCC内建函数 ==== | ||
| + | |||
| + | 这些函数经过编译器的高度优化，运行速度很快，且省事 | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | int __builtin_ffs(int x) | ||
| + | |||
| + | </code> | ||
| + | |||
| + | 返回 $x$ 的二进制中最后一个为 $1$ 的位置，最低位的编号为 $1$ ，当 $x$ 为 $0$ 时返回 $0$ | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | int __builtin_clz(unsigned int x) | ||
| + | |||
| + | </code> | ||
| + | |||
| + | 返回 $x$ 的二进制的前导 $0$ 的个数。也就是可以确定二进制从左到右第一个为 $1$ 的位置 | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | int __builtin_popcount(unsigned int x) | ||
| + | |||
| + | </code> | ||
| + | |||
| + | 返回 $x$ 的二进制中 $1$ 的个数 | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | int __builtin_parity(unsigned int x) | ||
| + | |||
| + | </code> | ||
| + | |||
| + | 判断 $x$ 的二进制中 $1$ 的个数的奇偶性 | ||
| + | |||
| + | ===== 矩阵的操作 ===== | ||
| + | |||
| + | 例题1：三维空间中 $n$ 个点 $p_{i}$ ，要求将 $m$ 个操作都应用与这些点，操作种类有三种： | ||
| + | |||
| + | 1.沿向量移动 | ||
| + | |||
| + | 2.按比例缩放坐标 | ||
| + | |||
| + | 3.绕某个坐标轴旋转 | ||
| + | |||
| + | 这些操作都可以重复 $k$ 次。 | ||
| + | |||
| + | 要求在尽可能低于 $O(nmk)$ 的时间内输出最终结果 | ||
| + | |||
| + | 对于三种操作，我们都可以理解为对三维坐标的线性变换。前两种的 $k$ 次很好解决。 | ||
| + | |||
| + | 看起来第二种很好搞，将 $3×3$ 的矩阵的对角分别写上三个维度的缩放比例，在进行矩阵乘法的时候就可以直接乘了。 | ||
| + | |||
| + | 但是这样对于第一种操作，我们首先肯定至少需要 $3×3$ 的矩阵，对角线是 $1$ ，因为要加上新输入的值，但新输入的值却没有地方放，只能将矩阵扩大，比如变成 $4×4$ 的。为了让三个维度的增量不相互影响，需要把新的增量写在新的一列，比如我们让 $AX=X'$ ， $x'=x+dx$ ，其中 $X$ 和 $X'$ 都是 $4×1$ 的矩阵，于是前三行都已经确定，都是由对角线的 $1$ 和最后的增量构成， $X$ 和 $X'$ 最后一行也可以确定为 $1$ ，因为要乘上增量，于是 $A$ 的最后一行也是在对角线那里是 $1$ 才可以保证 $X'$ 的最后一行为 $1$ 。 | ||
| + | |||
| + | 处理好了第一种操作，回头再看第二种操作。只需要在最后一行对角线处加一个 $1$ 就正确了。 | ||
| + | |||
| + | 现在只剩下第三种操作。比如绕 $z$ 轴旋转， $z$ 坐标不变，所以显然下面的两行只有对角线元素是 $1$ 。对于上面的矩阵，只需要考虑最左上角的 $2×2$ 即可。然后可以将坐标变为复平面就可以推出坐标变换之后和原坐标关系，矩阵就能求出来了，然后对于 $x,y$ 轴同理。 | ||
| + | |||
| + | 于是就把三种矩阵处理好了，分别求 $k$ 的快速幂，这样复杂度可以看成是 $O(mlogk)$ ，最后对于 $n$ 个点，分别乘矩阵，总复杂度为 $O(n+mlogk)$ 。 | ||
| + | |||
| + | 例题2：定长路径计数 | ||
| + | |||
| + | 给一个有向图，边权都为 $1$ ，求任意两点 $u,v$ 间从 $u$ 到 $v$ ，长度为 $k$ 的路径的条数。 | ||
| + | |||
| + | 套路题，将邻接矩阵求 $k$ 次幂即可。 | ||
| + | |||
| + | 如果是小于等于 $k$ ，则对于每个点加一个权值为 $1$ 的自环，这样就可以原地踏步，包括所有情况了。 | ||
| + | |||
| + | 例题3：树上询问 | ||
| + | |||
| + | 有一颗 $n$ 结点的树，根为 $1$ 号结点。每个结点有两个权值 $k_{i},t_{i}$ ，初始值均为 $0$ 。 | ||
| + | |||
| + | 有三种操作： | ||
| + | |||
| + | 1.将 $x$ 到根的路径上所有点的 $k_{i}$ 变成 $k_{i}+d$ | ||
| + | |||
| + | 2.将 $x$ 到根的路径上所有点的 $t_{i}$ 变成 $t_{i}+d×k_{i}$ | ||
| + | |||
| + | 3.查询点 $t_{x}$ | ||
| + | |||
| + | 我们用矩阵维护两种操作 | ||
| + | |||
| + | 每个点的矩阵都设为 $[k\ t\ 1]$ ，末尾的 $1$ 的理由上面说过了 | ||
| + | |||
| + | 于是两种操作写一下就很显然能知道转移矩阵了。 | ||
| ===== 组合数 ===== | ===== 组合数 ===== | ||
2020-2021/teams/legal_string/王智彪/数理知识.1628585005.txt.gz · 最后更改: 2021/08/10 16:43 由 王智彪
