Competitive ProgrammingGame TheoryDigit DP

CF2217F Interval Game

Nim + XOR 加法恆等式 + Digit DP

看起來像機率 + 區間問題，核心是把遊戲轉成 Nim，再做 XOR 分佈的 counting。

2026-04-08 · Problem Link

問題重述

Input：多組測資，每組給兩個整數 $x_1, x_2$ （ $1 \le x_1, x_2 \le 5 \times 10^5$ ）。

遊戲流程：

Alice 選一個區間 $[l_1, r_1] \subseteq [1, x_1]$
Bob 均勻隨機選一個區間 $[l_2, r_2] \subseteq [1, x_2]$
兩人用這兩個區間玩 Nim：每回合可以選一個區間，把 $l$ 縮小或把 $r$ 放大，不能動的人輸。Alice 先手。

Output：輸出 Alice 應該選的 $l_1, r_1$ ，使她的勝率最高。

觀察：這是 4 堆 Nim。堆的大小分別是 $l_1-1,\ x_1-r_1,\ l_2-1,\ x_2-r_2$ ，每堆代表這個方向還能擴展多少次。

Nim 的結論：先手贏 ⟺ 四堆 XOR ≠ 0。Alice 是先手，所以 XOR = 0 時 Alice 輸。

Alice 要選一組 $[l_1, r_1]$ ，讓 Bob 隨機選完之後，四堆 XOR = 0（Alice 輸）的機率盡量小。而 Bob 的可選範圍不受 Alice 的選擇影響，所以最小化機率等價於最小化滿足條件的組合數。

Step 1：轉成 XOR 問題

令：

a = l_1-1, \quad b = x_1-r_1 \quad(\text{Alice 控制})

c = l_2-1, \quad d = x_2-r_2 \quad(\text{Bob 隨機})

Alice 輸 ⟺ $a \oplus b \oplus c \oplus d = 0$ ⟺ $c \oplus d = a \oplus b$ 。

令 $s = a \oplus b$ ，Alice 的策略就是選一個 $s$ ，讓 Bob 滿足 $c \oplus d = s$ 的機率最小。

Step 2：定義 counting 問題

Bob 的合法範圍： $c \ge 0,\ d \ge 0,\ c + d \le x_2 - 1$ 。定義：

f(s) = \left|\{(c, d) : c + d \le x_2 - 1,\; c \oplus d = s\}\right|

Alice 要在 $s \in [0, x_1-1]$ 中找到 $f(s)$ 最小的那個。

Step 3：關鍵代數轉換

利用經典恆等式：

c + d = (c \oplus d) + 2 \cdot (c \mathbin{\&} d)

令 $t = c \mathbin{\&} d$ ，則 $c + d = s + 2t$ ，條件變成：

t \le \frac{x_2 - 1 - s}{2} \quad \text{且} \quad t \mathbin{\&} s = 0

把 $t$ 的上界記作 $M = \lfloor(x_2 - 1 - s) / 2\rfloor$ ，也就是在固定 $s$ 之後， $t$ 最大能取到多少。

第二個條件的原因：XOR 為 1 的 bit 代表 c 和 d 恰好一個是 1，AND 不可能同時也是 1。

每個 t 對應幾組 (c, d)？

固定 $t$ 和 $s$ 後，逐 bit 看：

$s$ 的 bit	$t$ 的 bit	$c, d$ 的選擇	方案數
1	0（必須）	(1,0) 或 (0,1)	2
0	0	(0,0)	1
0	1	(1,1)	1

$s$ 中有 $\text{popcount}(s)$ 個 1-bit，每個貢獻 2 種選擇，所以：

\text{每個 } t \text{ 對應的 } (c,d) \text{ 數} = 2^{\text{popcount}(s)}

cpp

// 對每個 s (= i):
int mx = (x2 - i - 1) / 2;  // M: t 的上界
long long sum = digit(i, mx) * (1LL << __builtin_popcount(i));

Step 4：Digit DP

現在需要數：只用 $s$ 的 0-bits 組成的數字中， $\le M$ 的有幾個：

g(s) = \left|\{t \ge 0 : t \mathbin{\&} s = 0,\; t \le M\}\right|

這就是標準的 Digit DP。從最高位到最低位掃：

遇到 $s$ 的 1-bit： $t$ 必須放 0。如果 $M$ 這位是 1， $t$ 已經比 $M$ 小了，後面的 free bits 全部自由 → 加上 $2^{\text{free\_below}}$ 。
遇到 $s$ 的 0-bit（free bit）： $t$ 可以放 0 或 1。如果還在 tight 且 $M$ 這位是 1 → 放 0 的分支不再 tight → 加上 $2^{\text{free\_below}}$ ，放 1 繼續 tight。

每個 $s$ 花 $O(20)$ 時間。

cpp

long long digit(int mask, int lim) {
    if (lim < 0) return 0;
    long long res = 0;
    bool flag = 1;
    for (int b = 19; b >= 0; b--) {
        bool m = (mask >> b) & 1;
        bool l = (lim >> b) & 1;
        if (flag && l) {
            int cnt = 0;
            for (int i = b - 1; i >= 0; i--)
                if (!((mask >> i) & 1)) cnt++;
            res += 1LL << cnt;
            if (m) flag = 0;
        }
    }
    if (flag) res++;
    return res;
}

Step 5：合併與枚舉

合併起來：

f(s) = 2^{\,\text{popcount}(s)} \cdot g(s)

遍歷所有 $s \in [0, x_1-1]$ ，取 $f(s)$ 最小的。構造 Alice 的區間：取 $a = s,\ b = 0$ ，也就是 $[l_1, r_1] = [s+1, x_1]$ 。

Special Case

如果 $x_1 > x_2$ ，可以選 $s \ge x_2$ 。此時 $c \oplus d \le c + d \le x_2 - 1 < s$ ， Bob 不可能匹配 → Alice 必勝。

cpp

if (x1 > x2) {
    cout << x2 + 1 << " " << x1 << "\n";
    return;
}

複雜度

O\!\left(\min(x_1, x_2) \cdot \log x_2\right)

完整 Code

cpp

#include <bits/stdc++.h>
using namespace std;

long long digit(int mask, int lim) {
    if (lim < 0) {
        return 0;
    }
    long long res = 0;
    bool flag = 1;
    for (int b = 19; b >= 0; b--) {
        bool m = (mask >> b) & 1;
        bool l = (lim >> b) & 1;
        if (flag && l) {
            int cnt = 0;
            for (int i = b - 1; i >= 0; i--) {
                if (!((mask >> i) & 1)) {
                    cnt++;
                }
            }
            res += 1LL << cnt;
            if (m) {
                flag = 0;
            }
        }
    }
    if (flag) {
        res++;
    }
    return res;
}

void solve() {
    int x1, x2;
    cin >> x1 >> x2;
    if (x1 > x2) {
        cout << x2 + 1 << " " << x1 << "\n";
        return;
    }
    int ans = 0;
    long long mn = 2e18;
    for (int i = 0; i < x1; i++) {
        long long sum = 0;
        if (i < x2) {
            int mx = (x2 - i - 1) / 2;
            sum = digit(i, mx) * (1LL << __builtin_popcount(i));
        }
        if (sum < mn) {
            mn = sum;
            ans = i;
            if (!sum) {
                break;
            }
        }
    }
    cout << ans + 1 << " " << x1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

解法 Flow

區間博弈 → 4 堆 Nim

↓

先手輸 ⟺

c \oplus d = s

，找

f(s)

最小的

s

↓

c + d = (c \oplus d) + 2(c \mathbin{\&} d)

，令

t = c \mathbin{\&} d

↓

數

t \le M

且

t \mathbin{\&} s = 0

→ Digit DP

↓

f(s) = 2^{\text{popcount}(s)} \cdot g(s)

，枚舉

s

取最小

CodeforcesNimXORDigit DPGame TheoryCompetitive Programming