SG函数和SG定理

Fibonacci again and again

利用SG函数求出每一堆的SG值，如果三个值的异或和为零 先手必败态，否则，先手必胜态。

#include <bits/stdc++.h>
#define scanf_d(a) scanf("%d",&a)
#define scanf_dd(a,b) scanf("%d%d",&a,&b)
#define maxn 1000+10
#define N 20
//#define DEBUG
using namespace std;
int s[maxn],sg[maxn],fib[N];

void getsg( int n) {
    memset(sg,0,sizeof(sg));
    for ( int i = 1;i <= n; i++) {
        memset(s,0,sizeof(s));
        for ( int  j = 0; fib[j] <= i && j <= N; j++) s[sg[i-fib[j]]]=1;
        for ( int j = 0; ; j++) { if(!s[j]) { sg[i] = j; break; } }
    }
}

int main()
{
#ifdef DEBUG
    freopen("Text.txt","r",stdin);
#endif // DEBUG
    int n,m,k;
    fib[0] = fib[1] = 1;
    for( int i = 2; i <= 16; i++)   fib[i] = fib[i-1] + fib[i-2];
    getsg(1000);
    while(~scanf("%d%d%d",&n,&m,&k),m||n||k) {
        if(sg[n]^sg[m]^sg[k]) puts("Fibo");
        else puts("Nacci");
    }
    return 0;
}