关于二进制优化
多重背包问题
- 在多重背包问题中，将问题简化为01背包问题时，如果采用朴素解法，时间复杂度为O(n),后续中，利用二进制优化，将复杂度降成O(logn)
- 对于二进制优化，将一个很大的数拆分成若干个数，其中数的规律为1,2,4,8….，最后，不足的数填充即可。例如，数字10，将其拆分成1,2,4,3.四个包,对应的二进制为0000~1111，每个包有拿和不拿两种选择。
二进制优化和二分的关系(快速幂)
牵涉到的题目
372题超级次方
- 该题中同样用到了优化的思想，刚开始以为二进制优化和二分可以等同，但是并不然，该题的思路是，将一个数不断二分，二分的条件是,如果数为偶数，二分，如果数为奇数，数减一。
- 对于求解一个大数的幂，该思路可以可以将复杂度从O(n)降为O(logn),其中时间复杂度O(n)对应着朴素解法。
- 同样是优化，二进制优化是为了方便从0~n任何一个数之间进行选取。而二分(快速幂)则是为了将一个很大的指数迅速拆分成一个很小的数，从而降低乘法的次数。
- 其次，本题中的另外一思路为，先将一个很大的指数拆分成小于10的数，用的是高中数学，同底数幂运算和幂的乘方运算。
取模公式
- (a∗b)%MOD=((a%MOD)∗(b%MOD))%MOD
二分最关键的一步
找到区间上的二段性- 目前遇到的两种类型的二分题目，一种是已知连续区间，找未知的值(475),另一种是在非连续单调递增区间内找已知的值