数位DP概念和实例讲解

101819 阅读 0 评论 0 点赞

说到数位DP，它主要是用于处理一些与数位有关的问题，主要是计数问题。并且数位DP一直以来是DP家族里比较冷门的一种，但一旦遇上了，如果不会数位DP单纯靠暴力方法很难骗分。

一、什么是数位DP？

数位DP是一种计数用的DP，一般就是要统计一个区间[l,r]内满足一些条件数的个数。所谓数位DP，字面意思就是在数位上进行DP。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位！

之所以要引入数位的概念完全就是为了DP。数位DP的实质就是换一种暴力枚举的方式，使得新的枚举方式满足DP的性质，然后记忆化就可以了。

数位DP往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总数。而这个区间可能很大，简单的暴力代码如下：

int ans=0;
for(int i=l;i<=r;i++){
    if(check(i))ans++;
}

我们发现，若区间长度超过1e8，我们暴力枚举就会超时了，而数位DP则可以解决这样的题型。数位DP实际上就是在数位上进行DP。

数位DP解法

数位DP就是换一种暴力枚举的方式，使得新的枚举方式符合DP的性质，然后预处理好即可。

我们来看：我们可以用f(n)表示[0,n]的所有满足条件的个数，那么对于[l,r]我们就可以用[l,r]⟺f(r)−f(l−1)，相当于前缀和思想。那么也就是说我们只要求出f(n)即可。那么数位DP关键的思想就是从树的角度来考虑。将数拆分成位，从高位到低位开始枚举。我们可以视N为n位数，那么我们拆分。那么我们就可以开始分解建树，如下。之后我们就可以预处理再求解f(n)了，个人认为求解f(n)是最难的一步。

数位DP解法内容

听完是不是有点绕，我们可以来点题目练习一下，做完就会发现了数位DP的套路了。

二、数位DP经典例题

例题：度的数量

题目：求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：

度的数量

输入格式

第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B 。

输出格式

只包含一个整数，表示满足条件的数的个数。

数据范围

输入样例：

15 20

输出样例：

解题思路

此题实际上就是将十进制数转化为B进制数，判断位数上的值是否为1。那么我们可以视N为n位数，那么我们拆分。从树的角度考虑：我们设N=76543210，B=10，那么我们从高位往最低位开始枚举如下；枚举时，我们有两种选择：

（1）走右边分支，那么我们填，而题目要求每一位只能填1或者0,而，所以不是合法方案，我们直接剔除。

（2）走左边分支，那么我们可以填0~6，即，那么由于每一位只能填1或者0，所以我们累加这两种选择的方案。

记住，走到了左边分支是可以直接累加的。

所以我们实际上还是要做一个预处理的，我们用f[i][j]表示还剩下i位没有填，且需要填写j个1的方案数。那么在(i,j)这个状态，我们可以选择填1，那么接下来的状态就是f[i−1][j−1]，而如果填0，那么接下来的状态就是f[i−1][j]，那么状态转移方程就是f[i][j]=f[i-1][j]+f[i][j−1]。而初始状态即是当j=0时，f[i][0]=1。这样我们就可以预处理f数组了。

处理完之后我们就可以直接模拟做了。

代码如下：

/**
  *@filename:度的数量
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-05-12 11:23
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int l,r,k,b;
int f[35][35];
//首先我们先预处理f数组。其中f[i][j]表示剩下还有i个没填，需要填写j个1的方案数。
void init(){
    for(int i=0;i<35;i++){
        for(int j=0;j<=i;j++){
            if(!j)f[i][j]=1;
            else{
                f[i][j]=f[i-1][j]+f[i-1][j-1];
            }
        }
    }
}
int dp(int n){
    //求解f(n)。我们需要避免n为0的情况，这里需要特判。
    if(!n)return 0;
    vector<int> nums;//将n分割，存储位数。
    while(n){
        nums.push_back(n%b);
        n/=b;
    }
    int ans=0;//答案。
    int last=0;//前面的信息，这里代表的是前面分支选取了多少个1.
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        if(x){
            //说明x>0，我们可以选择左边分支填0.
            ans+=f[i][k-last];
            if(x>1){
                //当x>1我们才可以枚举左边分支填1.
                if(k-last-1>=0){
                    //如果还可以填1的话。
                    ans+=f[i][k-last-1];
                }
                break;//因为右边分支只能为0或1，所以不符合条件。break。
            }
            else{
                //当x=1就可以进入右边的分支继续讨论。
                last++;
                if(last>k)break;
            }
        }
        //考虑到最后一位，如果符合条件那么末位填0也算一种方案。
        if(!i&&last==k)ans++;
    }
    return ans;
}
void solve(){
}
int main(){
    cin>>l>>r>>k>>b;
    init();
    cout<<dp(r)-dp(l-1)<<endl;
    solve();
    return 0;
}