Contest1422/F2.cpp

#include <cstdio>
#include <cstring>

#define rr register
using namespace std;
using ll=long long;
ll dp[15][15], l, r;
int dig[15];

inline ll dfs(int dep, bool lim, bool ahe, int now, int sum) {
    rr ll ans = 0;
    if (!dep) return sum;
    if (!lim && ahe && dp[dep][sum] != -1) return dp[dep][sum];
    rr int mx = lim ? dig[dep] : 9;
    for (rr int i = 0; i <= mx; ++i)
        ans += dfs(dep - 1, lim && (i == mx), ahe || i, now, sum + ((ahe || i) && (i == now)));
    if (!lim && ahe) dp[dep][sum] = ans;
    return ans;
}

inline ll answ(ll x, int now) {
    memset(dp, -1, sizeof(dp));
    rr int len = 0;
    while (x)
        dig[++len] = x % 10, x /= 10;
    return dfs(len, 1, 0, now, 0);
}

signed main() {
    l = 1;
    scanf("%d", &r);
    for (rr int i = 0; i < 10; ++i)
        printf("%lld%c", answ(r, i) - answ(l - 1, i), i == 9 ? 10 : 32);
    return 0;
}