感觉题解说的都很不清晰，这里只谈个人理解。
考虑操作的本质是什么，两人从低到高确定二进制下的每一位填的数，并且场上只保留对应后缀的数字，当场上没有数字时当前操作者输。
设 \(f[i,S]\) 表示确定了前 \(i\) 位，填的数为 \(S\)，接下来先手是否能赢，那么有 \(f[i, S] = \neg (f[i + 1, S] \land f[i + 1, S + 2^i])\)。特别的，当不存在数字时，\(f[i, S] = -1\)，且如果两个儿子中有一个为 \(-1\)，那么 \(f[i, S] = 1\)。
考虑枚举 \(i = 59...0\)，直觉告诉我们，\(f[i,\_]\) 的连续段数为 \(O(n)\)。
对于每个 \(i\)，我们显然可以将 \(f[i + 1, 0...2^i - 1]\) 和 \(f[i + 1, 2^i ... 2^{i + 1} - 1]\) 通过双指针的方式合并起来。考虑数学归纳法，若 \(i + 1\) 层连续段数为 \(O(n)\)，由双指针可得第 \(i\) 层连续段数也是 \(O(n)\)。
时间复杂度 \(O(n\log V)\)。
- 启示：不要认为极其暴力的 dp 不可行，世上有数百万种 dp 优化的方式。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pir pair <ll, ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn = 1e6 + 10, P = 60;
ll t, n, pos[maxn], val[maxn], m, _pos[maxn], _val[maxn], _m;
ll l[maxn], r[maxn];
int main() {
scanf("%lld", &t);
while(t--) {
scanf("%lld", &n); m = 0, r[0] = -1;
for(ll i = 1; i <= n; i++) {
scanf("%lld%lld", l + i, r + i);
if(l[i] > r[i - 1] + 1) {
pos[++m] = r[i - 1] + 1;
val[m] = -1;
}
pos[++m] = l[i];
val[m] = 1;
}
if(r[n] < (1ll << P) - 1)
pos[++m] = r[n] + 1, val[m] = -1;
for(ll i = P - 1; ~i; i--) {
ll x = 1, B = 1ll << i;
while(x <= m && pos[x] < B) ++x;
if(x > m || pos[x] > B) {
for(ll j = m; j >= x; j--)
pos[j + 1] = pos[j], val[j + 1] = val[j];
pos[x] = (1ll << i), val[x] = val[x - 1], ++m;
}
pos[m + 1] = (1ll << i + 1), _m = 0;
for(ll j = 1, k = x; j < x; j++) {
while(pos[k + 1] - B <= pos[j]) ++k;
while(pos[k] - B < pos[j + 1]) {
_pos[++_m] = max(pos[j], pos[k] - B);
if(min(val[j], val[k]) == -1) {
if(val[j] + val[k] == -2)
_val[_m] = -1;
else _val[_m] = 1;
} else {
_val[_m] = (val[j] & val[k]) ^ 1;
} ++k;
} if(k > x) --k;
}
for(ll i = 1; i <= _m; i++)
pos[i] = _pos[i], val[i] = _val[i];
m = _m;
} puts(val[1]? "Takahashi" : "Aoki");
}
return 0;
}