「AHOI2009」同类分布 - 数位 DP

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

给出两个数 \(a,b\)，求出 \([a, b]\) 中各位数字之和能整除原数的数的个数。

数据范围：\(1 \le a \le b \le 10^{18}\)

解题思路

本题显然数位 DP。可转化为求小于等于 \(n\) 的各位数字之和能整除原数的数的个数。直接求本题所问过于困难，可以拆分为求各数位和为 \(\text{sum}\) 且该数可被 \(\text{sum}\) 整除的数的个数，然后枚举可行的 \(\text{sum}\) 即可。

在有 \(\text{sum}\) 限制下，我们设 \(f_{i, s, m, c}\) 表示遍历到第 \(i\) 位，前 \(i - 1\) 位数字和为 \(s\)，且当前数 \(\mod \text{sum}\) 的余数为 \(m\) 情况下的满足条件的数的个数。\(c\) 表示前 \(i\) 位是否达到 \(n\) 的上限：\(0\) 表示未达到，\(1\) 表示达到。假设 \(k\) 为第 \(i\) 位数组（\(c = 0\) 则 \(0 \le k \le 9\)，\(c = 1\) 则 \(0 \le k \le n_i\)）（\(n_i\) 表示 \(n\) 的第 \(i\) 位），于是我们可以推出以下方程：

\[ f_{i + 1, s + k, (m \times 10 + k) \bmod \text{sum}, [c = 1 \wedge k = n_{i + 1}]} = f_{i + 1, s + k, (m \times 10 + k) \bmod \text{sum}, [c = 1 \wedge k = n_{i + 1}]} + f_{i, s, m, c} \]

最后我们只需要初始化 \(f_{i, s, m, c} = [i = 0 \wedge s = 0 \wedge m = 0 \wedge c = 1]\)，然后对于每个 \(\text{sum}\)，我们将 \(f_{n, \text{sum}, 0, 0} + f_{n, \text{sum}, 0, 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
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

const int MAXN = 20;

inline long long solve(long long k) {
    int n = 0;
    std::vector<int> bit = { 0 };
    for (; k; k /= 10, n++) bit.push_back(k % 10);
    std::reverse(bit.begin() + 1, bit.end());

    static long long f[MAXN][9 * MAXN][9 * MAXN][2];
    long long ans = 0;

    for (int sum = 1; sum <= n * 9; sum++) {
        memset(f, 0, sizeof(f));
        f[0][0][0][1] = 1;

        for (int i = 0; i < n; i++) {
            for (int s = 0; s <= sum; s++) {
                for (int m = 0; m < sum; m++) {
                    for (int c = 0; c <= 1; c++) {
                        if (f[i][s][m][c]) {
                            for (int k = 0; k <= (c ? bit[i + 1] : 9); k++) {
                                if (s + k > sum) break;
                                f[i + 1][s + k][(m * 10 + k) % sum][c && (k == bit[i + 1])] += f[i][s][m][c];
                            }
                        }
                    }
                }
            }
        }

        ans += f[n][sum][0][0] + f[n][sum][0][1];
    }

    return ans;
}

int main() {
    long long l, r;

    scanf("%lld %lld", &l, &r);

    printf("%lld\n", solve(r) - solve(l - 1));

    return 0;
}