type
status
date
slug
summary
tags
category
icon
password
组合数学
求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。而是需要在计算分子的时候，不断除以分母。
这个代码不行：
这个代码可以：
集合和位运算结合
位运算「并行计算」
位运算
进制
转十进制
每个数位的加权和
转非十进制
对整数部分和小数部分分别转换
整数部分每次除以X直到变成0，反向遍历每次的余数
一开始的，不能整除的，余留的部分，说明是bits最末尾的残留
每一次整除都是提升权重
小数部分的转换方式是将十进制数的小数部分每次乘以X直到变成0，正序遍历每次的整数部分
每一次乘法都是提升权重
原码、反码和补码
正数是三个都一样
负数符号位都是不动的
两个方向都是 取反 + 1
反码的引入，解决了原码的减法运算结果错误的问题，但是仍然没有解决同时存在+0和−0的问题
位运算符
左移
注意溢出
将一个数左移k位，等价于将这个数乘以
当乘数不是2的整数次幂时，可以将乘数拆成若干项2的整数次幂之和
右移
向下取整
对于负数，(-50)>>2 == -13，而(-50)/4 ==12（向0取整或者舍弃小数点），是不等价的
位运算的性质
一个数是2的幂次，那就仅有一个bit是1
计算机内部天然用二进制、十六进制表示数值
m可以是任何数，比如这题的12345
数学
数学在算法中的常见应用有以下几点：
- 有些算法需要通过数学证明其正确性，例如贪心算法需要证明贪心策略可以得到最优解，动态规划算法使用最优子结构的性质，部分情况下也需要证明动态规划算法的正确性；
- 有些算法问题本身就是数学问题，例如概率、几何、数论、组合等问题；
- 博弈问题经常需要用到数学知识。
知识点列举：
- 幂运算；——快速幂
- 概率；——递归、推导公式、模拟
- 几何；——模拟
- 数论；——prime、最大公约数gcd（辗转相除）
- 组合数学；
- 博弈。
- URL:/article/06cd4dae-7ccf-4143-a1d2-d7a7ad8aa891
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!