Skip to main content

数位 DP

Summary

数位 DP（Digit DP）统计某区间内满足特定数位约束的整数个数，通常把对 l 到 r 的统计转化为 f(r) 减 f(l-1)，其中 f(x) 数出 0 到 x 内的合法数。做法是从高位到低位逐位填数，用 lim 标记当前位是否顶到上界、lead 标记是否仍在前导零阶段，其余状态记录影响后续决策的信息；当不受上界约束且已脱离前导零时状态可复用，配合记忆化搜索缓存结果。以不含数字 4 且不含连续子串 62 为例给出记忆化搜索实现。

参考资料​

简介​

数位 DP（Digit DP）用于统计区间 [l,r][l,r] 内满足某种数位约束的整数个数。将问题转化为 f(r)−f(l−1)f(r)-f(l-1)，其中 f(x)f(x) 为 [0,x][0,x] 内满足条件的数的个数。

从高位到低位逐位填数，用布尔参数 lim\mathrm{lim} 表示当前位是否受上界约束、lead\mathrm{lead} 表示是否仍处于前导零状态，其余状态用来记录影响后续决策的信息（如上一位数字、数位和模余数等）。当 lim=0\mathrm{lim}=0 且 lead=0\mathrm{lead}=0 时状态可复用，使用记忆化搜索缓存结果，时间复杂度为 O(log⁡x⋅状态数)O(\log x\cdot\text{状态数})。

以「不含数字 4 且不含连续子串 62」为例：状态为当前位 pos\mathrm{pos}、上一位是否为 6（pre6\mathrm{pre6}），转移时跳过不合法数字并更新状态。

实现​

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

using ll=long long;
int a[15],tot;
ll f[15][2];
ll dfs(int pos,int pre6,bool lim,bool lead)
{
	if(pos==0)return 1;
	if(!lim&&!lead&&f[pos][pre6]!=-1)return f[pos][pre6];
	int up=lim?a[pos]:9;
	ll res=0;
	for(int d=0;d<=up;d++)
	{
		if(d==4)continue;
		if(pre6&&d==2)continue;
		res+=dfs(pos-1,d==6,lim&&d==up,lead&&d==0);
	}
	if(!lim&&!lead)f[pos][pre6]=res;
	return res;
}
ll solve(ll x)
{
	tot=0;
	while(x){a[++tot]=x%10;x/=10;}
	memset(f,-1,sizeof f);
	return dfs(tot,0,1,1)-1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1)<<'\n';
	return 0;
}

例题​

洛谷 P2602 [ZJOI2010] 数字计数

给定两个正整数 aa 和 bb，求在 [a,b][a,b] 中的所有整数中，每个数码(digit)各出现了多少次。