自动搬运

查看原文

来自洛谷，原作者为

	__Watcher Never accept the world as it appears to be. Always dare to see it for what it could be.

搬运于2025-08-24 22:18:40，当前版本为作者最后更新于2020-06-28 09:39:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

借此题，总结数位 dp 模板。

在洛谷上打上 数位dp 的标签，这是两道蓝题之一，很适合小结。借助代码来理解吧。下面是所有核心代码。

int dfs(bool limit, bool lead, int pos, int cha) {
	if(pos==0) return cha>=30;
	if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
	int res=0;
	int up=limit?a[pos]:1;
	for(int i=0;i<=up;i++) {
		res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
	}
	if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
	return res;
}

变量说明：

$limit$：当前位能否取到最大值（此题中的 1，10 进制中就是能否取到 9）；

$lead$：当前位是否是前导 0；

$pos$：当前是从前向后的第 $pos$ 位。

$cha$：0 比 1 多多少。由于可能出现负数，统统加上了 30；

$vis(pos,cha),f(pos,cha)$：两个记忆化数组，记录没有限制且没有前导 0 时的情况是否搜索过，并记录搜索结果。

逐行解释：

if(pos==0) return cha>=30;
如果当前所有位搜索完毕，0 比 1 多（差值大于 0）返回 1，否则返回 0。

if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
如果当前没有特殊限制并且已经搜索过了，直接返回。

int up=limit?a[pos]:1;
当前位能去到的最大值。有限制那么就是原数中的 $pos$ 位，没有限制也只能取到 1.

res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
如果之前都有限制且这一位也顶上了位，那么 $limit$ 也是 1；如果之前都是前导 0 且这一位还是 0，那么这一位还是前导 0；位置就往下一位搜；计算新差值（前导 0 统统不算）。

if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
当前不是特殊情况，那么就记忆下来。

小说明：

复杂度如何保证？当 $limit$ 是 1 或者 $lead$ 是 1 的时候并没有记忆化，那么如何保证复杂度？为了让 $limit$ 是 1，每一位都得顶位，只有 $len$ 种情况；如果让 $lead$ 是 1，那么每一位都得是 1，也只有 $len$ 种情况。因此，只有极少数情况未被记忆化，复杂度保障在 $len^2$ 的水平。

提供代码，仅供参考：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {
	int x=0, f=1; char ch=' ';
	while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return x*f;
}
int a[50], len, f[50][65], vis[50][65];
int dfs(bool limit, bool lead, int pos, int cha) {
	if(pos==0) return cha>=30;
	if(!limit&&!lead&&vis[pos][cha]) return f[pos][cha];
	int res=0;
	int up=limit?a[pos]:1;
	for(int i=0;i<=up;i++) {
		res+=dfs(limit&(i==a[pos]), lead&(i==0), pos-1, cha+(i==0?(lead?0:1):-1));
	}
	if(!limit&&!lead) vis[pos][cha]=1, f[pos][cha]=res;
	return res;
}
int solve(int x) {
	len=0;
	while(x) {
		a[++len]=x%2;
		x/=2;
	}
	return dfs(1, 1, len, 30);
}
int main() {
	int l=read(), r=read();
	cout<<solve(r)-solve(l-1);
}