1234567891011121314151617181920212223242526272829303132333435 |
- #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;
- }
|