前言：

都大半年没在洛谷上提交过题解了。

SPOJ 上有双倍经验，题号为 SP7602。

我看题解区的大佬们都是打表的，但是感觉只讲了打表可以得 XXX，没有讲得很形象，这篇题解将生动讲述做法，从打表前的转移方程到打完表后的分析都会很具体。

正文：

Step 1：基本解法（打表找规律）

为了方便起见，我们不妨令 \(n \le m\)，显然交换 \(n,m\) 对答案无影响。

令 \(b_{i,j}\) 表示从第 \(i\) 行第 \(j\) 列出发，是胜还是败。如果胜，\(b_{i,j}=1\)，否则 \(b_{i,j}=0\)。

我们先不考虑越界的问题，如果 \(b_{i+1,j},b_{i,j+1},b_{i+k,j+k}\) 中至少有一个为零（具体意义就是，从第 \(i\) 行第 \(j\) 列出发可以走到一个对手会败的位置），那么 \(b_{i,j}=1\)，否则 \(b_{i,j}=0\)。

也就是说，\(b_{i,j}=\lnot(b_{i+1,j} \bigwedge b_{i,j+1} \bigwedge b_{i+k,j+k})\)。

状态转移时，如果越界的话，那么那个越界的值就不参与运算，所以为了方便起见，可以设它为 1.

附上打表程序

为了直观，我先搞一张表来给大家解释：

0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

我们发现整个图被红色标记的反 L 形给切割成若干段，每段里面都是 0，1 交替的矩阵，特殊的就是这几个反 L 形，全是 1。

由于我们要求的是 \(b_{1,1}\) 的值，所以只需考虑起始点是否在反 L 形里。

如果在就需要特判，这个反 L 形会浓缩成一个宽为 1 的矩形（因为它不可能向上延伸了），而每两个反 L 形间从行看，夹了 \(k\) 行，从列看，夹了 \(k\) 列。所以无论从行列看，都可以当作 \(k+1\) 行（或列）为一个周期，那么当且仅当 \(n\) 为 \(k+1\) 的倍数，起始点在反 L 形内，此时 \(b_{1,1}=1\)。

如果不在：我们观察一下上表中蓝色标记的数，也就是每个反 L 形围成的矩形的右下角，以及整个图形的右下角。注意到了吗，它们是 0,1 交替的，所以我们可以通过反 L 形的个数，判断最里层矩阵右下角位于哪一行（记为第 \(x\) 行）和哪一列（记为第 \(y\) 列），以及它对应的数（记为 \(z\)）。考虑从起始点走到该点需要走 \(x+y-2\) 步（因为是最里层的矩形，向右下角走就走出该矩形了，不能到达该矩阵右下角），所以我们只需判断 \(x+y-2\) 的奇偶性，就能知道 \(b_{1,1}\) 是否与 \(z\) 相同。

那么现在这题就做完了，提交一下——我们发现在第 13 个点寄掉了，这是什么原因呢？

考虑一下 \(k=1\) 的时候，每个蓝色标记的位置无伦选用三种走法的哪一种，都会走到 1 的位置，此时每个蓝色标记的数就都为 0，这个需要特判。

现在是真的做完了。

Step 2：Code

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar(x%10+48);
}
ll T,n,m,K,sx,s,sy;
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    T=read(),K=read();
    while(T--){
        bool w;
        n=read(),m=read();
        if(n>m)swap(n,m);
        s=n/(K+1),sx=n-s*(K+1),sy=m-s*(K+1);//s代表“1围成的反L形”的个数
        if(sx==0)w=1;
        else{
            if(K==1)w=0;//特判
            else w=s&1;
            if((sx+sy)&1)w^=1;
        }
        printf(w?"+\n":"-\n");
    }
    return 0;
}