fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Fast counting of distinct S(x) = sorted digits of concat(x, x+1) for x=1..n
  5. // Complexity: O( sum_{m=1..L} C(m+8,8) * m * 9 ) ~ 4e6 for n up to 1e9
  6.  
  7. // Custom hash for array<int,10>
  8. struct ArrHash {
  9.     size_t operator()(array<int,10> const &a) const noexcept {
  10.         // FNV-like hash
  11.         uint64_t h = 146527;
  12.         for (int i = 0; i < 10; ++i) {
  13.             h = (h ^ a[i]) * 1099511628211ULL;
  14.         }
  15.         return (size_t)h;
  16.     }
  17. };
  18.  
  19. // Build the lexicographically smallest string of length 'len' from digit counts rem[0..9],
  20. // with the constraint that the first character is non-zero.
  21. string build_min_prefix(array<int,10> rem, int len) {
  22.     string s;
  23.     s.reserve(len);
  24.     // find smallest non-zero digit for first char
  25.     for (int d = 1; d <= 9; ++d) {
  26.         if (rem[d] > 0) {
  27.             s.push_back('0' + d);
  28.             rem[d]--;
  29.             break;
  30.         }
  31.     }
  32.     // then zeros
  33.     int zeros = rem[0];
  34.     for (int i = 0; i < zeros; ++i) s.push_back('0');
  35.     rem[0] = 0;
  36.     // then remaining digits in ascending order
  37.     for (int d = 1; d <= 9; ++d) {
  38.         while (rem[d] > 0) {
  39.             s.push_back('0' + d);
  40.             rem[d]--;
  41.         }
  42.     }
  43.     return s;
  44. }
  45.  
  46. int main(){
  47.     ios::sync_with_stdio(false);
  48.     cin.tie(nullptr);
  49.  
  50.     long long n;
  51.     cin >> n;
  52.     string n_str = to_string(n);
  53.     int L = n_str.size();
  54.  
  55.     // Count boundary cases: x = 10^m - 1, where 10^m -1 <= n
  56.     long long B = 0;
  57.     long long p = 10;
  58.     while (p - 1 <= n) {
  59.         B++;
  60.         if (p > n / 10) break;
  61.         p *= 10;
  62.     }
  63.  
  64.     long long total = B;
  65.     vector<long long> ten(L+2,1);
  66.     for (int i = 1; i <= L+1; ++i) ten[i] = ten[i-1] * 10;
  67.  
  68.     // For each digit-length m
  69.     for (int m = 1; m <= L; ++m) {
  70.         long long lo = ten[m-1];
  71.         long long up_full = ten[m] - 2;  // last full-block x
  72.         bool is_full = (n >= up_full);
  73.         if (!is_full && n < lo) break;  // no valid x of this digit-length
  74.  
  75.         unordered_set<array<int,10>, ArrHash> seen;
  76.         array<int,10> c;
  77.         c.fill(0);
  78.  
  79.         // recursive generation of c counts by combinations with replacement
  80.         function<void(int,int)> dfs = [&](int pos, int start) {
  81.             if (pos == m) {
  82.                 if (c[0] == m) return;  // would be leading zeros
  83.                 // for each run of trailing 9's
  84.                 for (int r = 0; r < m && c[9] >= r; ++r) {
  85.                     // for each digit to increment a
  86.                     for (int a = 0; a < 9; ++a) {
  87.                         if (c[a] == 0) continue;
  88.                         // feasibility: ensure non-zero MSB among rem
  89.                         int nz_rem = m - 1 - r;
  90.                         array<int,10> rem = c;
  91.                         rem[9] -= r;
  92.                         rem[a] -= 1;
  93.                         if (nz_rem > 0) {
  94.                             int sum_nz = 0;
  95.                             for (int d = 1; d <= 9; ++d) sum_nz += rem[d];
  96.                             if (sum_nz == 0) continue;
  97.                         } else {
  98.                             // r = m-1: only a is MSB
  99.                             if (a == 0) continue;
  100.                         }
  101.                         // if partial top block, ensure existence of x <= n
  102.                         if (!is_full && m == L) {
  103.                             string pref = build_min_prefix(rem, nz_rem);
  104.                             string x_str = pref + char('0'+a) + string(r, '9');
  105.                             // x_str length = m = L = n_str.size()
  106.                             if (x_str > n_str) continue;
  107.                         }
  108.                         // build combined digit-count tot
  109.                         array<int,10> tot;
  110.                         for (int i = 0; i < 10; ++i) tot[i] = 2 * c[i];
  111.                         tot[a]   -= 1;
  112.                         tot[a+1] += 1;
  113.                         tot[9]   -= r;
  114.                         tot[0]   += r;
  115.                         seen.insert(tot);
  116.                     }
  117.                 }
  118.                 return;
  119.             }
  120.             for (int d = start; d < 10; ++d) {
  121.                 c[d]++;
  122.                 dfs(pos+1, d);
  123.                 c[d]--;
  124.             }
  125.         };
  126.  
  127.         dfs(0, 0);
  128.         total += (long long)seen.size();
  129.     }
  130.  
  131.     cout << total << "\n";
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
1337
stdout
copy 
948
https://ideone.com/HnpWw5
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!