数位 dp

数位 \(\text{dp}\)

前言

谨慎学习此算法。

算法讲解

AcWing 1081.度的数量

1. 题意分析：你看到这道题，是不是无从下手？其实题目就是让我们求在 \(x \sim y\) 中，有多少个数分解成 \(B\) 进制后仅有 \(k\) 位为 \(1\)，其余均为 \(0\)；

2. 考虑暴力：从 \(x\) 枚举到 \(y\)，将 \(i(x \le i \le y)\) 分解为 \(B\) 进制，看是否满足条件，统计数量。因为 \(x,y \le 2^{31} - 1\)，所以很显然会 \(\text{TLE}\)；

3. 分析：首先我们可以求 \(1 \sim y\) 和 \(1 \sim (x - 1)\) 中有多少个数满足条件，最终答案即为 \(\text{dp(y) - dp(x - 1)}\)。首先我们要解决此题需要知道数位 \(\text{dp}\) 的核心方法：从高位到低位采用字典序来分类整批的统计。

那么这道题的思路就是：

1. 将 \(x\) 每一位数提取出来（\(B\) 进制）；

Code

vector<int> v;
while (x) {
    v.push_back(x % B);
    x /= B;
}

2. 按字典序从高到低整批统计；

Code

int res = 0,last = 0;
for (int i = v.size() - 1; i >= 0; -- i ) {
    int t = v[i]; // 拿出第 i 位
    if (!t) {
        if (!i && last == k) ++ res;
        continue;
    }
	// 1.第 i 位填 0
    res += f[i][k - last]; // 右边填 k - last 个 1 满足条件的数的个数
	// 2.第 i 位填 1
    if (t == 1) {
        ++ last;
        if (last > k) break;
    } else if (t > 1) {
        ++ last;
        if (last > k) break;
        res += f[i][k - last];
        break;
    }
    if (!i && last == k) ++ res; // 如果此数本身满足条件，也要累加
}

3. 初始化求 \(f_{i,j}\)

\(f_{i,0} = 1,f_{i,j} = f_{i - 1,j} + f_{i - 1,j - 1}(j \le i)\)

Code

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] + f[i - 1][j - 1];
}

AC Code of AcWing 1081.度的数量

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 35;

int x,y,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] + f[i - 1][j - 1];
}

int dp(int x) {
    if (!x) return 0;
    vector<int> v;
    while (x) {
        v.push_back(x % B);
        x /= B;
    }
    int res = 0,last = 0;
    for (int i = v.size() - 1; i >= 0; -- i ) {
        int t = v[i];
        if (!t) {
            if (!i && last == k) ++ res;
            continue;
        }
        res += f[i][k - last];
        if (t == 1) {
            ++ last;
            if (last > k) break;
        } else if (t > 1) {
            ++ last;
            if (last > k) break;
            res += f[i][k - last];
            break;
        }
        if (!i && last == k) ++ res;
    }
    return res;
}

signed main() {
    cin >> x >> y >> k >> B;
    init();
    cout << dp(y) - dp(x - 1) << endl;
    return 0;
}

作者：\(\text{songszh}\)