算法学习--数位DP

#include<iostream>
#include<vector>
using namespace std;
const int NN=36;
int C[NN][NN];
int X, Y, K, B;
//求区间[0,x]中的 “满足条件的数” 的个数
//“满足条件的数”是指：一个数的B进制表示，其中有K位是1、其他位全是0
int dp(int x){
    if(x==0) return 0;
    vector<int> nums;
    while(x>0){
        nums.push_back(x%B);
        x/=B;
    }
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--){
        int t=nums[i];
        // 如果当前位为0的话, 不会对结果产生贡献
        if(t>0){ 
            res+=C[i][K-last];
            if(t>1){
                if(K-last-1>=0)
                    res+=C[i][K-last-1];
                // 枚举过的数位就是已经确定下来的数
                // 我们不能使得确定下来的数大于 1 , 所以当遇到第一个 >1 的数的时候
                // 就把使得它为 1, 然后res+=C[i][K-last-1], 结束枚举
                break;
            }
            else{ // 如果当前位为1的话, 增加last
                last++;
                if(last>K) break;
            }
        }
        // 当枚举到最后一位时, 也就是x数本身, 如果它符合条件, 那么就纳入计数
        if(i==0 && K==last) res++;
    }
    return res;
}
int main(){
    cin>>X>>Y;
    cin>>K;
    cin>>B;
    for(int i=0;i<NN;i++){
        for(int j=0;j<=i;j++){
            if(j==0) 
                C[i][j]=1;
            else
                C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
    cout<<dp(Y)-dp(X-1)<<endl;
    return 0;
}

class Solution {
public:
    int countSpecialNumbers(int n) {
        string s=to_string(n);
        int m = s.length(), memo[m][1 << 10][2][2];
        memset(memo, -1, sizeof memo);
        // 返回从 pos 开始填数字, 之前填过的数字为mask, 能构造出的特殊整数的个数
        // is_limit 表示前面填的数字是否是 n 对应位上的, 如果是的话当前位最大为 (int)s[pos], 否则为 9
        // is_num 表示前面是否填了数字(是否跳过)
        function<int(int,int,bool,bool)> dp=[&](int pos, int mask, bool is_limit, bool is_num){
            if(pos==s.size()){
                return (int)is_num;
            }
            if(memo[pos][mask][(int)is_limit][(int)is_num]!=-1)
                return memo[pos][mask][(int)is_limit][(int)is_num];
            int res=0;
            if(!is_num){
                res+=dp(pos+1, mask, false, false);
            }
            int up=is_limit?s[pos]-'0':9;
            for(int d=(is_num?0:1);d<=up;d++){
                if(!((mask>>d) & 1)){
                    res+=dp(pos+1, mask|(1<<d), is_limit && d==up, true);
                }
            }
            memo[pos][mask][(int)is_limit][(int)is_num]=res;
            return res;
        };
        // 递归入口, is_limit 要为true, 用n来施加限制
        return dp(0, 0, true, false);
    }
};