P6791 [SNOI2020] 取石子 题解 / 齐肯多夫定理学习笔记

zrl123456 · 2025-10-24 16:35:51 · 题解

:::::info[题目基本信息] 考察：数学，博弈论，数位 DP（NOI/NOI+/CTSC）。
题目简介：

• 1\le N,K\le 10^{18}

时间限制：1s。
空间限制：180MB。
::::: 齐肯多夫定理相关博弈板子题，引入齐肯多夫定理：
:::::success[齐肯多夫定理讲解] 齐肯多夫定理：\forall n\in\mathbb Z_+,\exist k\in\mathbb Z_+,\exist\{id_k\} 满足：

::::success[证明] 考虑数学归纳法：
若 \exist p\in\mathbb Z_+,f_p=n，则显然成立。
否则，设 f_p<n<f_{p+1}，递归 n-f_p 的子问题，容易发现 f_{p-1}>n-f_p，所以不会取到相邻的斐波那契数，同时由于数一直在不断减小，所以最终一定能转化成第 1 种情况。
:::: ::::: 对于本题，容易发现先手全取完一定能赢，所以我们不妨钦定先手不能先取完。
对 n 分类讨论：

• 这时先手必败。 :::::success[证明] 设 $(n-i,2i)$ 为它的后继状态。
• 当 i\ge f_{p-2} 时，后手直接全取完就赢了。
• 在 n=1 时，先手都取不了，必败。
• 在 n=2 时，先手同样必败。
• 在 i<f_{p-2} 的其他情况时，归纳假设后手能在 f_{p-2} 的子问题获胜，然后递归到 f_{p-1} 的子问题，先手唯一希望是取完 f_{p-1}，但是不可能，因为后手最后一手取的不超过 \dfrac{2}{3}f_{p-2}，由于有定理： \frac{4}{3}f_{x}<f_{x+1}

  ::::success[证明]

  \frac{4}{3}f_x<f_{x+1}\\\Leftrightarrow\frac{4}{3}f_x<f_{x-1}+f_x\\\Leftrightarrow\frac{1}{3}f_x<f_{x-1}\\\Leftrightarrow\frac{1}{3}(f_{x-1}+f_{x-2})<f_{x-1}\\\Leftrightarrow\frac{1}{3}f_{x-2}<\frac{2}{3}f_{x-1}\\\Leftrightarrow f_{x-2}<2f_{x-1}

  显然成立。
  :::: :::::

• 对于其他情况，答案就为 f_{id_1}。 :::::success[证明] 先证明 [1,f_{id_1}) 的数不合法，这时 f_{id_1} 的子问题后手胜利，套用上面的结论，后面的数均为后手胜利，所以先手必败。 ::::: 这时我们直接枚举 $n$ 判断合法性会 TLE，考虑 Fib 位数位 DP。 设 $dp_{x,0/1,0/1}$ 表示考虑到第 $x$ 位，前面是否选了任何一个 $f_p$，同时上一位选没选。 转移是平凡的，在 $f_p$ 小于等于 $k$ 的时候后面直接全填 $0$ 就可以得出先手必败的数量（记得要判 $0$）。 然后容斥以下就行。 时间复杂度为 $\Theta(T\log n)$，空间复杂度为 $\Theta(\log n)$。

code