数位DP

问题 往往是求一个区间中满足某种性质的数的个数。

技巧1 [X, Y] -> f(Y) - f(X - 1), f(N)：求0(或1)到N中满足性质的数个数

技巧2 树

易错点：

  1. main()中不执行init()
  2. 不能正确判断是否需要处理前导0，只有Windy数这种题型需排除前导0（第一层左支只能取1∼an−1−11\sim a_{n-1}-1）
  3. 不能判断n等于0时返回0还是1

AcWing 1081. 度的数量

求给定区间 [X,Y][X,Y] 中满足下列条件的整数个数：这个数恰好等于 KK 个互不相等的 BB 的整数次幂之和。

例如，设 X=15,Y=20,K=2,B=2X = 15, Y = 20, K = 2, B = 2，则有且仅有下列三个数满足题意：

17=24+2017 = 2^4 + 2^0
18=24+2118 = 2^4 + 2^1
20=24+2220 = 2^4 + 2^2

输入格式

第一行包含两个整数 XX 和 YY，接下来两行包含整数 KK 和 BB。

输出格式

只包含一个整数，表示满足条件的数的个数。

数据范围

1≤X≤Y≤231−11 \le X \le Y \le 2^{31}-1,
1≤K≤201 \le K \le 20,
2≤B≤102 \le B \le 10

输入样例：

15 20
2
2

输出样例：

3

数位DP

树分支

只有当前位上数大于0才存在左右分支

当 x>0x>0 时，左支一定会存在：左支取 0∼x−10\sim x-1, 当 x>0x>0 时，左支至少可以取0

当 x>1x>1 时，右支不能存在，左支中可以再取0：当 x>1x>1 时，按照数型结构此层就得取 xx，而题目中规定的是**“恰好等于”**，即每一为上数字必须取0或1，所以右分支不能继续往下走了。

当 x=1x = 1 时，右支取1（左支取 0∼x−10\sim x -1 就不能再取啦），沿右支进入下一层

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
#include <iostream>
#include <vector>

using namespace std;

const int kN = 35;
int K, B;
int f[kN][kN];

// 计算f[i][j]: C_a^b
void init() {
  for (int i = 0; i < kN; 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) {
  if (!n) return 0;  // K >= 1
  vector<int> nums;
  while (n) {
    nums.push_back(n % B);  // B进制, 而非十进制
    n /= B;
  }
  int res = 0;
  int last = 0;
  for (int i = nums.size() - 1; ~i; i--) {  // ~i等价于i != -1
    int x = nums[i];
    if (x) {  // 当前值大于0才会存在左右分支
      res += f[i][K - last];  // a_{n-1}选0, a_{n-2}到a_0有i=n-1个数
      if (x > 1) {
        if (K - last - 1 >= 0) res += f[i][K - last - 1];
        break;  // x>1时, 右分支a_{n-1}没法往下走
      } else {  // x=1时, 成为右分支往下一层走
        last++;
        if (last > K) break;
      }
    }
    if (!i && last == K) res++;  // 整棵树唯一的右根
  }
  return res;
}

int main() {
  init();
  int l, r;
  scanf("%d%d%d%d", &l, &r, &K, &B);
  printf("%d\n", dp(r) - dp(l - 1));
  return 0;
}

AcWing 1082. 数字游戏

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123123，446446。

现在大家决定玩一个游戏，指定一个整数闭区间 [a,b][a,b]，问这个区间内有多少个不降数。

输入格式

输入包含多组测试数据。

每组数据占一行，包含两个整数 aa 和 bb。

输出格式

每行给出一组测试数据的答案，即 [a,b][a,b] 之间有多少不降数。

数据范围

1≤a≤b≤231−11 \le a \le b \le 2^{31}-1

输入样例：

1 9
1 19

输出样例：

9
18

数位dp

根据每一位aia_i的值可分为左右两支：

  • 左支 最高位取0∼an−10 \sim a_n -1（其实是<last>∼an−1<last> \sim a_n -1），低位无限制，可以预计算
  • 右支 最高为取ana_n，低位有限制，需要进一步分支

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 kN = 15;

int f[kN][kN];

// 计算f[i][j]: i位且最高位为j的不降数个数
void init() {
  for (int i = 0; i <= 9; i++) f[1][i] = 1;
  for (int i = 2; i < kN; 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;  // 0也是不降低数
  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; i--) {
    int x = nums[i];
    for (int j = last; j < x; j++) {  // < 左支叶只能到a_{n-1}
      res += f[i + 1][j];
    }
    if (x < last) break;
    last = x;  // 沿右走
    if (!i) res++;
  }
  return res;
}

int main() {
  init();
  int l, r;
  while (scanf("%d%d", &l, &r) == 2) {  // == 2
    printf("%d\n", dp(r) - dp(l - 1));
  }
  return 0;
}

AcWing 1083. Windy数

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。

Windy 想知道，在 AA 和 BB 之间，包括 AA 和 BB，总共有多少个 Windy 数？

输入格式

共一行，包含两个整数 AA 和 BB。

输出格式

输出一个整数，表示答案。

数据范围

1≤A≤B≤2×1091 \le A \le B \le 2 \times 10^9

输入样例1：

1 10

输出样例1：

9

输入样例2：

25 50

输出样例2：

20

题解

本题出现了一个问题：不能使用前导0

举一个例子：014（即14）按理来说是Windy数，但是由于我们给他加上了前导0，这样看上去就不是Windy数了。

正确的做法：第一层左分支只能取1∼an−1−11\sim a_{n-1} -1，最后还要加上位数少于N的位数的情况。(第一位必须从1开始取就会遗漏位数较N少的数，比如14)

当n = 0时，虽然0也是Windy数，但为了运算正确，我们必须返回0：

比如 l = 1, r = 1时，dp(r = 1)其实只有有1层，有2个数：0和1, 即返回2。
所以在可以使用前导0的情况下，根据具体意义取ret 1是可以的，但是这里ret 0的话, dp(1) - dp(0) = 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
51
52
53
#include <iostream>
#include <vector>

using namespace std;

const int kN = 11;
int f[kN][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 < kN; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = 0; k <= 9; k++) {
        f[i][j] += (abs(j - k) >= 2) * f[i - 1][k];
      }
    }
  }
}

int dp(int n) {
  if (!n) return 0;  // 0虽然也是Windy数，但由于计算时排除前导0, 这里取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; i--) {
    int x = nums[i];
    for (int j = (i == nums.size() - 1); j < x; j++) {  // 第一层从1开始取
      res += (abs(j - last) >= 2) * f[i + 1][j];
    }
    if (abs(x - last) < 2) break;
    last = x;
    if (!i) res++;
  }
  for (int i = 1; i < nums.size(); i++) {  // 加上位数较N少的情况
    for (int j = 1; j <= 9; j++) {
      res += f[i][j];
    }
  }
  return res;
}

int main() {
  init();
  int l, r;
  scanf("%d%d", &l, &r);
  printf("%d\n", dp(r) - dp(l - 1));
  return 0;
}

AcWing 1084. 数字游戏 II

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 mod Nmod\ N 为 00。

现在大家又要玩游戏了，指定一个整数闭区间 [a.b][a.b]，问这个区间内有多少个取模数。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含三个整数 a,b,Na,b,N。

输出格式

对于每个测试数据输出一行结果，表示区间内各位数字和 mod Nmod\ N 为 00 的数的个数。

数据范围

1≤a,b≤231−11 \le a,b \le 2^{31}-1,
1≤N<1001 \le N < 100

输入样例：

1 19 9

输出样例：

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
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int kN = 11, kM = 105;
int N;
int f[kN][10][kM];

// cpp的取模运算与py等不同, cpp中-1 % 3 = -2
int mod(int x, int y) {
  return (x % y + y) % y;
}

// 计算f[i][j][k]: i位, 最高位为j, 且所以数位山数的和为k的数个数
void init() {
  memset(f, 0, sizeof f);  // 每轮清空状态
  for (int i = 0; i <= 9; i++) f[1][i][i % N] = 1;
  for (int i = 2; i < kN; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = 0; k < N; k++) {
        for (int x = 0; x <= 9; x++) {
          f[i][j][k] += f[i - 1][x][mod(k - j, N)];
        }
      }
    }
  }
}

int dp(int n) {
  if (!n) return 1;  // 0 mod N 总等于0, 符合要求
  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; i--) {
    int x = nums[i];
    for (int j = 0; j < x; j++) {
      res += f[i + 1][j][mod(-last, N)];
    }
    last = mod(last + x, N);
    if (!i && mod(last, N) == 0) res++;
  }
  return res;
}

int main() {
  int l, r;
  while (scanf("%d%d%d", &l, &r, &N) == 3) {
    init();  // 记得init()
    printf("%d\n", dp(r) - dp(l - 1));
  }
  return 0;
}

AcWing 1085. 不要62

杭州人称那些傻乎乎粘嗒嗒的人为 6262（音：laoer）。

杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。

不吉利的数字为所有含有 44 或 6262 的号码。例如：62315,73418,8891462315,73418,88914 都属于不吉利号码。但是，6115261152 虽然含有 66 和 22，但不是 连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照号区间 [n,m][n,m]，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含一个整数对 nn 和 mm。

当输入一行为“0 0”时，表示输入结束。

输出格式

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

数据范围

1≤n≤m≤1091 \le n \le m \le 10^9

输入样例：

1 100
0 0

输出样例：

80

题解

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
#include <iostream>
#include <vector>

using namespace std;

const int kN = 11;
int f[kN][kN];

// 计算f[i][j]: i位, 且最高位为j的满足条件数的个数
void init() {
  for (int i = 0; i <= 9; i++) {
    if (i == 4) continue;
    f[1][i] = 1;
  }
  for (int i = 2; i < kN; i++) {
    for (int j = 0; j <= 9; j++) {
      if (j == 4) continue;
      for (int k = 0; k <= 9; k++) {
        if (k == 4 || (j == 6 && k == 2)) continue;
        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; i--) {
    int x = nums[i];
    for (int j = 0; j < x; j++) {
      if (j == 4 || (last == 6 && j == 2)) continue;
      res += f[i + 1][j];
    }
    if (x == 4 || (last == 6 && x == 2)) break;
    last = x;
    if (!i) res++;
  }
  return res;
}

int main() {
  init();
  int l, r;
  while (scanf("%d%d", &l, &r), l || r) {
    printf("%d\n", dp(r) - dp(l - 1));
  }
  return 0;
}

AcWing 1086. 恨7不成妻

单身！

依然单身！

吉哥依然单身！

DS 级码农吉哥依然单身！

所以，他平生最恨情人节，不管是 214214 还是 7777，他都讨厌！

吉哥观察了 214214 和 7777 这两个数，发现：

2+1+4=72 + 1 + 4 = 7
7+7=7×27 + 7 = 7 \times 2
77=7×1177 = 7 \times 11

最终，他发现原来这一切归根到底都是因为和 77 有关！

所以，他现在甚至讨厌一切和 77 有关的数！

什么样的数和 77 有关呢？

如果一个整数符合下面三个条件之一，那么我们就说这个整数和 77 有关：

  1. 整数中某一位是 77；
  2. 整数的每一位加起来的和是 77 的整数倍；
  3. 这个整数是 77 的整数倍。

现在问题来了：吉哥想知道在一定区间内和 77 无关的整数的平方和。

输入格式

第一行包含整数 TT，表示共有 TT 组测试数据。

每组数据占一行，包含两个整数 LL 和 RR。

输出格式

对于每组数据，请计算 [L,R][L,R] 中和 77 无关的数字的平方和，并将结果对 109+710^9+7 取模后输出。

数据范围

1≤T≤501 \le T \le 50,
1≤L≤R≤10181 \le L \le R \le 10^{18}

输入样例：

3
1 9
10 11
17 17

输出样例：

236
221
0

题解

大体看懂了，跟着y总敲了一遍，累，暂时没动力继续咯……

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int kN = 20, N = 1e9 + 7;

struct F {
  int s0, s1, s2;
}f[kN][10][7][7];

int power7[kN], power9[kN];

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

void init() {
  for (int i = 0; i <= 9; i++) {
    if (i == 7) continue;
    auto &v = f[1][i][i % 7][i % 7];
    v.s0++, v.s1 += i, v.s2 += i * i;
  }
  LL power = 10;
  for (int i = 2; i < kN; i++, power *= 10) {
    for (int j = 0; j <= 9; j++) {
      if (j == 7) continue;
      for (int a = 0; a < 7; a++) {
        for (int b = 0; b < 7; b++) {
          for (int k = 0; k <= 9; k++) {
            if (k == 7) continue;
            auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)];
            v1.s0 = mod(v1.s0 + v2.s0, N);
            v1.s1 = mod(v1.s1 + v2.s1 + j * (power % N) % N * v2.s0, N);
            v1.s2 = mod(v1.s2 + 
                        j * j * (power % N) % N * (power % N) % N * v2.s0 + 
                        2 * j * power % N * v2.s1 + 
                        v2.s2,
                        N);
          }
        }
      }
    }
  }
  power7[0] = power9[0] = 1;
  for (int i = 1; i < kN; i++) {
    power7[i] = power7[i - 1] * 10 % 7;
    power9[i] = power9[i - 1] * 10ll % N;
  }
}

F get(int i, int j, int a, int b) {
  int s0 = 0, s1 = 0, s2 = 0;
  for (int x = 0; x < 7; x++) {
    for (int y = 0; y < 7; y++) {
      if (x != a && y != b) {
        auto v = f[i][j][x][y];
        s0 = (s0 + v.s0) % N;
        s1 = (s1 + v.s1) % N;
        s2 = (s2 + v.s2) % N;
      }
    }
  }
  return {s0, s1, s2};
}

int dp(LL n) {
  if (!n) return 0;
  LL bak_n = n % N;
  vector<int> nums;
  while (n) {
    nums.push_back(n % 10);
    n /= 10;
  }
  int res = 0;
  LL last_a = 0, last_b = 0;
  for (int i = nums.size() - 1; ~i; i--) {
    int x = nums[i];
    for (int j = 0; j < x; j++) {
      if (j == 7) continue;
      int a = mod(-last_a * power7[i + 1], 7);
      int b = mod(-last_b, 7);
      auto v = get(i + 1, j, a, b);
      res = mod(res + 
                (last_a % N) * (last_a % N) % N * power9[i + 1] % N * power9[i + 1] % N * v.s0 % N + 
                2 * last_a % N *power9[i + 1] % N * v.s1 + 
                v.s2,
                N);
    }
    if (x == 7) break;
    last_a = last_a * 10 + x;
    last_b += x;
    if (!i && last_a % 7 && last_b % 7)
      res = (res + bak_n * bak_n) % N;
  }
  return res;
}

int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    LL l, r;
    scanf("%lld%lld", &l, &r);
    printf("%d\n", mod(dp(r) - dp(l - 1), N));
  }
  return 0;
}