自动搬运

查看原文

来自洛谷，原作者为

	Vix AFO

搬运于2025-08-24 22:20:42，当前版本为作者最后更新于2023-09-06 18:43:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

分析

看到题目的第一眼，发现这个人的走法比较鬼魅，但是我们考虑拆成一条条斜着走的路径。

对于当前 $n$ 行 $m$ 列的矩形，令 $n \le m$，我们发现第 $1 \sim n$ 条路径的长度递增，第 $n+1 \sim m$ 条路径的长度达到最大并且一直保持不变， 第 $m + 1 \sim n + m - 1$ 条路径的长度递减。记录路径的端点，并用差分数组维护，我们就可以快速找到每一行可以走到的最右边的数是多少。

现在需要快速得到，对于一个数 $x$，有多少在 $[0,y]$ 之间的数满足 $x\oplus y=x+y$。转化一下，我们发现只要 $x$ 和 $y$ 的二进制位上有至少一位都为 $1$，那么就不满足条件。我们求出不合法数的总和，答案就是 $k$ 减去不合法数。那么对于从高到低的第 $i$ 位，如果 $y$ 的第 $i$ 位是 $0$，跳过，找下一位。当前 $y$ 的第 $i$ 位是 $1$，我们假定这一位是 $0$，那么后面的位子就必须要有一个公共 $1$，简单计数。如果 $x$ 的第 $i$ 位也是 $1$，那么 $y$ 就可以不用找了，因为已经找到一个 $1$ 了，后面的数直接累加到答案里面。

具体实现可以看代码，总时间复杂度 $O(n \log^2 V)$，$V$ 是值域大小。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 10;
int n, m, d[N];
ll k, tot, step;

inline int pos(int x, int i) {
	return (x >> i - 1) & 1;//位运算找到 x 的第 i 位是 0 还是 1
}

inline int work(int x, int y) {//这里 x 和 y 是反着的
	int ans = 0;
	for (int i = 21; i; i--) {
		if (!pos(x, i)) continue;
		int cnt = 0;//记录 1 的个数
		for (int j = i - 1; j; j--) cnt += pos(y, j);
		ans += (1 << (i - 1 - cnt)) * ((1 << cnt) - 1);//0 的位子上随便选，1 的位子至少有一个 1
		if (!pos(y, i)) continue;
		for (int j = i - 1; j; j--)
			if (pos(x, j)) ans += 1 << (j - 1);
		ans++;//加上后面全部选 0 的
		return ans;
	}
	return ans;
}

int main() {
	cin >> n >> m >> k;
	int l, r, pos = 1;
	while (tot < k) {
		int cnt = (pos > n) + (pos > m);//判断路径的长度如何变化
		if (cnt == 0) step++;
		if (cnt == 2) step--;
		l = max(1, pos - m + 1);
		r = min(n, pos);//寻找端点
		step = min(step, k - tot);
		tot += step;//最多走 k 步
		if (pos & 1) d[r - step + 1]++, d[r + 1]--;
		else d[l]++, d[l + step - 1 + 1]--;//差分
		pos++;//奇偶性判断走的方向
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++, d[i] += d[i - 1])
		if (d[i]) ans += work(d[i] - 1, i - 1);//注意值域是从 0 开始的
	cout << k - ans;//总数减去不合法数
	return 0;
}