[ARC151C] 01 Game

首先每一段之间独立，考虑 \(sg\) 函数。

然后归纳一下 \(sg\) 函数值。当相邻的两个 painting 有一个在边界上的时候 sg=len，两个都在边界是 sg=len mod 2，都不在就是只有相等的时候是 sg=1 否则是 sg=0。归纳证明即可。

const int N = 2e5 + 5;
LL n;
int m, x[N], y[N];
int sg(int len, int dif, int id) {int w = 0;if (!id&&id==m) w ^= (len&1);else if (!id||id==m) w ^= len;else if (!dif) w ^= 1;return w;
}void solve() {cin >> n >> m; x[0] = 0; x[m + 1] = n + 1;rep(i, 1, n) cin >> x[i] >> y[i]; int res = 0;rep(i, 0, m) res ^= sg(x[i + 1] - x[i] - 1, y[i] ^ y[i + 1], i);cout << (res? "Takahashi\n": "Aoki\n");
}