CF1733E

给定一个初始箭头全部指向右的网格图，每时刻在 \((0,0)\) 新增一个黏球，之后黏球按照箭头指示运动一格，并将其刚才所在的上一个格子的箭头变换方向。箭头只会指向右或者下，两个黏球如果移动到同一个格子便融合成一个新的球，多次询问 \(T\) 时刻 \((x,y)\) 有没有黏球存在

注意到每个士兵的坐标 \((x, y)\)，因为每次行动只会走到 \((x + 1, y)\) 或者 \((x, y + 1)\)，\(x + y\) 的值每次都会增长 \(1\)，那么对于棋盘上 \(x + y = k\) 这条线上一定只有一个分身，从而可以推出每个位置一定同时只存在一个分身

我们也可以用这个方法推断出 \(t\) 秒可能到达 \((x,y)\) 的分身只有可能在 \(t - x - y\) 秒在 \((0, 0)\) 出现，对于 hard version，\(t\) 非常大，但是我们发现对于一个格子，经过这个格子的分身中，有一半上取整去了右边，有一半下取整去了下面，而我们只关心在 \(t - x - y\) 秒出现的分身，我们可以让这个分身之前出现的分身去跑一遍这个棋盘，用上面的结论我们可以得出 \(100\times 100\) 区间内所有格子经过的分身数量，从而知道在 \(t - x - y\) 秒出现的分身开始行走时整个棋盘的状态，模拟一遍即可，复杂度 \(O(xy)\)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define int long long
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 1e3 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, f[N][N];

signed main() {
	int T = read();
	while (T--) {
		n = read(); int x = read(), y = read();
		if (n < x + y) {printf("NO\n"); continue;}
		f[0][0] = n - x - y;
		for (int i = 0; i < 120; i++) {
			for (int j = 0; j < 120; j++) {
				if (i == 0 && j == 0) continue; f[i][j] = 0;
				if (i) f[i][j] += f[i - 1][j] >> 1;
				if (j) f[i][j] += f[i][j - 1] + 1 >> 1;
			}
		}
		int goal = x + y, X = x, Y = y; x = 0; y = 0;
		while (x + y < goal) {
			if (f[x][y] % 2 == 0) y++; else x++;
		}
		printf(x == X && y == Y ? "YES\n" : "NO\n");
	}
	return 0;
}