ImOlivia_uu!

博弈论的代码是这样的，别的算法只要考虑码力和思维，而博弈论要考虑的就多了

洛谷

---

思路

n堆石子，每堆数量不超过m

当n<=m，n为偶数先手赢，否则后手

当n>m，与上述同理，所以两方都希望最终合并次数变成奇数/偶数，假如现在轮到先手操作，先手还没动，这个时候最长合并次数为偶数次，那么先手有两种可能性，把后面一个堆丢进大堆里面，这样后手再丢一个小堆进去，或者把后面两个堆合成一个，无论怎么做，后手都能保证每轮完了之后，大堆的石子会增加两个，那么合并次数也会-2，一直保持为偶数，而这种方式使得合并次数最多。

那么先手一定会把小堆合并到一个大堆里，直到这一堆变成m个，所以最后的结果就会变成若干堆m个石子和一堆n%m个石子，总共要合并 $(n/m)*(m-1)+(n\%m?(n\%m-1):0)$ 次，再判断是否为偶数

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int t,n,m;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		ll ans=(n/m)*(m-1)+(n%m!=0)*(n%m-1);
		cout<<(ans&1?0:1)<<"\n";
	}

	return 0;
}

---

Very good Game Theory…