CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » 王智彪 » 数理知识
2020-2021:teams:legal_string:王智彪:数理知识

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:legal_string:王智彪:数理知识 [2021/08/08 00:22]
王智彪 		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$ 个操作都应用与这些点，操作种类有三种： 
 + 
 +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$ 的理由上面说过了 
 + 
 +于是两种操作写一下就很显然能知道转移矩阵了。 
 + 
 +===== 组合数 ​=====
  
 从排成一排的 $n$ 个球里选出 $r$ 个球互不相邻的方案种数是 $c(n-r+1,​r)$ 。 从排成一排的 $n$ 个球里选出 $r$ 个球互不相邻的方案种数是 $c(n-r+1,​r)$ 。
行 16: 行 178:
  
 $c(n,​r)c(r,​k)=c(n,​k)c(n-k,​r-k)$ ，通过组合意义证明。 $c(n,​r)c(r,​k)=c(n,​k)c(n-k,​r-k)$ ，通过组合意义证明。
 +
 +上指标反转（其实在我这里变成了下指标反转）： $c(r,​k)=(-1)^{k}c(k-r-1,​k),​k$ 是整数，对于任意的整数 $n$ 都成立！！！ 所以对于“下指标”和 $(-1)$ 同时出现的，要提高警惕。 ​
 +
 +比如现在有 $(-1)^{m}c(-n-1,​m)=(-1)^{n}c(-m-1,​n)$ ，整数 $m,n≥0$ ，因为两边都等于 $c(m+n,m)$
 +
 +又比如 $\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$ ​
 +
 +==== 例题 ====
 +
 +1.求 ${\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}}$
  
 ===== 斐波那契数列 ===== ===== 斐波那契数列 =====
2020-2021/teams/legal_string/王智彪/数理知识.1628353354.txt.gz · 最后更改: 2021/08/08 00:22 由 王智彪

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3