Description

在一张 \(n\times m\) 的灰白图中，要求计算出前 \(k\) 步总共走过了多少灰色格子。

走法见上图右。

定义左上坐标为 \((0,0)\)，右下坐标为 \((n-1,m-1)\)。

对于坐标 \((x,y)\) 的格子，如果 \(x\& y=0\)，则涂灰色。

Solution

考虑按行枚举或按列枚举，下面将按列进行枚举（自左向右）。

对于枚举的某列 \(y\)，根据题意中的走法，可知存在一个最大的 \(x\)，使得对于所有 \(x'\in [0,x]\)，坐标 \((x',y)\) 一定曾被走过，且对于所有 \(x''\in[x+1,n]\)，坐标 \((x',y)\) 一定未被走过。

因此可以考虑前缀和 + 二分来求出这个最大的 \(x\)。

最后对于每一列 \(y\)，问题就只剩下求 \(0\sim x\) 中有多少个数 \(x'\) 满足 \(x'\& y=0\)了，位处理即可。

总时间复杂度 \(O(n\log n)\)。

前缀和

令 \(sum[i]\) 表示存在多少个格子 \((x,y)\) 满足 \(x+y\le i\)，根据边界尺寸分三部分转移处理这个前缀和数组。根据走法，\(x+y\) 较小的格子一定比 \(x+y\) 较大的格子先被走过。

二分

在二分时，对于指定的 \(y\)，二分 \(x_{mid}\)，需要求出 \((x_{mid},y)\) 这个格子是在第几步走到的，再跟 \(k\) 进行比较。

通过 \(sum[x_{mid}+y-1]\) 直接得出前面的步数，而对于和为 \(x_{mid}+y\) 的格子数量，先根据奇偶性判断是右上往左下走还是相反，再处理边界的影响即可。

位运算

给定 \(x,y\)，求 \(0\sim x\) 中有多少个数 \(x'\) 满足 \(x'\& y=0\)。

考虑将 \(y\) 分为多段长度为 \(2\) 的幂次段进行处理。例如 \((20)_{10}=(10110)_2\)，将其看成 \(00000\sim 01111, 10000\sim 10011,10100\sim 10110\) 三段，长度分别为 \(16,4,2\)。

从高位向低位枚举幂次 \(2^i\)，如果 \(x\) 的 \(2^i\) 位为 \(1\)， \(y\) 的 \(2^i\) 位为 \(0\)，则在后 \(i-1\) 位中，除了 \(y\) 内为 \(1\) 的对应位置需要为 \(0\) 外，其余位置任选，答案加上 \(2^{i-cnt_{y1}}\)。

特殊的，如果 \(x\) 的 \(2^i\) 位为 \(1\)，同时 \(y\) 的 \(2^i\) 位也为 \(1\)，先假设 \(2^i\) 为 \(0\)，如上述方法计入答案后，在其后的分段中该位置恒为 \(1\)，因此与运算必不为 \(0\)，此时直接退出循环即可。

// Template Ver.220227
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include