数位 DP 是这样一类问题：求某个区间内，满足某种性质的数的个数。

有两个技巧：

  1. 前缀和思想。区间有两个界限，把它转化成一个界限，例如通过 f(N) 表示 0 - N 中满足这种性质的数的个数，求 [X, Y] 时，可用 f(Y) - f(X - 1)。
  2. 从树的角度进行考虑，按位进行分类讨论。

度的数量

度的数量

组合数的计算公式为：Cab=Ca−1b+Ca−1b−1C_a^b = C_{a-1}^b + C_{a-1}^{b-1}

简化题意：给一个区间 [X, Y]，问这个区间内有多少个数符合这样的条件：这个数的 B 进制表示中，有 K 位上是 1，其余位都是 0.

思路：

  1. 先将 n 转换成 B 进制数保存起来
  2. n 每一位上的数我们成为限定值，对 n 的每一位进行分类讨论
    1. 可以取限定值
    2. 取 0 ~ 限定值-1 的一个数

对于本题，用不到 2、3、9 这种限定值，本题要求 K 位上全填 1，其余位全填 0，当某位上的限定值 > 1 时，后面的位可以随便填（0 或 1），方案数可以直接算出来，然后 break 掉就可以了。

对 B 进制数从最高位开始遍历，用 last 存储当前位之前取过 1 的位的个数：

  1. 限定值为 0，当前位只能取 0，后面剩余位可以取 k - last 个 1
  2. 限定值为 1，当前位可以取 0 或 1。取 0 时后面剩余位可以取 k - last 个 1；取 1 时后面剩余位可以取 k - last - 1 个 1，因为当前位占用了一个 1，所以要减一
  3. 限定值大于 1，当前位可以取 0 或 1，同 2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
using namespace std;

const int N = 35;
int k, b;  // k 能用的 1 的个数，b 进制
int c[N][N];

// 预处理求组合数 C(i,j)，从 i 里选 j 个数。有数学意义要保证 j<=i
void init() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= i; j++) {
      if (!j)
        c[i][j] = 1;
      else
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
}

int dp(int n) {
  if (!n) return 0;
  vector<int> nums;
  while (n) nums.push_back(n % b), n /= b; // 将 n 转换成 b 进制
  int res = 0;
  int last = 0;  //当前位之前选了多少1
  for (int i = nums.size() - 1; i >= 0; i--) { // 从最高位开始遍历 n
    int x = nums[i]; // x 是限定位
    if (x) { // 限定位不为 0，左侧分支
      res += c[i][k - last]; // 当前位可以取 0，在后面的 i 位中选出剩余个数个 1 的选法为 C(i, k-last)
      if (x > 1) { // 限定位大于 1
        if (k - last - 1 >= 0) res += c[i][k - last - 1]; // 当前位可以取 1，在后面的 i 位中选出剩余个数个 1 的选法为 C(i, k-last-1)，因为当前位已经取 1 了，所以要 -1
        break; // 不用再考虑 2、3 等等，不符合本题要求，本质上逐位遍历就是在走最右侧分支，碰到不是 1 的就可以直接停止遍历了
      } else { // 限定位就是 1，放到下一位来处理，下一位处理的时候可用的 1 的个数会少一个
        last++;
        if (last > k) break;
      }
    }
    if (!i && last == k) res++; // 到达最后一位时，数字本来就有了 K 个 1，这个数本身也算一种方案
  }
  return res;
}

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

数字游戏

1082. 数字游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
using namespace std;

const int N = 15;

int f[N][N];

void init() {
  for (int i = 0; i <= 9; i++) f[1][i] = 1;
  for (int i = 2; i < N; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = j; k <= 9; k++) {
        f[i][j] += f[i - 1][k];
      }
    }
  }
}

int dp(int n) {
  if (!n) return 1;
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;
  int res = 0;
  int last = 0;  // 记录上一位数是几
  for (int i = nums.size() - 1; i >= 0; i--) {
    int x = nums[i];
    for (int j = last; j < x; j++) {
      res += f[i + 1][j];
    }
    if (x < last) break;
    last = x;
    if (!i) res++;
  }
  return res;
}

int main() {
  init();
  int l, r;
  while (cin >> l >> r) {
    cout << dp(r) - dp(l - 1) << endl;
  }
  return 0;
}

Windy 数

Windy 数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>

using namespace std;

const int N = 11;
int f[N][10];  // f[i][j] 表示共 i 位，最高位是 j 的 windy 数的个数

void init() {
  for (int i = 0; i <= 9; i++) f[1][i] = 1;
  for (int i = 2; i < N; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = 0; k <= 9; k++) {
        if (abs(j - k) >= 2) {
          f[i][j] += f[i - 1][k];
        }
      }
    }
  }
}

int dp(int n) {
  if (!n) 0;
  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;

  int res = 0;
  int last = -2;
  for (int i = nums.size() - 1; i >= 0; i--) {
    int x = nums[i];
    for (int j = i == nums.size() - 1; j < x; j++) {  // 首位不能填0
      if (abs(j - last) >= 2) {
        res += f[i + 1][j];
      }
    }
    if (abs(x - last) >= 2)
      last = x;
    else
      break;
    if (!i) res++;
  }
  for (int i = 1; i < nums.size(); i++) {
    for (int j = 1; j <= 9; j++) {
      res += f[i][j];
    }
  }
  return res;
}

int main() {
  init();
  int l, r;
  cin >> l >> r;
  cout << dp(r) - dp(l - 1) << endl;
  return 0;
}

数字游戏 2

数字游戏 2

给一个区间，问这个区间内多少个数符合这个性质：每一位加起来再模 P 等于零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

const int N = 11;
const int M = 110;

int P;
// 共 i 位，最高位为 j，各位相加再模 P 等于 k，这样的数的个数
int f[N][10][M];

int mod(int x, int y) {
  return (x % y + y) % y;
}

// 预处理 f[i][j][k]
void init() {
  memset(f, 0, sizeof f);
  // 只有一位，枚举最高位 0~9
  for (int j = 0; j <= 9; j++) {
    f[1][j][j % P]++;
  }
  for (int i = 2; i < N; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = 0; k < P; k++) {
        for (int x = 0; x <= 9; x++) { // 注意这里范围是 0~9，因为位与位之间没有任何约束关系，所以能随便取，和不降数那个题有区别
          f[i][j][k] += f[i - 1][x][mod(k - j, P)];
        }
      }
    }
  }
}

int dp(int n) {
  if (!n) {
    return 1;
  }
  vector < int > nums;
  while (n) {
    nums.push_back(n % 10);
    n /= 10;
  }
  int res = 0;
  int last = 0; // 当前位之前所有位的和
  for (int i = nums.size() - 1; i >= 0; i--) {
    int x = nums[i];
    // 当前位选择 0 ~ x-1 的情况，进行累加
    for (int j = 0; j < x; j++) {
      // 当前位选择填 j，要满足当前以及之后所有位相加的和为 -last 模 P，才能使整个数所有位相加模 P 为 0
      res += f[i + 1][j][mod(-last, P)];
    }
    last += x;
    if (!i && last % P == 0) { // 到达最后一位，且每位的和模 P 为 0，即这个数本身也是符合要求的
      res++;
    }
  }
  return res;
}

int main() {
  int l, r;
  while (cin >> l >> r >> P) {
    init();
    cout << dp(r) - dp(l - 1) << endl;
  }
  return 0;
}