本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-25 22:06:25

题解思路：

我们有 $T$ 轮，只有最后一轮赢了才是赢了，所以前 $T - 1$ 轮，随便就可以了。

状态：

必胜态：上一轮一定要输

必败态：上一轮一定要赢

所以我们知道了 $i - 1$ 的状态，那么我们就可以求出第 $i$ 轮的状态。

那么我们只要维护一个赢得状态值和输的状态值就可以得到结果。

难点就在他们怎么计算：

------------$Win$ 数组分割线------------

$Win_{e,e} = 0$，因为 $e \ge 1$，所以不管 $e \times 2$ 或者 $e + 1$ 都是必败态。

那么我们就可以通过 $Win_{e,e}$ 求出 $Win_{e-1,e}$ 等。

若 $e$ 是奇数：

$Win_{e,e} = 0$

$Win_{e - 1, e} = 1$只能加一转换成必胜态

$Win_{e - 2 , e} = 0$因为他是一个奇数，而奇数只能转移到必胜态，因为两个奇数相加，得偶数；奇数加一，就相当于奇数加奇数。所以只会转移到必胜态，所以他就是必败态。 $$\dots$$ $$\dots$$ 以此类推

$s$ 与 $e$ 奇偶性相同时，就会走向一个必败态，否则就会走向一个必胜态。

若 $e$ 是偶数：

当 $s$ 是偶数，那么 $s \times 2$ 就是必败态，所以当 $\left \lfloor \frac{e}{4} \right \rfloor < s \le \left \lfloor \frac{e}{2} \right \rfloor$，$s \times 2$ 一定是必胜态。

当在 $\left \lfloor \frac{e}{4} \right \rfloor$ 这个点时，他一定是必败态，因为他乘二，就会到 $s$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$，所以一定必败。

那么我们就可以递归去判断： $dfs (s , \frac{e}{4})$。

因为 $\left \lfloor \frac{e}{4} \right \rfloor$ 乘二到这个区间，而比他小的一定超不过这个区间，所以若能到必胜态区间 $\left \lfloor \frac{e}{4} \right \rfloor - 1$ ~ $\left \lfloor \frac{e}{2} \right \rfloor$ 这个区间的数，必定是必败态，当我们可以转到 $\frac{e}{2}$ 就是必胜态。

这就是 $Win$ 数组的求法。

------------$Lost$ 数组分割线------------

也可以类似的分析一下：

$\left \lfloor \frac{e}{2} \right \rfloor < s \le e $ 时，他一定是必胜态，那么对于 $\frac{e}{2}$ 一定是必败态，这就很像我们分析 $Win$ 时 $e$ 是偶数的情况，我们就可以直接让他转移到 $Win$ 的情况就可以了。

这样，Win 和 Lost 数组就都求出来了。

虽然我们前面说过要到着来，但是我们正着来就行了，那么当我们这一轮为先手，那么 Win 和 Lost 只有一个为 $1$，那么它就不能改变结果，若 Win 和 Lost 都是 $1$ 那么想输想赢都可以，这样最后的就可以知道了。

注意：$1 \le s_i,e_i \le 10^{18}$，要开 long long！

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
bool dfs (ll s , ll e) {
	if (e & 1) {\/\/奇偶性是否相同 
		if (s & 1) return false;
		else return true;
	}
	if (s > e \/ 2) {
		if (s & 1) return true; 
		else return false;
	}
	if (s > e \/ 4) return true;\/\/当他大于e\/4时，和偶数为必胜态区间范围，所以返回true 
	return dfs (s , e >> 2);\/\/递归 
}
bool check (ll s , ll e) { 
	if (s > e \/ 2) return true;\/\/奇数里这个区间为必胜态
	return dfs (s , e >> 1);\/\/否则返回和Win的共同部分 
}
int main() {
	int n;
	cin >> n;
	bool cur = false , win , lose;
	for (int i = 0; i < n; ++ i) {
		ll s , e;
		cin >> s >> e;
		win = dfs (s , e);\/\/Win
		lose = check (s , e);\/\/Lost
		win ^= cur;\/\/和是否先手异或一下 
		lose ^= cur;
		if (win == lose) break;\/\/若Lost和Win一样 ，break 
		if (win) cur = 1;\/\/若这一局你赢了，那么下一局你先手 
		else cur = 0;\/\/否则就是后手 
	}
	cout << win << ' ' << lose << endl; 
	return 0;
}

码字不易，求赞！