P6791 [SNOI2020] 取石子

题目描述

甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子，然后由甲先手，两人轮流从中取走石子：甲第一次取走的个数不能超过 $k$ ，接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败，另一方获胜。现在已知 $k$ ，请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。

输入格式

多组数据。

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行每行两个用空格隔开的整数 $k, N$ ，表示一组询问。

输出格式

输出 $T$ 行，按照输入顺序，每行一个整数表示答案。

输入输出样例 #1

输入 #1

输出 #1

1
2
3

2
3
4

说明/提示

样例说明

对于样例 $1$ ，当 $k = 1$ 时：

如果 $n = 1$ ，甲只能取走唯一一颗石子从而失败。
如果 $n = 2$ ，甲取走一颗石子，乙只能取走最后一颗石子，甲获胜。
如果 $n = 3$ ，甲只能取走一颗石子，乙再取走一颗石子，甲只能取走最后一颗石子从而失败。
如果 $n = 4$ ，甲只能取走一颗石子，乙再取走两颗石子，甲只能取走最后一颗石子从而失败。
如果 $n = 5$ ，甲只能取走一颗石子，乙只能取走一颗或两颗石子，甲总能再留给乙留下最后一颗石子从而获胜。

数据说明与提示

对于所有数据， $1 \leq T \leq 10^{5}, k, N \leq 10^{18}$ 。

对于 $10 %$ 的数据， $T, N \leq 500$ 。
对于另外 $20 %$ 的数据， $T, N \leq 10^{5}$ 。
对于另外 $20 %$ 的数据， $T \leq 3, N \leq 3 \times 10^{6}$ 。
对于另外 $20 %$ 的数据， $k = 1$ 。
对于余下 $30 %$ 的数据，无特殊限制。

题解

取到最后一颗石子的输，可以直接认为是取到倒数第二颗石子的获胜。

令 $f (i, j)$ 表示还剩 $i$ 颗石子，本次最多能取 $j$ 颗石子时是否是先手必胜。由策梅洛定理，

f (i, j) = ⋁_{k = 1}^{j} [f (i - k, 2 k) = 0]

容易发现，对于某一个特定的 $i$ ，必然有一个 $j_{0}$ ，使得对于所有的 $j \geq j_{0}$ 都有 $f (i, j) = 1$ 。

设 $J (i)$ 表示最小的 $j_{0}$ 使得 $f (i, j_{0}) = 1$ ，那么一定有 $J (i - J (i)) \geq 2 J (i)$ 。这一不等式的含义是，局面 $i$ 下取走 $j_{0}$ 个石子后，下一个局面 $i - j_{0}$ 必胜所需要取走的数目 $J (i - j_{0})$ 必然大于 $2 j_{0}$ ，否则 $(i, j_{0})$ 不是一个必胜局面。

容易发现，这个数列的生成方式与斐波那契数列有关。设 $F_{i}$ 表示斐波那契数列的第 $i$ 项， $J$ 的前 $F_{i}$ 项就是将前 $F_{i - 2}$ 项接在第 $F_{i - 1}$ 项后面，然后将第 $F_{i}$ 项替换成 $F_{i}$ 。换言之， $J (i)$ 等于 $i$ 在斐波那契进制下的 lowbit。

现在要求的答案是 $\sum_{i = 0}^{n - 1} [J (i) \leq k]$ ，因为 $J$ 内本质不同的数字个数只有 $O (\log n)$ 个，所以可以分别统计出现次数。

设 $s_{i, j}$ 表示前 $F_{i}$ 项中 $F_{j}$ 的出现次数，那么 $s_{i, j}$ 可以 $O (\log^{2} n)$ 预处理，之后用类似斐波那契进制的就可以 $O (\log n)$ 地回答询问了。使用简单的前缀和优化可达到 $O (\log^{2} n + T \log n)$ 的总复杂度。