题意
把Nimm游戏的任意改成每次取的数量不超过当前的一半。
题解
暴力递推SG函数的话复杂度是
O
(
n
m
2
)
O(nm^2)
O(nm2)，n是堆数，m是堆的大小。稍微思考（实际上我是打表找规律发现的）可以发现，状态k和状态2k+1拥有相同的SG值，而偶数的SG值是它除以2。所以对于一个奇数，把他减1在除以2，一直到变为偶数，SG值就是这个偶数除以2。注意开始的几项不太一样，要特判。
AC代码
#include <bits/stdc++.h>
using namespace std
;
int n
;
int main()
{
int t
;scanf("%d",&t
);
for(int z
=1;z
<=t
;z
++){
scanf("%d",&n
);
int ans
=0;
for(int i
=1;i
<=n
;i
++){
int x
;scanf("%d",&x
);
int res
=0;
while(x
%2==1){
x
=(x
-1)/2;
if(x
==1){
res
=1;break;
}
}
if(x
==2){
res
=0;
}
else res
=x
/2;
ans
^=res
;
}
printf("Case %d: ",z
);
if(ans
!=0){
printf("Alice\n");
}
else printf("Bob\n");
}
return 0;
}
