题解报告：hdu 2516 取石子游戏（斐波那契博弈）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2516
Problem Description
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
Output
先取者负输出"Second win". 先取者胜输出"First win".参看Sample Output.
Sample Input
2
13
10000
Sample Output
Second win
Second win
First win
解题思路：斐波那契博弈。斐波那契博弈模型，大致上是这样的：有一堆个数为 n 的石子，游戏双方轮流取石子，满足：
1. 先手不能在第一次把所有的石子取完；
2. 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，求必败态。
我们简单举几个栗子：
当n=2时，后手必赢；
当n=3时，后手必赢；
当n=4时，只要先手取1个，剩下3个，无论后手取多少个，先手必赢；
当n=5时，①若先手先取1个，剩下4个，此时后手掌握n=4这种局面，则后手必赢；②若先手取2个，根据规则，后手可以一次性取完剩下的3个，则后手必赢；所以先手无论怎么取，此时后手必赢。
当n=6时，先手只要取1个，先手就掌握了n=5这种局面，即先手必赢；
当n=7时，先手只要取2个，先手就掌握了n=5这种局面，即先手必赢；
当n=8时，①若先手取1个时，后手就掌握了n=7这种局面，即后手必赢；②若先手取2个时，后手就掌握了n=6这种局面，即后手必赢；③若先手取3个，根据规则，后手可以一次性取走剩下的5个，剩下的情况都是后手必赢；所以无论先手怎么取，此时后手必赢。
......
继续推导下去，我们可以发现，只要n满足斐波那契数列2，3，5，8，13......，则后手必赢，否则先手必赢。相关证明看这：斐波那契博弈
由于n在int范围内，且fib[45]刚好超过int范围，所以fib数组长度只需为44即可。
AC代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int n,fib[44]={2,3};bool flag;
6 for(int i=2;i<44;++i)//只需枚举44个fib数即可
7 fib[i]=fib[i-1]+fib[i-2];
8 while(cin>>n && n){
9 flag=false;
10 for(int i=0;i<44;++i)
11 if(fib[i]==n){flag=true;break;}
12 if(flag)cout<<"Second win"<<endl;//如果满足斐波那契数列，则后手必赢
13 else cout<<"First win"<<endl;//否则先手必赢
14 }
15 return 0;
16 }