D. Unfair Game

时间限制：1 秒
内存限制：256 兆字节

问题描述

鲍勃厌倦了总是输给爱丽丝，为了确保不再输，他决定选择一个自己保证能赢的游戏。鲍勃从 $1$ 到 $n$ 中想了一个数字，已知 $n = 2^d$ ，其中 $d$ 是一个非负整数。最初，爱丽丝知道被选中的数字是奇数还是偶数。

在一轮操作中，爱丽丝可以将当前数字减 $1$ ，或者将其减半（只有当当前数字是偶数时才能减半）。只有爱丽丝可以进行操作。

每次操作后，爱丽丝会收到鲍勃的回复：要么是 $-1$ ，表示数字变成了 $0$ ，爱丽丝获胜；要么是一个非负整数 $x$ 。如果我们记当前数字为 $a$ ，那么 $x$ 必须同时满足以下条件：

$a$ 能被 $2^x$ 整除。
$a$ 不能被 $2^{x+1}$ 整除。

例如： - 如果 $a = 5$ ，则 $x = 0$ ，因为 $5$ 能被 $2^0 = 1$ 整除，但不能被 $2^1 = 2$ 整除。 - 如果 $a = 12$ ，则 $x = 2$ ，因为 $12$ 能被 $2^2 = 4$ 整除，但不能被 $2^3 = 8$ 整除。

可以证明，对于任意整数 $a > 0$ ，都存在唯一这样的 $x$ 。

鲍勃仍然担心爱丽丝会赢，所以他规定游戏最多进行 $k$ 轮。此外，鲍勃想最大化自己获胜的机会，所以他希望尽可能多地进行游戏。给定 $n$ 和 $k$ ，请计算从 $1$ 到 $n$ 中有多少个初始数字，使得爱丽丝即使采取最优策略，也无法在 $k$ 轮内获胜。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。

每个测试用例只有一行，包含 $2$ 个整数 $n$ 和 $k$ ( $1 \le n, k \le 10^9$ ) —— 分别表示所选数字的上限，以及爱丽丝最多能进行的轮数。保证 $n = 2^d$ 对某个非负整数 $d$ 成立。

输出格式

对于每个测试用例，输出在 $1$ 到 $n$ 中，爱丽丝即使采取最优策略也无法在 $k$ 轮内获胜的整数个数。

样例输入

样例输出

样例说明

第一个样例 n=4, k=1：初始数字为 $2$ , $3$ , $4$ 时是符合条件的，因为从 $a=1$ 只需 1 轮即可达到 $0$ （ $1 \rightarrow 0$ ），而对于其他值，至少需要 2 轮。
第二个样例 n=4, k=2：初始数字为 $3$ 和 $4$ 是符合条件的，因为对于 $a=2$ ，爱丽丝可以在 2 轮内获胜。
第三、四、五个样例 n=4, k=3,4,5：没有符合条件的 $a$ ，因为对于 $a=3$ 和 $a=4$ ，爱丽丝可以在 3 轮内获胜。
第六个样例 n=16, k=5：有 4 个符合条件的初始数字。
第七个样例 n=16, k=1：有 15 个符合条件的初始数字。

这是一个非常典型的从“模拟/暴力递推”转向“数学/组合计数”的问题。

核心思维突破

如果直接对 $1$ 到 $n$ 每个数字进行游戏模拟，时间复杂度是 $O(n \log n)$ （因为 $n$ 高达 $10^9$ ，这绝对会超时）。

我们需要找到一个 $O(1)$ 或 $O(\log n)$ 的方法直接计算出有多少个数字满足条件。这通常意味着要从二进制位的角度去寻找规律。

1. 爱丽丝的最优策略是什么？

爱丽丝的目标是让数字尽快变成 0。

根据游戏规则，她知道数字的奇偶性，也能通过反馈知道末尾有多少个 0。

如果是偶数：除以 2 总是优于减 1。因为减 1 会破坏二进制结构（把低位的 0 变成 1，增加操作次数），而除以 2 可以直接减少位宽。
如果是奇数：只能减 1。

基于此，我们可以推导出将一个数字 $x$ 变为 0 所需的最少步数 $Moves(x)$ 的公式。

设 $x$ 的二进制表示中，最高位（Most Significant Bit, MSB）在第 $i$ 位（即 $2^i \le x < 2^{i+1}$ ），且除去最高位后，剩余部分的二进制中 1 的个数为 $popcount(r)$ 。

公式为：

$Moves(x) = i + 1 + popcount(r)$

直观解释：

$i$ 代表我们需要做 $i$ 次“除以 2”的操作来把最高位移到最低位。
$1$ 代表最后把剩下的 1 减为 0 的操作。
$popcount(r)$ 代表中间遇到的每一个 1，都需要一次额外的“减 1”操作才能使其变成偶数从而继续除以 2。

2. 转化问题：组合计数

题目要求统计 $1 \le x \le n$ 中，满足 $Moves(x) > k$ 的个数。

这就变成了统计有多少个 $x$ ，其最高位位置与剩余位中1的个数之和超过某个阈值。

由于 $n = 2^d$ ，区间 $[1, n]$ 恰好涵盖了所有最高位为 $0, 1, \dots, d-1$ 的数字，以及数字 $n$ 本身。我们可以按照最高位 $i$ 进行分类讨论：

对于最高位为 $i$ 的所有数字（范围 $[2^i, 2^{i+1}-1]$ ）：

这部分数字的 $Moves(x) = i + 1 + popcount(r)$ 。
我们需要计算其中有多少个数字满足 $Moves(x) \le k$ ，即 $popcount(r) \le k - i - 1$ 。
这里 $r$ 是除去最高位后的余数，它可以是 $0$ 到 $2^i - 1$ 之间的任意整数。也就是说， $r$ 是一个 $i$ 位的二进制数。
问题转化为：在一个 $i$ 位的二进制数中，1 的个数不超过 $M$ 的方案数是多少？
这正是组合数学中的二项式系数求和： $\sum_{j=0}^{M} \binom{i}{j}$ 。

算法流程

预处理组合数 $\binom{n}{m}$ （杨辉三角），因为 $n$ 最大为 $10^9$ ，对应的二进制位数 $d \approx 30$ ，只需要预处理到 30 即可。
计算 $n$ 的幂次 $d$ （即 $\log_2 n$ ）。
初始化 alice_wins = 0。
遍历最高位 $i$ 从 $0$ 到 $d-1$ ：
- 计算允许的最大 1 的个数： $allowed\_ones = k - i - 1$ 。
- 如果 $allowed\_ones < 0$ ，这组里没有任何数字能让爱丽丝赢。
- 如果 $allowed\_ones \ge i$ ，这组里所有 $2^i$ 个数字爱丽丝都能赢。
- 否则，累加组合数 $\sum_{j=0}^{allowed\_ones} \binom{i}{j}$ 到 alice_wins。
单独检查数字 $n$ 本身：如果 $d + 1 \le k$ ，则 alice_wins++。
最终答案为 $n - alice\_wins$ 。

优化后的代码实现

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 预处理组合数，范围很小，到 32 足够了
long long C[35][35];

void precompute() {
    for (int i = 0; i <= 32; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
}

void solve() {
    long long n, k;
    cin >> n >> k;

    // 因为 n = 2^d，我们可以直接求出 d
    // __builtin_ctz对于求2的幂次的指数非常方便 (count trailing zeros)
    // 例如 __builtin_ctz(4) = 2, __builtin_ctz(16) = 4
    int d = 0;
    long long temp_n = n;
    while ((temp_n & 1) == 0) {
        temp_n >>= 1;
        d++;
    }

    long long alice_wins = 0;

    // 1. 遍历最高位 i 从 0 到 d-1 的所有数字
    // 这些数字的范围是 [2^i, 2^(i+1) - 1]
    for (int i = 0; i < d; i++) {
        // 公式：moves = i + 1 + popcount(r) <= k
        // 变换：popcount(r) <= k - i - 1
        long long max_ones = k - i - 1;

        if (max_ones < 0) {
            continue; // 哪怕 r 全是 0，步数也超过 k 了
        }

        if (max_ones >= i) {
            // 无论 r 怎么取，步数都在 k 以内
            alice_wins += (1LL << i);
        } else {
            // 累加组合数 C(i, 0) + ... + C(i, max_ones)
            for (int j = 0; j <= max_ones; j++) {
                alice_wins += C[i][j];
            }
        }
    }

    // 2. 单独检查 n 本身
    // n = 2^d，二进制只有最高位是 1，其余全 0
    // moves = d + 1 + 0
    if (d + 1 <= k) {
        alice_wins++;
    }

    // 题目问的是爱丽丝无法获胜（步数 > k）的个数
    cout << n - alice_wins << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度：对于每个测试用例，循环次数等于 $\log_2 n$ （约 30 次）。内部的组合数求和也最多 30 次。所以每个测试用例是 $O(\log^2 n)$ 甚至可以说是常数级的 $O(1)$ 。处理 $10^4$ 组数据绰绰有余。
空间复杂度：仅需 $35 \times 35$ 的数组存储组合数，空间占用极小。

总结

优化的关键在于不模拟游戏过程，而是发现游戏步数与二进制特征（最高位位置 + 1的个数）的数学关系，从而利用组合数批量计算满足条件的数字个数。

这是一份针对 CF 2184 D - Unfair Game 的算法复盘总结。这道题是从“博弈模拟”转向“数学规律”的经典案例。

算法笔记：CF 2184 D - Unfair Game

算法/数学/组合数学 #算法/位运算 #题目/Codeforces

1. 题目本质与转化

[!NOTE] 核心洞察

直接模拟游戏过程会超时 ( $N \le 10^9$ )。我们需要找到数字的二进制特征与游戏步数之间的直接关系。

最优策略：爱丽丝为了尽快归零，如果是偶数一定除以 2（减少位宽），奇数才减 1。
步数公式：

对于一个二进制最高位在第 $i$ 位的数字（即 $2^i \le x < 2^{i+1}$ ），将其变为 0 的最小步数为：

$Moves(x) = (i + 1) + \text{popcount}(rest)$
- $i+1$ ：表示消除最高位需要的移位次数（包含最后变0的那一步）。
- $\text{popcount}(rest)$ ：除去最高位，剩下的每个 1 都需要一次额外的“减1”操作将其变为偶数。

2. 解题逻辑 (组合计数)

题目要求统计爱丽丝无法在 k 步内获胜（即 $Moves > k$ ）的数字个数。

因为 $n=2^d$ ，我们可以按最高位 (MSB) 对 $[1, n-1]$ 进行分组统计：

分组遍历：

遍历最高位 $i$ 从 $0$ 到 $d-1$ 。每组包含 $2^i$ 个数字。

这些数字除去最高位后，剩余部分可以是 $0$ 到 $2^i-1$ 的任意值（即 $i$ 位二进制数）。
设定阈值：

当前组的基础步数是 $i+1$ 。

若要爱丽丝赢，剩余部分的 1 的个数 $j$ 必须满足：

$i + 1 + j \le k \implies j \le k - i - 1$

令 need = k - i - 1（允许的最大 1 的个数）。
组合数求和 (鲍勃赢的情况)：

我们要找的是 $Moves > k$ ，也就是 $1$ 的个数 $j > need$ 。
- 若 need < 0：基础步数这就超了，整组 $2^i$ 个数鲍勃全赢。
- 若 need >= i：哪怕全是 1 爱丽丝也能赢，鲍勃赢 0 个。
- 否则：鲍勃赢的个数 = $\sum_{j=need+1}^{i} C(i, j)$ 。
特殊处理：

$n$ 本身 ( $2^d$ ) 单独判断。

3. 黄金代码模板

C++

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int C[50][50]; // 组合数表

void solve(){
    int n, k;
    cin >> n >> k;

    // 1. 计算 n 是 2 的多少次幂 (d)
    // 方法：n = 2^d，直接计算末尾 0 的个数
    int d = 0;
    int temp = n;
    while(temp > 1){
        temp >>= 1;
        d++;
    }

    int ans = 0; // 记录鲍勃赢的次数

    // 2. 遍历最高位 i (对应区间 [2^i, 2^(i+1)-1])
    for(int i = 0; i < d; i++){
        // 爱丽丝允许拥有的最大 1 的个数
        int allowed_ones = k - i - 1;

        if(allowed_ones < 0) {
            // 基础步数就超了，这一组所有数(2^i个)鲍勃都赢
            ans += (1LL << i);
        }
        else if(allowed_ones >= i) {
            // 就算全填满1步数也不够k，鲍勃这组赢不了，跳过
            continue;
        }
        else {
            // 统计 1 的个数超过 allowed_ones 的情况
            // 注意边界：一直加到 j=i (全为1的情况)
            for(int j = allowed_ones + 1; j <= i; j++){
                ans += C[i][j];
            }
        }
    }

    // 3. 单独检查 n 本身
    if(d + 1 > k) ans++;

    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 预处理杨辉三角
    for(int i=0; i<50; i++){
        C[i][0] = 1;
        for(int j=1; j<=i; j++){
            C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
    }

    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

4. 易错点/Debug清单

[!WARNING] 幂次 d 的计算

错误写法：while(n) { d++; n/=2; }

后果：对于 $n=4 (100_2)$ ，会算出 $d=3$ ，实际上应该是 $2$ 。这会导致外层循环多跑一轮。

正确写法：while(temp > 1) 或者使用 __builtin_ctz(n)。

[!WARNING] 组合数循环边界

错误写法：for (j = need + 1; j < i; j++)

后果：漏掉了 $j=i$ （即除去最高位后，剩下全是 1）的情况。

正确写法：j <= i。

[!TIP] 题目性质利用

题目保证 $n=2^d$ ，这大大简化了问题，使得每个最高位 $i < d$ 的区间 $[2^i, 2^{i+1}-1]$ 都是完整的，可以直接套用组合数公式，无需数位 DP。