题目大意：
给你指定一个数f，并给你T组游戏，
每组有n堆石子，A,B两人轮流对石子进行操作，
每次你可以选择其中任意一堆数量不小于f的石子，平均分为m份（即保证最大的一堆和最小的一堆中石子数量之差不超过1）。
不能操作者负。
问先手是否有必胜策略。
思路：
考虑现在把一堆x个石子分为i堆。
为了使数量尽量平均，我们应该使分出来每堆的石子数量尽可能等于$lfloorfrac{x}{i}
floor$，
如果每一堆分到$lfloorfrac{x}{i}
floor$个石子，那么最后会多出$xmod i$个石子。
考虑把这些多出来的石子分别放在分出来的石子堆中，那么有$xmod i$堆会分到新的石子。
经过简单的计算，我们可以发现最后有$xmod i$堆分到了$lfloorfrac{x}{i}
floor+1$个石子，有$i-xmod i$堆分到了$lfloorfrac{x}{i}
floor$。
因为$sg(x)=mex{sg(y)|y$是$x$的后继状态$}$，又因为$y$只有两种，由于相同的数异或可以抵消，我们可以通过判断$xmod i$和$i-xmod i$的奇偶性来缩小运算规模。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<algorithm> 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int N=100000; 13 int sg[N],mex[N]; 14 int f; 15 int getsg(const int x) { 16 if(~sg[x]) return sg[x];//记忆化 17 if(x<f) return sg[x]=0;//当x<f时，不能再往下分，是P状态 18 sg[x]=0;//做标记，表示x这个状态已经被访问过 19 for(int i=2;i<=x;i=x/(x/i)+1) {//分为i堆，x/(x/i)+1表示分出来最小的堆仍然为(x/i)的最大能分的堆数 20 for(int j=i;j<=std::min(i+1,x);j++) {//实际上分i堆和i+1堆两种情况 21 int tmp=0; 22 if((x%j)&1) tmp^=getsg(x/j+1);//分出来x/j+1个石子//判断奇偶性，如果是偶数直接能消掉，是奇数就算一次 23 if((j-x%j)&1) tmp^=getsg(x/j);//分出来x/j个石子 24 mex[tmp]=x;//判断mex的时候直接比x就可以了，不需要每次memset 25 } 26 } 27 while(mex[sg[x]]==x) sg[x]++; 28 return sg[x]; 29 } 30 int main() { 31 register int T=getint(); 32 f=getint(); 33 memset(sg,-1,sizeof sg); 34 while(--T) { 35 int ans=0; 36 for(register int n=getint();n;n--) { 37 ans^=getsg(getint()); 38 } 39 printf(ans?"1 ":"0 "); 40 } 41 int ans=0; 42 for(register int n=getint();n;n--) { 43 ans^=getsg(getint()); 44 } 45 printf(ans?"1 ":"0 "); 46 return 0; 47 }