自动搬运

查看原文

来自洛谷，原作者为

	Expert_Dream **

搬运于2025-08-24 22:53:00，当前版本为作者最后更新于2023-12-09 22:01:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更好的阅读

这是一道找规律的题目。

因为我个人习惯，以下部分使用从 $1$ 开始的下标讲述。

首先我们以 $1$ 来说：发现在第 $x$ 行 $y$ 列的连通块是可以直接连到第 $1$ 列的，所以很容易可以得出 $1$ 到 $y$ 列的连通块数量是 $2^y-1$。

接着，我们考虑再后面的情况：

显然，通过观察会分为后面两种情况。一种是遇到了不一样的数字，那么就无法继续判断下去。如果是一样的话那么必定是增加 $2^{y-1}$ 个连通块，于是，我们就可以用一个循环，一直增加 $y$，不断更新着连通块的数量。

如果考虑 $0$ 的情况也是同理。这里不过多解释。

但是我们还是会发现：这样的时间复杂度肯定过不去。

但是出题人给了善良的条件：$n \le 10^{18}$。那么 $\log(n)$ 最多也就 $64$ 了，所以，我们在 $y$ 大于 $64$ 的时候特判掉即可。

于是优化到了 $O(q \log n)$。

上代码：link。

其中感谢 @tiger2008 在 求助贴 中告知需要特判。感谢好心人！

给个关注或一个赞呗！