打表：威佐夫博弈与 k 倍动态减法

威佐夫博弈

两堆石子，每次可以取 $(x,y)$ ，你需要保证 $x+y\ge 1$ 并且 $x:y=(1:1)/(1:0)/(0:1)$ 。

在二维平面上打出必胜必败表，使用直角坐标系的上下左右观念。

由于每个点从下、左、左下转移而来，反演之后可得若一个点是必败，则上、右、右上都是必胜。

从下往上考虑，显然每行下面的部分只能排除掉有限格，所以该行必定有必败态，也就是说每行恰有一个必败态。

考虑对必败 pair 进行打表，该数列是 $(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),\cdots$ 。

上、右保证了这个数列中不会出现相同的数，右上保证了差是互异的，由于第一个数是递增的，差也是递增的，所以令第 $i$ 个对的差是 $i$ ，第二个数不会冲突。

看上去两项和对编号之间都是渐进意义上的倍数关系，设第 $i$ 个对的首元素是 $\alpha i$ ，第二个元素是 $(\alpha+1)i$ 。

考虑列方程，设所有的次元素中有 $t$ 个 $\le \alpha i$ 的，再加上前面所有的首元素，则 $t+i=\alpha i$ ，又因为 $(\alpha+1)t=\alpha i$ ，可以解得 $\alpha=\frac{\sqrt 5-1}{2}$ ，验证了前几项发现答案就是 $\lfloor\alpha i\rfloor$ ，那越到后面肯定误差越小，所以这个就是答案。

另一种暴力刻画的方式是，每次我们把 $\le$ 最后一个次元素的未出现的元素们拿出来，它们肯定是主元素，这个段数是 $\log n$ 的，

扩展：HDU6869 Slime and Stones

新增可选项： $|x-y|\le k$ 。

这个扩展是简单的，上、右、右上大宽条。

每行仍有一个，只不过差每次排除了 $k+1$ 个。

简单的打表也可以得到，设第 $i$ 个对的首元素是 $\alpha i$ ，则次元素是 $(\alpha+k+1)i$ 。

列方程，设所有的次元素中有 $t$ 个 $\le \alpha i$ 的，再加上前面所有的首元素，则 $t+i=\alpha i$ ，又因为 $(\alpha+k+1)t=\alpha i$ ，可以解得 $\alpha=\frac{1-k+\sqrt{k^2+2k+5}}{2}$ 。

扩展2

新增可选项： $x:y=(p:1)/(1:p),p\in\mathbb N^+$ ，即每次排除掉所有的倍数点。

显然每行仍恰有一个，剩的不会推了。

k 倍动态减法 UVA1567

一堆石子，第一个人限制取 $\le q$ 个，此后每个人限制取 $\le km$ 个， $m$ 是上一个人取的数量，问是否先手必胜。

$n\le 10^8,k\le10^5$ 。

我们敏锐地注意到，本题的状态是 $i,j$ 表示剩 $i$ 个石子时能取 $\le j$ 个。

显然 $j$ 这一维有单调性，所以我们研究的东西进一步简化为 $f_i$ 表示最小的 $j$ 使得先手必胜。

手玩 $k=1$ 的情况，发现是 $f_i=\text{lowbit}(i)$ ，仔细想想就会证了，若先手能取到 $\text{lowbit}$ ，则后手一定取不到，而如果先手取不到则后手一定能取到。

我们窥见一个 $f$ 的转移式： $f_i=\min_{j,f_{n-j}>kj}j$ ，也就是它取完后手取不到。

对其打表，我们用 $i\to i-f_i$ ，对每个 $i$ 求出这条链，将其从左往右写出来。

例如 $k=2$ 时是： $1,2,3,3+1,5,5+1,5+2,8$ 。

我们发现，构造第 $i$ 个数列的方式，就是数列 $i-1$ 后面加上 $1$ ，然后从后往前合并满足 $a_i\le ka_{i+1}$ 的人。

对其类似 $k=1$ 的手玩，发现 $\text{lowbit}$ 的位置就是这个新进制下的 $\text{lowbit}$ 。

何以证明？若先手能取到 $\rm lowbit$ ，则由于 $a_i>ka_{i+1}$ ，后手取不到 $\rm lowbit$ ，而若先手取不到 $\rm lowbit$ ，势必要拆掉最后一个位置，而 $f$ 的定义式天然满足了拆掉之后前面没被拆掉的很大的 $f$ 仍然会卡住，也就是说这个链结构只有最后一项分裂成小项了。

所以后手一定能取到新的 $\rm lowbit$ 。

这个数列增长的不快，但数列中的“基本数”（ $k=1$ 是 $2^t$ ， $k=2$ 是斐波那契数列）是通过 $a_i=a_{i-1}+\min_{j,ka_j\ge a_{i-1}}a_j$ 构造出来的，显然是一个指数级增长。