自动搬运

查看原文

来自洛谷，原作者为

	Saliеri 镜影倒倾，错的人陪着错的你

搬运于2025-08-24 22:24:02，当前版本为作者最后更新于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{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;
}