DP

数位DP

洛谷P2602

dp[n][n][2][2]: pos, cnt, is_zero, is_limit

pos: 在哪一位

cnt: 这个数多少个要求数位

is_zero: true为前面全是前导0

is_limit: true为有约束限制，即本位最高多少

LL calc(LL x, int dight) {
    auto s = std::to_string(x);
    int n = s.size();
    std::vector dp(n, std::vector(n, std::vector(2, std::vector<LL>(2, -1))));
    auto dfs = [&](auto self, int pos, LL cnt, bool is_limit, bool is_zero) -> LL {
        if (pos == n) {
            return cnt;
        }
        if (dp[pos][cnt][is_zero][is_limit] != -1) {
            return dp[pos][cnt][is_zero][is_limit];
        }
        LL ans = 0;
        for (int i = 0; i <= (is_limit ? s[pos] - '0' : 9); i++) {
            if (is_zero && i == 0) {
                ans += self(self, pos + 1, cnt, is_limit && i == s[pos] - '0', true);
            } else {
                ans += self(self, pos + 1, cnt + (i == dight), is_limit && i == s[pos] - '0', false);
            }
        }
        dp[pos][cnt][is_zero][is_limit] = ans;
        return ans;
    };

    return dfs(dfs, 0, 0, true, true);

}

void solve() {
    LL l, r;
    std::cin >> l >> r;
    for (int i = 0; i < 10; i++) {
        std::cout << calc(r, i) - calc(l - 1, i) << " \n"[i == 9];
    }
}