数位dp

数位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}/)