第五题 - MANY OPERATIONS 题目跳转：宏量运算。 一道位运算的恶心题目，跟上一题一样，可以用前缀和动态规划的思想来解决。因为每一位都是相互独立的，所以只需要按位进行 dp\mathtt{dp}dp 预处理就可以了。定义状态 dpi,j(0/1),kdp_{i, j(0/1), k}dpi,j(0/1),k 表示对于第 iii 位来说，一开始的值为 j(0/1)j(0/1)j(0/1)，经过前 kkk 次操作后这一位的值。而状态转移方程就是 dpi,j,k=dpi,j,k−1dp_{i, j, k} = dp_{i, j, k-1}dpi,j,k =dpi,j,k−1 。之后不断迭代就可以求出最后的解。 本题的主要难点是位运算的一些操作，有些同学对位运算的操作不太熟悉，这里提供一些常见的位运算操作： 1. 获取一个数字的第 jjj 位：(x >> j) & 1。 2. 判断数字是否是奇数：x & 1。 3. 将一个数字乘上 2j2^j2j：(1 << j) * x。 本题的时间复杂度约为 Θ(60N)\Theta(60N)Θ(60N)。 因此，本题的 AC 代码如下：

题目解析 对于位运算而言，每一「位」的计算结果都是 相互独立 的，而每次运算后的结果只有 000 和 111 两种可能的结果，所以我们可以单独考虑运算对每一位的影响。 * 令 oneione_ionei 为：前 iii 个运算对 XXX 中二进制位上的 111 产生影响后的结果。 * 令 zeroizero_izeroi 为：前 iii 个运算对 XXX 中二进制位上的 000 产生影响后的结果。 那么对于当前 XXX 施加前 iii 个运算的影响的结果，应为： * 将当前的 XXX 二进制位上的 111 转化为 oneione_ionei 对应二进制位上的状态，位运算操作为 (X and onei)(X\ \mathrm{and}\ one_i)(X and onei )； * 将当前 XXX 二进制位上的 000 转化为 zeroizero_izeroi 对应二进制位上的状态，位运算的操作为 ((X xor M) and zeroi)((X \ \mathrm{xor}\ M) \ \mathrm{and}\ zero_i)((X xor M) and zeroi )，其中 M=230−1M = 2^{30} - 1M=230−1（即有效二进制位上全为 111）； 如何维护 oneione_ionei 和 zeroizero_izeroi ？ 很简单，只需要在每次操作时，将对 XXX 执行的位运算作用到 oneione_ionei 和 zeroizero_izeroi 上即可。 每次位运算的时间复杂度为 O(1)\mathrm{O}(1)O(1)，总的时间复杂度为 O(N)\mathrm{O}(N)O(N)。 AC代码 C++ 代码： Python 代码：