2019 USP-ICMC G. Left Stack Game

G. Left Stack Game

题目链接-Left Stack Game

题目大意
Tomaz和Danftito正在玩游戏，有三堆石头，每一堆石头分别是a，b和c。每回合，玩家必须从一堆石头中取出1到m块，但如果左边的任何一堆中都有石头，他们就不能清空一堆石头。移走最后一块石头的玩家获胜，托马兹先走，他们轮流比赛，假设两名球员选择最优策略，那么谁会赢得比赛

解题思路
SG定理
Nim 博弈：两个人玩游戏，有 n堆石子，每次操作可以选一堆石子拿，最少拿一颗，无子可取者为负。

• 因为a的左边没有石子堆，所以a没有限制，如果能达到状态 0 1 1即先手赢
• 可分为a b-1 c-1的三队巴什博弈 后根据SG定理取异或即可
• 所有石子个数异或起来如果为0，那么先手必败，如果不为0那么先手必胜
• 假如现在所有石子异或起来为J，我们用Ai表示第3堆石子个数，总共n堆。那么就有A1^ A2 ^ A3=j，我们把j二进制表示，则A中必有一个数最高位与j的最高位同为1（位数一样），然后我们令这个数是Am，所以Am ^ j必然小于Am，显然最高位被消掉变小了，我们可以取石子把Am变成Am ^ j，那么对于原式就是A1 ^ A2^ A3 ^ j=j ^ j=0；
• 如果异或起来为0，那么如果任意拿掉石子，新的异或一定不为0，所以当异或不为0的时候，都可以通过操作让它变成0

附上代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f;
const int N=1e5+5;
typedef long long ll;
typedef pair<int,int> PII;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	ll m,a,b,c;
	cin>>m>>a>>b>>c;
    m=m+1;
    a=(a)%m;
	b=(b-1)%m;
	c=(c-1)%m;
    if((a^b^c)) 
		puts("Tomaz");
    else 
		puts("Danftito");
	return 0;
}