luoguP4101 [HEOI2014]人人尽说江南好 结论

题目大意：

给定(n)堆初始大小为(1)的石堆

每次选择两堆石子合并，特别的，合并之后的两堆石子不能(> m)

询问先手必赢？

---

不妨设我们是先手，且最后我们必胜

我们考虑构造局面(m, m, m, m,m, ..., n;mod;m)

我们从左往右依次合并出这些(m)堆

如果对手帮我们在当前堆上合并(1)，那就是自寻死路

否则，如果另外的合并出了一个大小为(2)的堆

如果$m - $ 当前堆的大小 (ge 2)，那么我们把这个对手新合并出的堆合并到自己的堆上

否则，我们另取一个(1)合并到当前堆，然后直接取对手合并出的堆为新的需要合并的堆

所以，到达最终方案的步数是确定的，算出步数然后判断即可

（有些地方有些细微的差异，就自行讨论一下吧QAQ）

---

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

#define gc getchar
inline int read() {
	int p = 0, w = 1; char c = gc();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = gc(); }
	while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
	return p * w;
}

int main() {
	int T = read();
	while(T --) {
		int n = read(), m = read();
		int t = n / m * (m - 1) + (n % m > 0) * (n % m - 1);
		printf("%d
", (t & 1) ? 0 : 1);
	}
	return 0;
}