【博弈论 && 斐波那契博弈】 HRPA

HRPA

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

分析：

这边我们先引入一个齐肯多夫（Zeckendorf）定理：

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

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

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

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

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