CF2157I

xujindong_ · 2025-11-25 15:46:14 · 题解

首先对偶数的 m，可以用巴什博弈的策略，(m+1)\mid n 时必败。下面假设 m 是奇数。

我们计算每个状态 (n,ban) 是必胜态或必败态，ban 为上一次取的数量。注意到对于一个 n，要么总是必败态，要么只有不超过一个 ban 是必败的。从前往后考虑，遇到一个必败的 n，则 n+ban(1\leq ban\leq m) 只有 (n+ban,ban) 可能失败。遇到一个必败的 (n,ban)，则 n+ban 只有 (n+ban,ban) 可能失败。

考虑一个必败的 n 会造成什么影响。首先对 n+1\leq n'\leq n+m，只有 (n',n'-n) 可能失败。对于 n+m+1，要赢必须跳到 (n+\frac{m+1}2,\frac{m+1}2)，否则对方可以跳到 n，因此 (n+m+1,\frac{m+1}2) 必败。若 n+m+1 不是全部必败，可推出 n+m+2 全部必败，因为跳到 n+m+1 或 [n+1,n+m] 都输。

我们考虑求出每个 m 的所有必败的 n，因为相邻两个必败的 n 距离 m+1 或 m+2，数量是 O(m\log m) 的。

设上一个必败的 n 是 n_i，尝试对 n_i+m+1 找一个必胜策略。令 f(n) 表示 n 不能走到上一个必败的 n_i 还能不能赢，有三种办法：走到 \frac{n+n_i}2、走到 \frac{n+n_{i-1}}2、走到 n_i-1，其中第三种因为 n_i-1 必败可能是 n_i-n_{i-1}=m+1 时 (n_i-1,m)，或 n_i-n_{i-1}=m+2。前者被第二种情况覆盖，后者因为 n_{i-1}-m+1 不必败，只有 (n_i-1,\frac{m+1}2) 必败，因此可 O(1) 判断。直接递归即可。

这个递归次数是难以计算的，10^6 时最大递归次数是 1339 次，但平均递归次数约为 5.187，因为两次递归发生的概率不高，而且也是比较随机的，可以通过。

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
vector<int>p[1000005];
bool calc(int n,int m,int pos){
  return n<m||(~(n-p[m][pos])&1&&!calc((n+p[m][pos])/2,m,pos))||(pos&&((p[m][pos]==p[m][pos-1]+m+2&&n-p[m][pos]==(m-1)/2)||(~(n-p[m][pos-1])&1&&n-p[m][pos-1]<=2*m&&!calc((n+p[m][pos-1])/2,m,pos-1))));
}
int main(){
  for(int i=3;i<=1000000;i+=2){
    p[i].push_back(0);
    while(p[i].back()<=1000000)p[i].push_back(p[i].back()+i+1+calc(p[i].back()+i+1,i,p[i].size()-1));
  }
  cin>>t;
  while(t--)cin>>n>>m,puts((m&1?!binary_search(p[m].begin(),p[m].end(),n):n%(m+1))?"Yes":"No");
  return 0;
}