題目

https://gmoj.net/senior/

題解

這算是我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;
}