差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/08 16:30]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/10 23:17] (当前版本)
王智彪
@@ 行 1: / 行 1: @@
 ====== 数理知识总结 ======
+===== 位运算 =====
+==== 判断一个数是不是 $2$ 的非负整数次幂 ====
+<code cpp>
+bool isPowerOfTwo(int n) {
+	return n>0&&(n&(n-1))==0;
+}
+</code>
+==== 对2的非负整数次幂取模 ====
+$mod$ 代表 $2^{k}$
+<code cpp>
+int modPowerOfTwo(int x,int mod) {
+	return x&(mod-1);
+}
+</code>
+==== 取绝对值 ====
+在某些机器上 效率比 $n>0?n:-n$ 高
+<code cpp>
+int Abs(int n) {
+	return (n^(n>>31))-(n>>31);
+}
+long long Abs(long long n) {
+	return (n^(n>>63))-(n>>63);
+}
+</code>
+==== 取两个数的最大/最小值 ====
+在某些机器上 效率比 $a>b?a:b$ 高
+如果 $a>=b,(a-b)>>31$ 为 $0$ ，否则为 $-1$
+<code cpp>
+int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }
+int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }
+</code>
+==== 模拟集合操作 ====
+差集是 $a\&(~b)$ 对称差是 $a$ ^ $b$
+==== 子集遍历 ====
+可以遍历一个数代表的集合中所有非空子集包括自己
+这个复杂度为 $O(2^{popcount(u)})$ 的复杂度遍历 $u$ 的子集
+进而可以在 $O(3^{n})$ 的时间复杂度内遍历大小为n的集合的每个子集的子集
+<code cpp>
+int n=13;
+for(int i=n;i;i=(i-1)&n){}
+//遍历子集的子集
+for(int i=n;i;i=(i-1)&n) {
+	for(int j=i;j;j=(j-1)&i) {}
+}
+</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$ 个操作都应用与这些点，操作种类有三种：
+.沿向量移动
+.按比例缩放坐标
+.绕某个坐标轴旋转
+这些操作都可以重复 $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$ 。
+有三种操作：
+.将 $x$ 到根的路径上所有点的 $k_{i}$ 变成 $k_{i}+d$
+.将 $x$ 到根的路径上所有点的 $t_{i}$ 变成 $t_{i}+d×k_{i}$
+.查询点 $t_{x}$
+我们用矩阵维护两种操作
+每个点的矩阵都设为 $[k\ t\ 1]$ ，末尾的 $1$ 的理由上面说过了
+于是两种操作写一下就很显然能知道转移矩阵了。
 ===== 组合数 =====
@@ 行 22: / 行 184: @@
 又比如 $\sum_{k≤m}c(r,k)(-1)^{k}=c(r,0)-c(r,1)+...+(-1)^{m}c(r,m)=\sum_{k≤m}c(k-r-1,k)=c(m-r,m)=(-1)^{m}c(r-1,m)$
+有意思的关系式： $\sum_{k≤m}c(m+r,k)x^{k}y^{m-k}=\sum_{k≤m}c(-r,k)(-x)^{k}(x+y)^{m-k},m$ 为整数，用数学归纳法可以证明，此处省略。
+令 $x=-1$ 并令 $y=1$ ，则有 $\sum_{k≤m}c(m+r,k)(-1)^{k}=c(-r,m)$
+令 $x=1$ 并令 $y=1,r=m+1$ ，则有 $\sum_{k≤m}c(2m+1,k)=\sum_{k≤m}c(m+k,k)2^{m-k}$
+又因为左侧是求了一半的组合数，所以是 $2^{2m+1-1}=2^{2m}$ ，所以这个式子等价于 $2^{m}=\sum_{k≤m}c(m+k,k)2^{-k}$
+$\sum_{k}c(l,m+k)c(s+k,n)(-1)^{k}=(-1)^{l+m}c(s-m,n-l)$ ，整数 $l≥0,m,n$ 为整数，数学归纳法，先拆后合可证，这里省略。
+$\sum_{k≤l}c(l-k,m)c(s,k-n)(-1)^{k}=(-1)^{l+m}c(s-m-1,l-m-n),$ 整数 $l,m,n≥0$
+$\sum_{-q≤k≤l}c(l-k,m)c(q+k,m)=c(l+q+1,m+n+1)$ ，整数 $m,n≥0,$ 整数 $l+q≥0$
+==== 例题 ====
+.求 ${\frac {\sum_{k=0}^{m}c(m,k)} c(n,k)}$ ，整数 $n≥m≥0$
+我们自然是希望统一分母，貌似没有选择，统一成 $c(n,m)$ 会好一些，又因为我们有 $c(n,m)c(m,k)=c(n,k)c(n-k,m-k)$ ，所以原式等于 ${\frac {\sum_{k=0}^{m}c(n-k,m-k)} {c(n,m)}}$ ，分子用 $t=m-k$ 换个元，再带公式，就知道是 $c(n+1,m)$ 和分母分别写成阶乘的形式，最后结果是 ${\frac {n+1} {n+1-m}}$
 ===== 斐波那契数列 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具