說(shuō)到數(shù)位DP，它主要是用于處理一些與數(shù)位有關(guān)的問(wèn)題，主要是計(jì)數(shù)問(wèn)題。并且數(shù)位DP一直以來(lái)是DP家族里比較冷門的一種，但一旦遇上了，如果不會(huì)數(shù)位DP單純靠暴力方法很難騙分。

一、什么是數(shù)位DP？

數(shù)位DP是一種計(jì)數(shù)用的DP，一般就是要統(tǒng)計(jì)一個(gè)區(qū)間[l,r]內(nèi)滿足一些條件數(shù)的個(gè)數(shù)。所謂數(shù)位DP，字面意思就是在數(shù)位上進(jìn)行DP。數(shù)位還算是比較好聽(tīng)的名字，數(shù)位的含義：一個(gè)數(shù)有個(gè)位、十位、百位、千位......數(shù)的每一位就是數(shù)位！

之所以要引入數(shù)位的概念完全就是為了DP。數(shù)位DP的實(shí)質(zhì)就是換一種暴力枚舉的方式，使得新的枚舉方式滿足DP的性質(zhì)，然后記憶化就可以了。

數(shù)位DP往往都是這樣的題型，給定一個(gè)閉區(qū)間[l,r]，讓你求這個(gè)區(qū)間中滿足某種條件的數(shù)的總數(shù)。而這個(gè)區(qū)間可能很大，簡(jiǎn)單的暴力代碼如下：

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

我們發(fā)現(xiàn)，若區(qū)間長(zhǎng)度超過(guò)1e8，我們暴力枚舉就會(huì)超時(shí)了，而數(shù)位DP則可以解決這樣的題型。數(shù)位DP實(shí)際上就是在數(shù)位上進(jìn)行DP。

數(shù)位DP解法

數(shù)位DP就是換一種暴力枚舉的方式，使得新的枚舉方式符合DP的性質(zhì)，然后預(yù)處理好即可。

 我們來(lái)看：我們可以用f(n)表示[0,n]的所有滿足條件的個(gè)數(shù)，那么對(duì)于[l,r]我們就可以用[l,r]?f(r)?f(l?1)，相當(dāng)于前綴和思想。那么也就是說(shuō)我們只要求出f(n)即可。那么數(shù)位DP關(guān)鍵的思想就是從樹的角度來(lái)考慮。將數(shù)拆分成位，從高位到低位開始枚舉。我們可以視N為n位數(shù)，那么我們拆分。那么我們就可以開始分解建樹，如下。之后我們就可以預(yù)處理再求解f(n)了，個(gè)人認(rèn)為求解f(n)是最難的一步。

聽(tīng)完是不是有點(diǎn)繞，我們可以來(lái)點(diǎn)題目練習(xí)一下，做完就會(huì)發(fā)現(xiàn)了數(shù)位DP的套路了。

二、數(shù)位DP經(jīng)典例題

例題：度的數(shù)量

題目：求給定區(qū)間 [X,Y] 中滿足下列條件的整數(shù)個(gè)數(shù)：這個(gè)數(shù)恰好等于K個(gè)互不相等的B的整數(shù)次冪之和。例如，設(shè) X=15,Y=20,K=2,B=2，則有且僅有下列三個(gè)數(shù)滿足題意：

輸入格式

第一行包含兩個(gè)整數(shù) X 和 Y，接下來(lái)兩行包含整數(shù) K 和 B 。

輸出格式

只包含一個(gè)整數(shù)，表示滿足條件的數(shù)的個(gè)數(shù)。

數(shù)據(jù)范圍

輸入樣例：

15 20

2

2

輸出樣例：

3

解題思路

此題實(shí)際上就是將十進(jìn)制數(shù)轉(zhuǎn)化為B進(jìn)制數(shù)，判斷位數(shù)上的值是否為1。那么我們可以視N為n位數(shù)，那么我們拆分。從樹的角度考慮：我們?cè)O(shè)N=76543210，B=10，那么我們從高位往最低位開始枚舉如下；枚舉時(shí)，我們有兩種選擇：

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

（2）走左邊分支，那么我們可以填0~6，即，那么由于每一位只能填1或者0，所以我們累加這兩種選擇的方案。

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

所以我們實(shí)際上還是要做一個(gè)預(yù)處理的，我們用f[i][j]表示還剩下i位沒(méi)有填，且需要填寫j個(gè)1的方案數(shù)。那么在(i,j)這個(gè)狀態(tài)，我們可以選擇填1，那么接下來(lái)的狀態(tài)就是f[i?1][j?1]，而如果填0，那么接下來(lái)的狀態(tài)就是f[i?1][j]，那么狀態(tài)轉(zhuǎn)移方程就是f[i][j]=f[i-1][j]+f[i][j?1]。而初始狀態(tài)即是當(dāng)j=0時(shí)，f[i][0]=1。這樣我們就可以預(yù)處理f數(shù)組了。

處理完之后我們就可以直接模擬做了。

代碼如下：

/**
  *@filename:度的數(shù)量
  *@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];
//首先我們先預(yù)處理f數(shù)組。其中f[i][j]表示剩下還有i個(gè)沒(méi)填，需要填寫j個(gè)1的方案數(shù)。
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分割，存儲(chǔ)位數(shù)。
    while(n){
        nums.push_back(n%b);
        n/=b;
    }
    int ans=0;//答案。
    int last=0;//前面的信息，這里代表的是前面分支選取了多少個(gè)1.
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        if(x){
            //說(shuō)明x>0，我們可以選擇左邊分支填0.
            ans+=f[i][k-last];
            if(x>1){
                //當(dāng)x>1我們才可以枚舉左邊分支填1.
                if(k-last-1>=0){
                    //如果還可以填1的話。
                    ans+=f[i][k-last-1];
                }
                break;//因?yàn)橛疫叿种е荒転?或1，所以不符合條件。break。
            }
            else{
                //當(dāng)x=1就可以進(jìn)入右邊的分支繼續(xù)討論。
                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;
}