思路:

好歹我也是做过一些博弈论的题,结果毫无思路.

因为不能分解成子游戏,所以SG函数直接废.

反正一切线索全部都指向一条唯一的道路--找规律!!(也许是构造?但我太弱)

然后有一个指数级的暴力打表:

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

int seq[31],lim;

bool Solve(){
	int num=0;register int i,j;
	for(i=1;i<=30;++i)num+=seq[i];
	if(num==1)return 0;
	int tseq[31];memcpy(tseq,seq,sizeof seq);
	for(i=1;i<=30;++i)for(j=i;j<=30;++j){
		memcpy(seq,tseq,sizeof tseq);
		if(i==j){
			if(seq[i]<2||2*i>lim)continue;
			seq[i]-=2,seq[2*i]++;
			if(!Solve())return 1;
		}
		else{
			if(!seq[i]||!seq[j]||i+j>lim)continue;
			--seq[i],--seq[j],++seq[i+j];
			if(!Solve())return 1;
		}
	}
	return 0;
}
int main(){
	register int i,j,k;
	for(i=1;i<=7;++i){
		for(j=1;j<=26;++j){
			memset(seq,0,sizeof seq),seq[1]=j;lim=i;
			if(Solve()==1)printf("lim=%d n=%d %d\n",i,j,j%i);
		}puts("");
	}
}

然后好像发现了什么.

然后就是AC程序.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
    int T;scanf("%d",&T);int n,lim;
    while(T--){
        scanf("%d%d",&n,&lim);
        if(lim==1)puts("1");
        else if(n==1)puts("1");
        else if(n<=lim){
            if(n&1)puts("1");else puts("0");
        }
        else if(lim==2){
            if(n%4==2||n%4==3)puts("0");else puts("1");
        }
        else{
            if(lim&1){
                if(n%lim!=0&&(n%lim)%2==0)puts("0");else puts("1");
            }
            else{
                int t=n%lim;
                if(t==0){
                    if((n/lim)&1)puts("0");else puts("1");
                }
                else if(t&1){
                    if(n%(2*lim)==lim+t)puts("0");else puts("1");
                }
                else{
                    if(n%(2*lim)==t)puts("0");else puts("1");
                }
            }
        }
    }
    return 0;
}