HDU 3032 Nim or not Nim? （博弈之求SG函数） - c++编程基础

题意：经典Nim博弈游戏变换，给你n堆石子pi，每堆有pi个石子，

Alice和Bob轮流取石子，每次可以从任意一堆中拿走任意个石子，也可以将某一堆石子分成两个小堆

（每堆石子个数必须不能为0），先拿完者获胜

思路：求SG函数后找规律；

SG函数定义及求法：点击打开链接

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include 
         
           #include 
          
            #include
           
             #include
            
              using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 1000001 #define PI acos(-1.0) int sg[maxn],vis[maxn]; void SG() { sg[0]=0; sg[1]=1; for(int i=2;i<100;i++) { memset(vis,0,sizeof(vis)); for(int j=i-1;j>=0;j--) { vis[sg[j]]=1; } for(int j=1;j