CF-1072-D. Unfair Game（记忆化搜索就是要搜索所有可能要转移到这个状态的状态）

题目大意

Bob 想了一个 1 到 n 之间的数字（n = 2^d）。Alice 初始知道这个数字是奇数还是偶数。

Alice 每回合可以选择：

• 将当前数字除以 2（仅当数字为偶数时）

• 将当前数字减 1

每次操作后，Bob 会告诉 Alice 一个非负整数 x，表示当前数字 a 能被 2^x 整除，但不能被 2^(x+1) 整除。如果数字变为 0，Alice 获胜。

游戏最多进行 k 回合。求有多少个初始数字（1 到 n）使得 Alice 在最优策略下无法在 k 回合内获胜。

ABC-387-C - Snake Numbers 

HDU - 2089- 不要62

思路讲解

在题目要求下，一个数字要删多少次有规律吗？其实就是 $\text{popcount}(x)+\lfloor\log_{2}(x)\rfloor$

然后问题就来到了这个怎么样快速统计了，这个是这道题目的难点。当然，显然我们应该使用这个数位 dp。

那么我们一般数位 dp 采用的是这个记忆化搜索，我们定义搜索递归函数为 $dfs(len,limit)$ ，$dp_{len,limit,val}$ 表示在 $len $ 长度下，$limit$ 受或不受 $n$ 高位限制的情况下，数字所需消耗次数为 $val$ 的数有几个。

然后我们来想一想，就是这个普通搜索，我们要知道 $dfs(len,limit)$ 的结果，进入到 $dfs(len,limit)$ 之后，我们需要搜什么？显然，我们需要搜索 $dfs(len-1,?)\cdots dfs(l,?)\cdots dfs(0,?)$，因为我们要搜索所有可能会转移到这个状态的状态。

从状态 $l\to len$，那么会增加多少消耗次数呢？$\Delta \gets len-l+1$（长度增加 $len-l$，还增加了一个 1）。

⚠️ 注意：从 0 转移过来的特殊情况，$\Delta \gets len-l$，如果你像我一样认为 0 的二进制长度为 1 的话（这个是因为，我们虽然认为 0 的二进制长度为 0，但是实际上我们的 $len$ 并没有增加 $len$ 的长度，只增加了 $len-1$ 的长度）。

那么前面讲的有点抽象，举个例子就是，$(1011)_{2}$ 就是从 $(11)_{2}$ 转移过来的，因为我们的状态设计是不包含前导 0 的。当然，如果 $(1011)_{2}$ 就是题目中的 n 的话（即表示二进制长度为 4 的上限限制），除了 $(11)_{2}$，还可以从 $(1)_2$，$(0)_2$ 转移过来，但是显然不能从 $(100)_2$ 等二进制长度为 3 的状态转移过来。

最后统计答案的时候，需要将这个 $dfs(len,1),dfs(len-1,0),\cdots,dfs(0,0)$ 的状态结果累和得到答案。

AC代码

AC
https://codeforces.com/contest/2184/submission/357806886

源代码

/**
 * Problem: D. Unfair Game
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/D
 * Created: 2026-01-14 11:06:00
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
template <class T>
constexpr int lg_bw(T x) {
#ifdef LOCAL
    static_assert(std::is_integral_v<T>, "__lg_bw requires integral type");
#endif
    using U = std::make_unsigned_t<T>;
    U u = static_cast<U>(x);

    // 和 g++ 的 __lg 一样：对 0 没有定义。可以选择 assert 或返回 -1
#ifdef LOCAL
    assert(u != 0);
#endif
    // if (u==0) {
    //     return -1;
    // }
    return static_cast<int>(std::bit_width(u)) - 1;
}

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector dp(35,vector(2,vector<ll>(75)));
    vector vis(35,vector<char>(2));
    bitset<35> bin(N);
    auto dfs=[&](auto && self,ll len,bool limit) {
        if (len==0) {
            dp[len][limit][0]=1;
            return;
        }
        if (vis[len][limit]) {
            return;
        }
        vis[len][limit]=true;
        if (limit) {
            int pos_encounter_1=-1;
            for (int l=len-1;l>=0;--l) {
                if (l==0 || bin[l-1]) {
                    pos_encounter_1=max(pos_encounter_1,l);
                }
                // 没有遇到过 1，就没有办法从这些状态转移过来
                if (pos_encounter_1==-1) {
                    continue;
                }
                ll diff=len+1-l;
                if (l==0) {
                    diff=len-l;
                }
                if (pos_encounter_1==l) {
                    // 是第一次遇到 1？那么还是受限制的
                    self(self,l,limit);
                    for (int val=diff;val<=70;++val) {
                        dp[len][limit][val]+=dp[l][limit][val-diff];
                    }
                }else {
                    // 可以从所有不是第一次遇到 1 的位置无条件转移
                    self(self,l,false);

                    for (int val=diff;val<=70;++val) {
                        dp[len][limit][val]+=dp[l][false][val-diff];
                    }
                }
            }
        }else {
            for (int l=len-1;l>=0;--l) {
                ll diff=len+1-l;
                if (l==0) {
                    diff=len-l;
                }
                self(self,l,false);
                for (int val=diff;val<=70;++val) {
                    dp[len][limit][val]+=dp[l][false][val-diff];
                }
            }
        }
    };
    dfs(dfs,lg_bw(N)+1,true);
    dfs(dfs,lg_bw(N),false);
    vector<ll> acc(75);
    for (int val=0;val<=70;++val) {
        for (int len=lg_bw(N);len>=0;--len) {
            acc[val]+=dp[len][false][val];
        }
        acc[val]+=dp[lg_bw(N)+1][true][val];
    }
    ll ans=0;
    for (int i=K+1;i<=70;++i) {
        ans+=acc[i];
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2184/submission/357806886

7
4 1
4 2
4 3
4 4
4 5
16 5
16 1

1
4 3

*/

心路历程（WA，TLE，MLE……）

向左短路 RE 了。

首先，不难发现，在题目要求下，我们只能够在二进制第一个 1 出现位置进行操作，把这个 1 后面出现的所有 0 全部消除。所以说，一个数字要删多少次有规律吗？

首先，不妨定义状态，$dp_i$ 指的是

当然，虽然知道了要使用数位 dp，如何实现也至少是需要想一想的。虽然说数位 dp 一般采用这个自顶向下的记忆化搜索设计方法，但是这道题目没什么限制条件，以计数为主，直接采用这个递推法即可。

$dp_{len,i}$ 表示在该（二进制）长度下，$val=i$ 的这个数字的数量。

$$dp_{len,i}\gets \sum_{l=0}^{len-1}dp_{l,i+1+len-l}$$

那么我们一般数位 dp 采用的是这个记忆化搜索，我们就先想搜索吧，搜索 $[0,n]$ 有几个数字的 $val>k$。当然这个有点奇怪，我们不妨假设我们是求的这个 $[0,n]$ 下，$val=i$ 的这个数字的数量，即 $dp_i$。

那我们要搜索这个东西，需要什么呢？$dfs(len,ismax)$ 可以吗？我们先试试，我们首先发现，只有 $dp_{i}$ 无法满足这个我们的要求，设置为 $dp_{len,i}$ 更为合适。