数位dp

• 数位dp
  • 简介
  • 题
    • 同类分布
    • \(\text{Balanced Number}\)

简介

数位 \(dp\) 是一种在数位上进行的 \(dp\)，通常用于解决值域 \([L,R]\) 中有几个数满足条件，且 \([L,R]\) 极大 (如 \(1\le L\le R\le 1e18\)) 的问题，这时我们就会在数位上进行 \(dp\)，问题规模变为 \(\lg R\) 的

数位 \(dp\) 就是一次考虑数的每一位，且从高到低枚举 (因为高位限制低位的取值范围)

我们通常用 \(lim\) 变量来表示更高的数位是否都与 \(R\) 的对应位相同

如：\(R=123\)，若前面两位取的 \(12\)，那第 \(3\) 位只能为 \(0\sim 3\)，若不是，则可以取 \(0\sim 9\)

我们通常使用记忆化搜索来实现数位 \(dp\)

数位 \(dp\) 模板：

inline ll dfs(int pos,int sum,int lim,...){
	if(!pos) {...}//数字填完了
	if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim];//记忆化
	int mx=lim?a[pos]:9;//当前位最大是多少
	ll res=0;
	for(int i=0;i<=mx;++i)
		res+=dfs(pos+1,sum+i,lim&(i==mx),...);//填数
    f[pos][sum][rm][lim]=res;//记忆化
	return res;
}

题

https://vjudge.net/contest/513260

同类分布

以这道题为例说明一下数位 \(dp\) 的常规解法

记搜的时候我们记录 \(4\) 个变量：

\(pos\)：当前搜到第几位

\(sum\)：各位数字之和

\(rm\)：原数对当前枚举的模数 \(mod\) 取模的结果

\(lim\)：前几位是否和原数相同

这题我们的思路是枚举模数 \(mod\)，然后通过记搜记录有几个符合要求，并统计答案

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

#define ll long long

int len,a[20],mod;
ll l,r,f[20][180][180][2];

inline ll dfs(int pos,int sum,int rm,int lim){
	if(pos>len&&!sum) return 0;
	if(pos>len) return (rm==0&&sum==mod);
	if(~f[pos][sum][rm][lim]) return f[pos][sum][rm][lim];
	int mx=lim?a[len-pos+1]:9;
	ll res=0;
	for(int i=0;i<=mx;++i)
		res+=dfs(pos+1,sum+i,1ll*(1ll*rm*10ll+i)%mod,lim&(i==mx));
    f[pos][sum][rm][lim]=res;
	return res;
}

inline ll solve(ll x){
	len=0;
	do{
		a[++len]=x%10;
		x/=10;
	}while(x);
	ll res=0;
	for(mod=1;mod<=9*len;++mod){
        memset(f,-1,sizeof(f));
		res+=dfs(1,0,0,1);
	}
	return res;
}

signed main(){
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
}

\(\text{Balanced Number}\)