题解【SNOI2020】取石子游戏

Saliеri · 2022-02-11 18:53:01 · 题解

~~为什么全是打表找规律啊，这不是经典模型吗/yiw~~

给一个更自然的数位 DP 做法，同时附上 Fibonacci Nim 的性质证明。

先不考虑第一手不能取超过 k 个的限制，日后再说。

然后通过 n:=n-1 去掉该死的 Anti 游戏。

因为本题的性质，如果在非 Anti 游戏中可以必胜的话，必然也可以故意空一个来让自己在 Anti 游戏中必胜。

于是问题变成了经典 Fibonacci Nim，存在结论： Fibonacci Nim 先手必败当且仅当石子个数是 Fibonacci 数。

补充：经典 Fibonacci Nim 中先手不能一次取完。

以下我们给出证明。（认为 fib_1 = 1,fib_2 = 2）。

引理一：fib_{i+1} < 2fib_i < fib_{i+2}。

引理二：\frac{4}{3}fib_{i} < fib_{i+1}。

证明：拆项即可，很容易；或者说你归纳法也没人管。

引理三：（齐肯多夫定理）任意正整数可以被拆分为若干个不连续的 Fibonacci 数之和。

证明：简单数学归纳法。（是真的很简单，把前十几个的拆分画出来就能看到怎么归纳了）

定理一：当石子个数是 Fibonacci 数时先手必败。

证明：数学归纳法。
- 奠基是容易的。
- 关于归纳：我们考虑将规模为 fib_n 的游戏拆分为两个规模为 fib_{n-1},fib_{n-2} 的子游戏。
  - Q1：怎么拆成子游戏？这不是一堆吗？A1：我们认为二玩家在这一堆中所取出的前 fib_{n-2} 颗石子是第一个子游戏，后者亦然。
  - Q2：那万一跨越子游戏怎么办？不就不合法了？A2：不会的，看证明。
  - 首先，先手不能第一次取 \ge fib_{n-2} 颗石子，否则根据引理一，后手直接取完。
    - 所以先手第一手不会离开第一个子游戏。
  - 根据归纳假设，后手一定可以赢得第一个子游戏，同时控制自己不去动第二个子游戏。
  - 先手现在又面临一个必败态，同时还有后手上一次操作给的数量限制，因此唯一的获胜希望就是一次将 fib_{n-1} 取完。
  - 然而这是不可能的，因为后手在第一个子游戏中最后一手必然不超过 \frac{2}{3}fib_{n-2}，根据引理二，先手这一次取不完。归纳完成。

定理二：当石子个数不是 Fibonacci 数的时候先手必胜。

证明：我们可以给出一个必胜策略。
根据引理三，假设当前石子个数为 n = \sum_{i}fib_{p_i},p_{i-1}+1<p_i。
先手第一次取 fib_{p_1} 颗，由引理一，后手不能一次取完 fib_{p_2}，于是在 fib_{p_2} 这个子游戏中也是先手胜。
以此类推，最终整个游戏一定也是先手胜。

现在预备知识应当是足够了。我们先加上第一次取 \le k 的个数限制：

发现这其实是好讨论的：即非 Fibonacci 数时，如果 fib_{p_1} > k 先手也必败。
原因：因为这样就取不完第一堆，从而留给后手一个必胜的局面；否则先手的必胜策略不受影响。
- Q：如果先手第一次取很小的数量来臭后手呢？A：自证不难/xyx

问题现在被转化成了这个样子：设 \text{lowbit(n)} 为 n 的齐肯多夫表示法下最小的 Fibonacci 项，则：

\text{ans} = \sum_{i=1}^n[k\ge\text{lowbit(i)}]

容斥变成 \text{lowbit} > k 的数量。

考虑 数位 DP。

然后发现这个玩意好做的不得了啊，直接记搜数位 DP 写就完了，一点难度都没有。

还是详细说一下：考虑低 i 位可以构成多少个数，后效性有是否顶满 n 与高一位上是否是 1（因为齐肯多夫表示法要求不连续），记下来就可以了。
同时要求 < k 的 Fib 位上不能有 1，那就在不满足条件时直接 return 1 就完了（因为底下只能填全 0）。

复杂度 O(T\log n)。

Code:

#include <cstdio>
#include <cstring>
typedef long long ll;
int T;bool v[105];
ll n,k,f[105],dp[105];
ll DP(int p,bool bound,bool lst){
    if(p < k)return 1;
    if(!lst&&!bound&&~dp[p])return dp[p];
    ll r = 0;
    r += DP(p-1,bound&(v[p]==0),0);
    if(!lst && (!bound || v[p] == 1))
        r += DP(p-1,bound,1);
    if(!lst&&!bound)dp[p] = r;
    return r;
}
int main(){
    scanf("%d",&T);
    f[1] = 1,f[2] = 2;
    for(int i=3;i<=90;++i)f[i] = f[i-1] + f[i-2];
    while(T--){
        scanf("%lld %lld",&k,&n),--n;
        ll tn = n;memset(v,0,sizeof(v));
        ll tk = k;for(int i=90;i;--i)if(f[i]>tk)k=i;
        for(int i=90;i;--i)if(tn>=f[i])tn-=f[i],v[i]=1;
        memset(dp,-1,sizeof(dp)),printf("%lld\n",n-DP(90,1,0)+1);
        //为什么 +1：因为上面的 dp 不可避免的会将 0 计入答案，需要去掉。
    }
    return 0;
}

题解 【SNOI2020】取石子游戏

题解【SNOI2020】取石子游戏