CF2217F

公平组合游戏博弈论+DP

可以将问题转换为一个四堆的 Nim 游戏。

什么是 Nim 游戏？

Alice 可以决定两个堆的异或和 $X$ 为 $[1, x_{1} - 1]$ 的任意一个值。（最简单的构造方法是第一个堆是 0，第二个堆是 $X$，区间就是 $[1, x_{1}-X]$

设第二个堆随机的区间异或和为 $Z$，那么当 $X \oplus Z = 0$ 时，Alice 才会输（处于必败状态）。

最大化赢的概率等价于最小化输的概率。

那么我们需要知道对于一个固定的 $X$，有多少种可能的 $Z$ 满足 $X \oplus Z = 0$。

我们设第二段被分为两个堆 $(a, b)$，每一个 $(a, b)$ 对代表一个可能的区间，我们现在的问题就变成了，对于给定的 $X$，有多少对 $(a, b)$ 满足：$a \oplus b = X， a+b \leq x_{2}-1, a \geq 0, b \geq 0$

要满足的条件既包含异或又包含加法，考虑能否统一到二进制，这样就可以按位考虑了。

$a+b=a \oplus b + 2(a \& b)$

我们设 $Y=a + b$，则 $Y=X+2(a\& b)$ ，得到 $2(a\& b)=Y-X$

考虑对于固定的 $X$，每一个合法的 $Y$ 可以产生多少对 $(a, b)$。

目前的条件：

• $Y\leq x_{2}-1$
• $Y - X\geq 0$
• $Y-X$ 能被 2 整除
• $(a\oplus b)\&(a\& b)=0$

按位考虑，因为 $X=a\oplus b$，所以对于 $X=1$，$(a, b)$ 都有两种情况 $(0, 1), (1, 0)$；对于 $X=0$，那么 $a\&b=1$，此时 $(a, b)$ 要么是 $(1, 1)$，要么是 $(0, 0)$，而对于一个确定的 $Y$，$a\& b$ 也是确定的，所以该位只有一种情况。

因此，对于每一个合法的 $Y$，一共会产生 $2^{popcount(X)}$¹ 对 $(a, b)$。

那怎么计算有多少合法的 $Y$ 呢？

我们发现条件中有很多与 $a\& b$ 有关，类比 $X=a\oplus b$，我们设 $a\& b=K$，则 $Y=X+2K\leq x_{2}-1$，由于 $Y-X$ 能被二整除，所以 $K\leq \lfloor \dfrac{x_{2}-1-X}{2} \rfloor$，设 $K$ 的最大值 $\lfloor \dfrac{x_{2}-1-X}{2} \rfloor$ 为 $lim$，则现在要计算有多少合法的 K 满足：

• $0 \leq K \leq lim$
• $K\&X = 0$

使用贪心/数位 DP 即可在 $\log(lim)$ 时间内计算出合法的 K，对应每一个合法的 $Y$。

$lim$ 与 $x_{2}$ 线性相关，所以总时间复杂度为 $x_{1}\log(x_{2})$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 676767677;

ll dp[32];
ll D(int pos, bool limit, int maxn, int x) {
  if (pos == -1) return 1;
  if (!limit && dp[pos] != -1) return dp[pos];
  ll res = 0;
  int digit = (maxn >> pos & 1);
  if (limit && !digit)
    res = (res + D(pos - 1, true, maxn, x)) % MOD;
  else if ((x >> pos & 1) == 1)
    res = (res + D(pos - 1, limit && digit == 0, maxn, x)) % MOD;
  else
    res = (res + D(pos - 1, limit && digit == 0, maxn, x) +
           D(pos - 1, limit && digit == 1, maxn, x) % MOD) %
          MOD;
  return (limit ? res : dp[pos] = res);
}

void solve() {
  int x1, x2;
  cin >> x1 >> x2;
  array<ll, 2> ans{MOD, -1};
  for (int x = 0; x < x1; x++) {
    memset(dp, -1, sizeof(dp));
    if (x2 - 1 - x < 0) {
      ans[0] = 0;
      ans[1] = x;
      break;
    }
    int lim = (x2 - 1 - x) / 2;
    int idx = 0;
    while (lim >> idx) {
      idx++;
    }
    ll pab = (1 << __builtin_popcount(x)) % MOD;
    ll res = D(idx - 1, true, lim, x);
    res = (res * pab) % MOD;
    if (res < ans[0]) {
      ans[0] = res;
      ans[1] = x;
    }
  }
  cout << 1 << ' ' << x1 - ans[1] << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}