题目

https://gmoj.net/senior/#main/show/6823

题解

这算是我SG函数的入门题吧…… 不妨先考虑每一堆石子中的情况，设$f_i$表示操作前堆中有 i 个石子时，当前操作的玩家是否是取完这堆石子的那个玩家（记为0/1，0不是1是），或者他可以自由选择0或1状态（记为2）。 这样显然$f_b=0$， $$f_i=mex\{\begin{array}{ll}{f}_{i\cdot k}& ,i\le \lfloor \frac{b}{k}\rfloor \\ f_{i+1}& \end{array},1\le i<b$$ 通过打表找规律，可以发现$\left[\lfloor \frac{b}{k}\rfloor +1,b\right],\left[\lfloor \frac{\lfloor \frac{b}{k}\rfloor }{k}\rfloor +1,\lfloor \frac{b}{k}\rfloor \right],\cdots$这些区间中除前两个 f 外，其它 f 都是循环的，且循环节长度为2（即0 2 0 2 0 2 0 2……这样的）。 因此维护每个区间的前4位就好了，计算单个堆的时间复杂度为$O({\log }_{k}b)$，这个块的sg函数值为$f_a$。 接着如果$SG(1)⨁SG(2)⨁\cdots ⨁SG(n)=0$，那么Bob胜；否则Alice胜（SG定理）。 其实也可以换一种理解：

sg值为0的块不改变先后手，sg为1的块强制改变先后手，sg为2的块则是可以自由选择是否改变先后手。最后后手必胜。 可以把两人的操作视为两部分：第一部分是操作sg为0/1的块，第二部分是操作sg为2的块，前者的结果是固定的。现在的问题就变成了一开始有一个人必败，另一个人必胜，两个人每次可以改变或不改变胜利者，问最后谁必胜。 这其实就是谁的sg为2的块多，谁就赢；一样多就不改变胜利情况。由于Alice先选，她的sg为2的块绝对不会比Bob少，因此当sg为2的块的个数为奇数时，Alice必胜；为偶数时，等于忽略sg为2的块的子问题。

CODE

#include<cstdio> using namespace std; #define ll long long #define N 65 ll b,k,g[100005],arr[100005];int cnt,s; struct block{int num[4];ll front;}f[N]; inline int search(ll x) { for(int i=s;i;--i) if(x<=f[i].front) return i; } inline int calc_f1(ll y) { int s=search(y); if(y>f[s].front-4) return f[s].num[f[s].front-y]; return f[s].num[2+((y&1)^(f[s].front-2&1))]; } inline int calc(ll x) { if(x==arr[cnt]) return g[cnt]; arr[++cnt]=x; int f1=x<=b/k?calc_f1(x*k):2,f2; f2=arr[cnt-1]!=x+1?calc_f1(x+1):g[cnt-1]; if(f1&&f2) return g[cnt]=0; if(f1!=1&&f2!=1) return g[cnt]=1; return g[cnt]=2; } int main() { freopen("candy.in","r",stdin); freopen("candy.out","w",stdout); ll a,x;int id,t,n,ans; scanf("%d",&t); for(id=1;id<=t;++id) { scanf("%d",&n),ans=0; while(n--) { scanf("%lld%lld%lld",&a,&b,&k); s=1,cnt=0,f[1]=(block){0,1,0,0,b}; for(int i=2;i<4;++i) f[1].num[i]=calc(b-i); while(f[s].front/k+1>a&&f[s].front-3>a) { x=f[s].front/k,f[++s].front=x; for(int i=0;i<4;++i) f[s].num[i]=calc(x-i); } // for(int i=b-1;i>=a;--i) f[++s].front=i,f[s].num[0]=calc(i); ans^=calc_f1(a);//printf("%lld\t%lld\t%lld\t%d\n",a,b,k,calc_f1(a)); } puts(ans?"Alice":"Bob"); } return 0; }