HRPA


在这里插入图片描述

这道题就是一个斐波那契博弈的经典模型:
有一堆个数为n的石子,第一个人第一次不能全部取完,每次一个人取石子的个数都应当大于0,且小于等于上一个人取的石子个数的两倍。
问是否有先手必胜策略。
如果有,第一个人取的石子个数最少是多少?


分析:

这边我们先引入一个齐肯多夫(Zeckendorf)定理:

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

这个定理使我们分析这道题目的理论基础。

我们先抛出一个结论:
如果n恰好是斐波那契数,那么先手必败。
为什么呢?
由于n是斐波那契数,那么 n = f x + f x + 1 n=f_x+f_{x+1} n=fx+fx+1
先手的人不能直接取>= f x f_x fx个数的石子,因为这样后手就可以直接取完剩下的石子。
那么问题就变成了,先手有没有策略分别取完 f x f_x fx f x + 1 f_{x+1} fx+1个数的石子。
由于 f x f_x fx f x + 1 f_{x+1} fx+1都是斐波那契数列,因此问题产生了迭代。
边界情况是 x = 2 x=2 x=2,即 n = 2 n=2 n=2的情况。
这个时候,先手只能取1,因此后手胜利。

综上,如果n恰好是斐波那契数,那么后手必胜。

那么,如果n不是斐波那契数列呢?
根据齐肯多夫定理,n可以分解为若干个不连续的斐波那契数列之和:
n = f x 1 + f x 2 + f x 3 + … … n = f_{x1}+f_{x2}+f_{x3}+…… n=fx1+fx2+fx3+……
这里,f数组依次递增。
那么,这个时候,先手取完 f x 1 f_{x1} fx1之后,就可以必胜。
为什么呢?
首先,我们要知道, 2 ∗ f x 1 < f x 2 ( 1 ) 2*f_{x1}<f_{x2}(1) 2fx1<fx2(1),这也就是说,如果我们取了 f x 1 f_{x1} fx1,对方也没有办法直接取完 f x 2 f_{x2} fx2,这个时候对方也就落入了第一种情况的被动局面。
但是, ( 1 ) (1) (1)怎么证明呢?
我们利用反证法,假设 2 ∗ f x 1 > = f x 2 2*f_{x1}>=f_{x2} 2fx1>=fx2,那么这个时候 x 2 x_2 x2必然等于 x 1 + 1 x_1+1 x1+1,那么 f x 1 + f x 2 = f_{x1}+f_{x2}= fx1+fx2= f x 1 + f x 1 + 1 = f x 1 + 2 f_{x1}+f_{x1+1}=f_{x1+2} fx1+fx1+1=fx1+2,也就是说,这两个斐波那契数,可以用 f x 1 + 2 f_{x1+2} fx1+2代替,那么也就不会存在 f x 1 + f x 2 f_{x1}+f_{x2} fx1+fx2这种情况了。
因此,如果想要这种斐波那契分解存在,就必须满足 条件 ( 1 ) 条件(1) 条件(1)

那么这题的分析到这里就结束了。


#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5+100;
int n;
int f[N];
int nn;

signed main(){
	int x; cin>>x;
	f[0] = 1;
	f[++n] = 1; f[++n] = 1;
	for (int i = 3; i <= 1000; i++){
		if (f[n] > x) break;
		f[++n] = f[i-1]+f[i-2];
	}
	int now = n-1;
	while (x){
		while (f[now] > x) now--;
		x-=f[now];
		if (x == 0) cout<<f[now]<<endl;
	}
	return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部