第六章 基础算法

位运算

快速幂和取余运算
快速幂

递推与递归

费解的开关

每盏灯只能按一次，按灯顺序无影响
思路1：从正确结果逆推所有的状态，大概是2$^{32}$中状态
思路2：每一层状态确定后只能由下一行灯的状态的改变所影响，因此只要第一行灯的状态确定后，枚举最后一行灯的状态即可知道是否正确

前缀和与差分

增减序列

a[1], a[2], a[3] … a[n]
b[1], b[2], b[3] … b[n]
b 是 a 的差分，a 是 b 的前缀和
题目等同于
1 将 b[2] … b[n] 变成 0
2 b[1] 有多少种取值可能
操作一个区间的数等同于操作两个差分数组中的元素
1 2 <=i, j <= n 优先操作
2 i = 1, 2 <= j <= n
3 2 <= i <= n, j = n + 1
4 i = 1, j = n + 1 无意义
b[2], b[3] .. b[n]的正数总和为 p，负数总和的绝对值 q
1 min(p, q) + | p - q| == max(p, q)
2 |p - q| + 1