题目传送门：Click。
某蒟蒻看见这道题，想了足足一个晚上，过后茅塞顿开，故作此篇。感谢神犇的题解。
看题目数据范围：\(1 \leq r,c \leq 10^6,1 \leq k \leq 10^{12}\)，显然打暴力 \(\mathcal{O}(rc)\) 的时间复杂度是行不通的。必须做到近似于 \(mathcal{O}(r)\) 的时间复杂度。
观察题目：题目中说：当 \(x+y=x \oplus y\) 时，这个格子是灰色的。而最后所求的答案就是走过的灰色的格子数，很容易想到斜着划分所有的格子，每一组的格子中的任意一个格子 \((x,y)\) 都满足 \(x+y=S\)，其中 \(S\) 是不变的。如下图：（图可能有点丑，仅做示意）
接下来，我们针对某个特定的 \(S\) 进行考虑。设有一组 \((x,y)\)，那么 \(x \oplus y=S\) 必然满足：\(S\) 二进制上的第 \(x\) 位为 \(1\)，则 \(x\) 与 \(y\) 的二进制第 \(x\) 位上必然不同；而当 \(S\) 二进制上的第 \(x\) 位为 \(0\)，那么 \(x\) 与 \(y\) 二进制第 \(x\) 位上必然相同。
再来考虑加法。首先看 \(S\) 二进制位的最后一个 \(1\)，发现它有两种情况，通过后两位进位，或是由 \(x,y\) 中一个 \(0\) 一个 \(1\) 相加而成。
当它是通过后两位进位而成时，则 \(x,y\) 该位上相同则无法满足异或；不同，则无法满足相加（因为有进位）。（见下图 1）
而它是由更前面的某一位 \(0\) 对应的 \(x,y\) 中的 \(1\)，也无法满足要求。（见下图 2）
综上，在 \(S\) 的每一位 \(0\) 上，\(x\) 与 \(y\) 同为 \(0\) ；否则，\(x,y\) 有且仅有一个 \(1\)。
标签：COCI2008,格子,leq,JEZ,题解,二进制,题目,进位 From： https://www.cnblogs.com/TimelessWelkinBlog/p/17642051.html