abc336 E - Digit Sum Divisible 题解 数位DP

题目链接：https://atcoder.jp/contests/abc336/tasks/abc336_e

题目大意：

我们定义一个整数 \(n\) 的 数位和 为 \(n\) 的十进制表示中的各位上的数字之和。比如：整数 \(2024\) 的数位和为 \(2 + 0 + 2 + 4 = 8\)。

一个正整数 \(n\) 被称作一个 好数 如果 \(n\) 能被它的数位和整除。举例，\(2024\) 是好数，因为它能被它的数位和 \(8\) 整除。

给你一个整数 \(N(1 \le N \le 10^{14})\)，请你计算有多少 \(\le N\) 的好数。

输入 \(N\)，输出 \(\le N\) 的好数个数。

解题思路：

枚举数位和 \(X\)（\(X\) 最大也就 \(14 \times 9\)），然后对于每一个 \(X\)，做一遍数位DP。

定义状态 \(f_{p, x, y}\) 表示当前在第 \(p\) 位，到第 \(p\) 位为止的数模 \(X\) 为 \(x\)，到第 \(p\) 位为止的数的数位和为 \(y\) 对应的数字个数。

则最终（边界条件）只有当 \(p = -1\) 时，只有 \(x = 0\) 且 \(y = X\) 的状态对应的个数为 \(1\)。

示例程序：

#include <bits/stdc++.h>
using namespace std;

int a[22], X;
// f[p][x][y] 第 p 为，模 X = x，数位和 y
long long N, ans, f[22][140][140][2];
bool vis[22][140][140][2];

long long dfs(int p, int x, int y, bool limit) {
    if (p < 0) {
        return x == 0 && y == X;
    }
    if (vis[p][x][y][limit]) return f[p][x][y][limit];
    vis[p][x][y][limit] = true;
    long long &res = f[p][x][y][limit];
    res = 0;
    int up = limit ? a[p] : 9;
    for (int i = 0; i <= up; i++) {
        int xx = (x * 10 + i) % X, yy = y + i;
        res += dfs(p-1, xx, yy, limit && i == up);
    }
    return res;
}

long long cal(long long num) {
    memset(vis, 0, sizeof vis);
    int p = 0;
    while (num) {
        a[p++] = num % 10;
        num /= 10;
    }
    return dfs(p-1, 0, 0, 1);
}

int main() {
    scanf("%lld", &N);
    for (X = 1; X <= 14 * 9; X++)
        ans += cal(N);
    printf("%lld\n", ans);
    return 0;
}