数位dp学习

参考借鉴：

数位DP学习整理（数位DP看完这篇你就会了）-CSDN博客

AcWing1081.度的数量(数位DP)题解_求给定区间$ [x,y]$ 中满足下列条件的整数个数:这个数恰好等于 k k k 个互不相等-CSDN博客

就是类似前缀和的思想，进行数字在位数上的前缀操作，以此dp来简化暴力计算的方法；

例题一：

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

输入格式
第一行包含两个整数 X 和 Y，接下来两行包含整数 K和 B。
输出格式
只包含一个整数，表示满足条件的数的个数。
数据范围
1 ≤ X ≤ Y ≤ 
1 ≤ K ≤ 20
2 ≤ B ≤ 10
输入样例：
15 20
2
2
输出样例：
3

 解题思路：
首先将N转化为b进制数,则一个数能由b的整数次方合成,则转化为b进制后，对应的b的次方的位置为1, 那么我们只需判断转化为b进制后，各个位数上0，1的个数就可以,得到总的方案数；

假设 N 转化为 b 进制后有 n 位数,从最高位开始遍历,当前位的数为 x, 枚举填 0 和填 1 的方案：

1.如果 x == 0,直接跳过(不能由b的多少次方组成)

2.如果x == 1, 当前位置 i 可以填0, 还需要填 k 个 1 ，则需要从剩下的 i - 1 位中填 k 个 1 ,即C(i - 1, k), 并让x =1，继续判断下一位;

3.如果x > 1, 则该位上可以填 0 ,方案数为C(i - 1, k), 也可以填 1 ,即方案数为C(i - 1, k - 1), 因为填大于 1 的数不合法，所以直接break掉

4.判断 i 是否等于 0，即判断i是否为最后一位, 如果是的话, 那么最后以后可以填 0 , ans++;f(i, j)表示从i个数里面选j个数的方案数,预处理出每一位上左分支的方案数

//首先我们先预处理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];
            }
        }
    }
}

上述代码描述了填写内容的转移关系

 完整代码：

#include <bits/stdc++.h>
#include <iostream>  
#include <vector>  
#include <string>  
#include <unordered_set>  
#include <cmath>  

using namespace std;

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

int l=15,r=20,k=2,b=2;
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;
    int l=15,r=20,k=2,b=2;
    init();
    cout<<dp(r)-dp(l-1)<<endl;
    solve();
    return 0;
}