view in my blog

引入

[COCI2010-2011#4] HRPA

题意：一堆个数为 $n$ 的石子，两人轮流取石子，取走最后一块石子的胜。要求：

• 先手第一次可取任意多个石子

• 此外每次可取的石子的个数，至少为 $1$ ，至多为上一轮对方所取个数的 $2$ 倍。

求先手第一次取石子最少取多少可保证获胜。

思考

显然先手可以第一次直接取完获胜，但大多数情况下这么做并不是最少的。下面我们考虑第一次不取完的情况。

齐肯多夫（Zeckendorf）定理

Wikipedia 中对齐肯多夫定理的描述：

任何正整数都可以表示成若干个不连续的斐波那契数之和。

这种和式称为齐肯多夫表述法。

构造这种和式可以通过每次贪心选出最大的不超过它的斐波那契数。

证明：

• 若正整数 $n$ 为斐波那契数，得证。

• 否则

  • 先取 $Fib_{t_1}$，其中 $t1$ 满足 $Fib_{t_1} < n < Fib_{t_{1} + 1}$。

  • $n'=n - Fib_{t_1}$，同上一步取出一个 $Fib_{t_2}$ 满足 $Fib_{t_2} < n' < Fib_{t_{2} + 1}$。

  • 只要证 $t_1 ≠ t_2 + 1$。考虑反证法：

    • 假设 $t_1 = t_2 + 1$，则第一步取出的应当是 $t_1 + 1$ 而不是 $t_1$。原因是 $Fib_{t_1 + 1} = Fib_{t_1} + Fib_{t_1 - 1}$。

解题

引理 1

如果正整数 $n$ 为斐波那契数，则先手必败。

证明：

设 $n = Fib_{t}$，我们把 $n$ 看成 $Fib_{t-1}$ 和 $Fib_{t-2}$ 两堆。

• 若第一步取的个数超过 $Fib_{t-2}$，则后手可以直接取完剩余石子。

• 否则，该问题变成了一个 $n' = Fib_{t-2}$ 的规模更小的同样的问题。

考虑 $n = 2$ 的情况（即规模最小的情况），先手只能取 $1$，于是后手取 $1$ 获胜。

引理 2

如果正整数 $n$ 不为斐波那契数，则将其用齐肯多夫表示法表示后，最小的那一堆个数即为答案。

证明：

$n = f_1 + f_2 + ... + f_k$

先手取完最小的那一堆（即 $f_k$）后，根据齐肯多夫定理，$f_{k-1} > 2 \times f_k$，于是后手无法一次性取完次小的那一堆。再根据引理 1，次小的一堆的最后一块石子一定还是由先手取到，于是先手一定能取到最大的那一堆的最后一块，即整堆石子的最后一块。

CODE

signed main() {
    ll n=gin();
    while(1) {
        if(n==1) {puts("1"); break;}
        if(n==2) {puts("2"); break;}
        ll x=1,y=2,z=3;
        while(z<n) x=y,y=z,z=x+y;
        if(z==n) {printf("%lld\n",z); break;}
        else n-=y;
    }
    return 0;
}