Number of Beautiful Integers in the Range

You are given positive integers low, high, and k.

A number is beautiful if it meets both of the following conditions:

The count of even digits in the number is equal to the count of odd digits.
The number is divisible by k.

Return the number of beautiful integers in the range [low, high].

Example 1:

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

Example 2:

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

Example 3:

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

Constraints:

0 < low <= high <= 10⁹
0 < k <= 20

解题思路

　　一碰到数位dp就谔谔，昨晚硬是磨了一个多小时都没做出来，然后今天调了一早上才过了，被傻逼lc的评测机制气乐了。

　　数位dp我一直都用递推去做的，记忆化搜索一直没学会。当时想状态定义的时候就想了很久，现在的总结就是其实只用关注从最高位往低位递推时会用到哪些特定的数，然后把需要的状态定义出来就好了，比如说最基本的数位的个数，最高位是哪一个数，然后是其他特性比如这题中奇偶数位分别有多少，整个数模$k$是多少。

　　定义状态$f(i,j,u,v,w)$表示所有数位大小为$i$，最高位是$j$，奇数数位有$u$个，偶数数位有$v$个，整个数模$k$为$w$的数的个数。很明显数位大小为$i$的数可以转移到数位大小为$i+1$的数，因此当前状态$f(i,j,u,v,w)$可以转移到的状态就有$$\left\{ \begin{array}{c} f \left(i+1, \ x, \ u+1, \ v, \ (x \cdot {10}^i + w) \bmod k \right) \quad x \in \{ 1,3,5,7,9 \} \\ f \left(i+1, \ x, \ u, \ v+1, \ (x \cdot {10}^i + w) \bmod k \right) \quad x \in \{ 0,2,4,6,8 \} \end{array} \right.$$

　　然后递推的时候求的是$1 \sim x$中有多少个数满足条件，先把$x$中的每一个数分离出来，然后从最高位开始往底位枚举。只有$x$的数位大小为偶数时才能递推，因为要求奇偶数位相同，并且在递推时要保证没有前导$0$（前导$0$会印象奇偶数位的数目），最后再把那些含前导$0$的数补上即可。递推时需要开变量分别记录前面已确认的数的奇数数位和偶数数位有多少，以及组成的数在十进制中模$k$是多少。

　　最后因为lc的逆天评测机制，如果对于每个样例都跑dp预处理那么肯定会TLE，因此需要把预处理的结果记录到全局变量中，这样只用跑一次即可，不过需要把$1 \leq k \leq 20$所有情况都跑一遍，预处理的计算量大概是$20 \times 10 \times 10 \times 6 \times 6 \times 20 \times 10 \approx {10}^7$。

　　AC代码如下：

 1 vector<vector<vector<vector<vector<vector<int>>>>>> f;
 2 
 3 class Solution {
 4 public:
 5     void init() {
 6         f = vector<vector<vector<vector<vector<vector<int>>>>>>(21, vector<vector<vector<vector<vector<int>>>>>(11, vector<vector<vector<vector<int>>>>(10, vector<vector<vector<int>>>(6, vector<vector<int>>(6, vector<int>(20))))));
 7         for (int k = 1; k <= 20; k++) {
 8             vector<int> p(10);
 9             p[0] = 1 % k;
10             for (int i = 1; i < 10; i++) {
11                 p[i] = p[i - 1] * 10 % k;
12             }
13             for (int i = 0; i <= 9; i++) {
14                 if (i & 1) f[k][1][i][1][0][i % k] = 1;
15                 else f[k][1][i][0][1][i % k] = 1;
16             }
17             for (int i = 1; i < 10; i++) {
18                 for (int j = 0; j <= 9; j++) {
19                     for (int u = 0; u <= 5; u++) {
20                         for (int v = 0; v <= 5; v++) {
21                             for (int w = 0; w < k; w++) {
22                                 for (int x = 0; x <= 9; x++) {
23                                     if (x % 2 && u + 1 <= 5) f[k][i + 1][x][u + 1][v][(x * p[i] + w) % k] += f[k][i][j][u][v][w];
24                                     else if (x % 2 == 0 && v + 1 <= 5) f[k][i + 1][x][u][v + 1][(x * p[i] + w) % k] += f[k][i][j][u][v][w];
25                                 }
26                             }
27                         }
28                     }
29                 }
30             }
31         }
32     }
33     
34     int numberOfBeautifulIntegers(int low, int high, int k) {
35         if (f.empty()) init();
36         vector<int> p(10);
37         p[0] = 1 % k;
38         for (int i = 1; i < 10; i++) {
39             p[i] = p[i - 1] * 10 % k;
40         }
41         function<int(int)> get = [&](int x) {
42             if (!x) return 0;
43             vector<int> q;
44             while (x) {
45                 q.push_back(x % 10);
46                 x /= 10;
47             }
48             int ret = 0, odd = 0, even = 0, s = 0;
49             if (~q.size() & 1) {
50                 int t = q.size() >> 1;
51                 for (int i = q.size() - 1; i >= 0; i--) {
52                     for (int j = i == q.size() - 1; j < q[i]; j++) {
53                         ret += f[k][i + 1][j][t - odd][t - even][(k - s) % k];
54                     }
55                     if (q[i] & 1) odd++;
56                     else even++;
57                     if (odd > t || even > t) break;
58                     s = (s + q[i] * p[i]) % k;
59                     if (!i && odd == even && !s) ret++;
60                 }
61             }
62             for (int i = 1; i < q.size(); i++) {
63                 if (~i & 1) {
64                     for (int j = 1; j <= 9; j++) {
65                         ret += f[k][i][j][i >> 1][i >> 1][0];
66                     }
67                 }
68             }
69             return ret;
70         };
71         return get(high) - get(low - 1);
72     }
73 };

　　这题还可以用暴搜，可以发现只有数位大小为偶数的数才能满足奇数数位和偶数数位的数目相同，因此可以暴搜出来这些数，实际上大概有$2 \times {10}^7$个左右。然后在暴搜的时候要保证搜到的数有序，对于$\text{low}$和$\text{high}$二分出可选数的区间，然后再逐个枚举是否模$k$为$0$即可。详细见参考资料，这里就不写了，比赛很少会这样做，一般都直接数位dp。