CF-1072-D. Unfair Game（记忆化搜索就是要搜索所有可能要转移到这个状态的状态） · znzryb
## 题目大意
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 ](/2025/01/05/20250105-e78e5b35)
[HDU - 2089- 不要62](/2025/01/14/20250114-6b4320a2)
## 思路讲解
在题目要求下，一个数字要删多少次有规律吗？其实就是 $\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](https://codeforces.com/contest/2184/submission/357806886)
::: 源代码
```cpp
/**
* 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}$ 更为合适。