EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

P6791 [SNOI2020] 取石子

题目描述

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

输入格式

多组数据。

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
3
1 5
2 5
1 10

输出 #1

1
2
3
2
3
4

说明/提示

样例说明

对于样例 $1$,当 $k=1$ 时:

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

数据说明与提示

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

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

题解

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

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

$$ f(i,j) = \bigvee_{k=1}^{j} [f(i-k,2k) = 0] $$

容易发现,对于某一个特定的 $i$,必然有一个 $j_0$,使得对于所有的 $j \ge j_0$ 都有 $f(i,j) = 1$。

设 $J(i)$ 表示最小的 $j_0$ 使得 $f(i,j_0) = 1$,那么一定有 $J(i - J(i)) \geq 2J(i)$。这一不等式的含义是,局面 $i$ 下取走 $j_0$ 个石子后,下一个局面 $i-j_0$ 必胜所需要取走的数目 $J(i-j_0)$ 必然大于 $2j_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)$ 的总复杂度。