https://www.acwing.com/problem/content/description/340/
It’s the first time to do this kind of numbering, and it feels like it is the same in theory , The return is not 1 but his contribution.
It is reasonable to pay attention to 0, but there is no 0 in the title. After all, 0 is very special. It is all leading 0 but also contributes 1 0.
#includeusing namespace std;typedef long long ll;int a[40];ll dp[10][40][40];ll dfs (int id, int pos, int s1, bool lead, bool limit) {if(pos == -1) {return s1;} if(!limit && !lead && dp[id][pos][s1] != -1) return dp[id][pos][s1]; int up = limit? A[pos]: 9; ll ans = 0; for(int i = 0; i <= up; i++) {int ns1 = s1 + (i == id); if(id == 0) ns1 = s1 + ((i == id) && (!lead)); ans += dfs(id, pos-1, ns1, lead && i == 0, limit && i == a[pos]);} if(!limit && !lead) dp[id][pos][s1] = ans; return ans;}ll ans[10];void solve( ll x) {memset(ans, 0, sizeof(ans)); if(x <= 0) return; int pos = 0; while(x) {a[pos++] = x% 10; x /= 10;} for(int id = 0; id <= 9; ++id) ans[id] = dfs(id, pos-1, 0, true, true);}void solve2(ll x) {if(x <= 0 ) return; int pos = 0; while(x) {a[pos++] = x% 10; x /= 10;} for(int id = 0; id <= 9; ++id) ans[id] -= dfs(id, pos-1, 0, true, true);}int main() {#ifdef Yinku freopen("Yinku .in", "r", stdin);#endif memset(dp, -1, sizeof(dp)); ll le, ri; while(~scanf("%lld%lld", &le, &ri)) {if (le == 0 && ri == 0) break; if(le> ri) swap(le, ri); solve(ri); solve2(le-1); for(int id = 0; id <= 9; ++id) {printf("%lld%c", ans[id], " "[id == 9]);} }}