AcWing 1081 度的数量

一、读懂题意

• \([X,Y]\)之间所有数(闭区间)，表示成\(B\)进制，然后每一位上必须是\(1\)或\(0\)。
  只有每个数位是\(1\)或者是\(0\)的才能表示出题目要求的数字。

• 题目要求 一段区间 内符合某些条件的数的个数，我们用 前缀和思想 转换为求两个 前缀区间 的问题

\(res[l,r]=res[1,r]?res[1,l?1]\)

• 题目要求求出在指定的数字\(n\)以内，\(B\)进制每个位置上的数字要么为\(1\)，要么为\(0\)，而且为\(1\)的个数还是\(K\)的数字个数是多少。

二、数位分离之模板大法

#include 

using namespace std;
const int N = 35; //因为2进制是最小的进制，2^31是极限，所以N=31，为了防止越界，这里开到了35
int l, r;         //左右边界
int k, b;         //k个b进制数
int a[N];         //对数字进行拆分的数位数组,数位分离专用
int dp[N][N];     //dp[pos][sum]表示当前第pos位,已经出现了几次数字1

/**
 * 功能：统计[0~pos]之间答案
 * @param pos 当前枚举到的数位pos（搜索的深度）由高到低
 * @param sum 数字1已经出现了几次
 * @param limit 是不是贴上界
 * @return 数字个数
 */
int dfs(int pos, int sum, bool limit) {
    if (pos == -1) return sum == k;//枚举到最后一位数位，是否恰有k个不同的1（也是递归的终止条件）
    //记忆化搜索，前提是不贴着上界（可以枚举满这一位所有的数字）
    //只有无限制、无前导零才算，不然都是未搜索完的情况
    if (!limit && ~dp[pos][sum]) return dp[pos][sum];
    //up表示能枚举的最高位数
    int res = 0, up = limit ? min(a[pos], 1) : 1;
    for (int i = 0; i <= up; i++) {     //尝试填充每一个可能的数字
        //剪枝
        if (sum + i > k) continue;      //如果超过了k个限制，是不行的(题意要求)
        //下一个位置的深搜
        res += dfs(pos - 1, sum + i, limit && i == a[pos]);
    }
    //如果不受限制，则记录下来提供下次使用；如果受限制，则一把一利索
    return limit ? res : dp[pos][sum] = res;
}

int calc(int x) {
    int pos = 0;
    while (x) a[pos++] = x % b, x /= b;        //把x按照进制分解到数组中
    return dfs(pos - 1, 0, true);
}

int main() {
    cin >> l >> r >> k >> b;
    memset(dp, -1, sizeof dp);
    cout << calc(r) - calc(l - 1) << endl;
    return 0;
}

三、DP解题思路

这是一道数位\(dp\)问题，对于数位\(dp\)问题关键就在于分类讨论。

首先我们把数字\(n\)对于\(B\)进制来进行分解 ，将每一位上的数字存入一个数组中，然后从高位往低位去讨论，

首先 对于第 \(i\) 位数字 \(x\) 有三种情况

\(x = 0\)
\(i\) 位上只能取 \(0\) ，所以产生\(k\)位\(1\)的光荣使命只能交给 \(i-1\)去实现啦~

\(x = 1\)

• \(i\) 位上取 \(0\) 的时候，后面\(i-1\)位都可以随意取值(全都可以取到)。
• \(i\) 位上取 \(1\) 的时候，后面\(i-1\)位要在小于题目的数\(i-1\)位的前提下取值，并且能取 \(k-last-1\)个\(1\)。[这类似于一个递归的子问题]

\(x > 1\)
\(i\) 位上 可以取 \(1 ，0\) ，并且后面 \(i-1\) 位可以随便取。

这里 \(i-1\)位随便取 和 对于\(i-1\) 位讨论的区别，就体现在前一个直接用组合数 \(f[i-1][k-last]\)就可以，后面则需要再进入循环去讨论。

对于最后一位进行单独讨论，如果对于 最后一位时 ，所有的\(k\)个\(1\)都已经取好了，也就是\(k==last\)了，才做\(res++\)。

组合数公式的递推式
\(C_a^b=C_{a-1}^{b-1}+C_{a-1}^b\)

四、DP代码实现

#include

using namespace std;

const int N = 33; //1≤X≤Y≤2^31?1 2进制时，数位最多，最多不会超过32位，这里给了33位，足够
int K, B;         //允许使用K个，B进制
int f[N][N];

//求组合数
void init() {
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= i; j++)
            if (!j)f[i][j] = 1;
            else f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
}

/**
 * 功能：计算0~n之间符合题意要求的数字的个数
 * @param n
 * @return
 */
int dp(int n) {
    if (!n) return 0;//如果n==0，返回0
    //转为B进制，存入nums数组
    vector nums;
    while (n) nums.push_back(n % B), n /= B;
    int res = 0;
    int last = 0;//表示已经取了多少个1
    for (int i = nums.size() - 1; i >= 0; i--) {//从最高位对每一位数讨论
        int x = nums[i];
        if (x) {//当x==0时，就请下一位继续讨论吧，表现在代码上就是只讨论x>=1的情况

            //(1)不管是x==1,还是x>1,它们在本位置选择放置0时，套路是一样的：
            //第i位取0，就是对于后面i位(0~i-1,共i位)取k-last个1的数量
            res += f[i][K - last];

            //(2)处理本位取1的情况
            if (x > 1) {
                //如果x>1，就可以直接用组合数表示出来，不用进行讨论，也就是i位取1的时候，后面i位随便取k-last-1个1
                if (K - last - 1 >= 0) res += f[i][K - last - 1];
                break;  //算完了，后面的情况全包圆了，还算个啥？
            } else {
                //如果x==1，那么i位取1的时候，还要进行讨论，后面i位不能随便取，也就不是组合数
                last++;//多占用了一个1
                if (last > K) break;//已选择个数++后，已经大于限定值K，则不用再讨论下去，退出循环，返回当前结果
            }
        }
        //对于最后一位来特殊考虑
        if (!i && last == K) res++;
    }
    //返回方案数
    return res;
}

int main() {
    //预处理组合数
    init();
    //左右边界
    int l, r;
    cin >> l >> r >> K >> B;
    //利用前缀和思路进行计算
    cout << dp(r) - dp(l - 1) << endl;
    return 0;
}