fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i128 = __int128_t;
  5. using u128 = __uint128_t;
  6.  
  7. struct DPCacheItem {
  8.     bool ok = false;
  9.     i128 total = 0;
  10.     array<i128,10> cnt{};
  11. };
  12.  
  13. struct DigitDP {
  14.     string s;
  15.     vector<array<array<DPCacheItem,2>,2>> memo; // [pos][tight][started]
  16.     DigitDP(long long M) { s = (M < 0) ? string("0") : to_string(M);
  17.                            memo.assign(s.size()+1, {}); }
  18.  
  19.     pair<i128, array<i128,10>> solve(int pos, int tight, int started){
  20.         auto &cell = memo[pos][tight][started];
  21.         if (cell.ok) return {cell.total, cell.cnt};
  22.         if (pos == (int)s.size()){
  23.             array<i128,10> z{}; z.fill(0);
  24.             // nếu chưa bắt đầu, đây là số 0 -> đếm một '0'
  25.             if (!started) z[0] = 1;
  26.             cell.ok = true; cell.total = 1; cell.cnt = z;
  27.             return {cell.total, cell.cnt};
  28.         }
  29.         int limit = tight ? (s[pos]-'0') : 9;
  30.         i128 total = 0; array<i128,10> cnt{}; cnt.fill(0);
  31.         for(int d=0; d<=limit; ++d){
  32.             int ntight = tight && (d == limit);
  33.             int nstarted = started || (d != 0);
  34.             auto [t2, c2] = solve(pos+1, ntight, nstarted);
  35.             total += t2;
  36.             if (nstarted) cnt[d] += t2;           // đặt chữ số d (không phải số 0 vô nghĩa ở đầu)
  37.             for(int dd=0; dd<10; ++dd) cnt[dd] += c2[dd];
  38.         }
  39.         cell.ok = true; cell.total = total; cell.cnt = cnt;
  40.         return {total, cnt};
  41.     }
  42.  
  43.     array<i128,10> run(){
  44.         if (s == "0"){ array<i128,10> z{}; z.fill(0); return z; }
  45.         return solve(0, 1, 0).second;
  46.     }
  47. };
  48.  
  49. array<i128,10> counts_digits_0_to(long long M){
  50.     if (M < 0){ array<i128,10> z{}; z.fill(0); return z; }
  51.     return DigitDP(M).run();
  52. }
  53.  
  54. // đếm từ 0..N với chữ số hàng đơn vị có parity p (p=0 chẵn, 1 lẻ)
  55. array<i128,10> count_up_to_parity(long long N, int p){
  56.     array<i128,10> total{}; total.fill(0);
  57.     if (N < 0) return total;
  58.     for(int u=0; u<10; ++u){
  59.         if ((u&1) != p || N < u) continue;
  60.         long long M = (N - u)/10;           // t chạy 0..M
  61.         auto prefix = counts_digits_0_to(M);
  62.         prefix[0] -= 1;                     // loại đóng góp của t=0 ở phần tiền tố
  63.         i128 cnt_u = (i128)M + 1;           // số lần xuất hiện ở hàng đơn vị
  64.         prefix[u] += cnt_u;
  65.         for(int d=0; d<10; ++d) total[d] += prefix[d];
  66.     }
  67.     return total;
  68. }
  69.  
  70. array<i128,10> count_interval_parity(long long a, long long b, int p){
  71.     auto R = count_up_to_parity(b, p);
  72.     auto L = count_up_to_parity(a-2, p);
  73.     array<i128,10> ans{};
  74.     for(int d=0; d<10; ++d) ans[d] = R[d] - L[d];
  75.     return ans;
  76. }
  77.  
  78. string to_string_i128(i128 x){
  79.     if (x == 0) return "0";
  80.     bool neg = x < 0; u128 v = neg ? -(u128)x : (u128)x;
  81.     string s;
  82.     while(v){ s.push_back('0' + int(v%10)); v/=10; }
  83.     if (neg) s.push_back('-');
  84.     reverse(s.begin(), s.end());
  85.     return s;
  86. }
  87.  
  88. int main(){ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.     long long k; unsigned long long n;
  91.     if(!(cin >> k >> n)) return 0;
  92.     __int128 b128 = ( __int128)k + 2 * ( (__int128)n - 1 );
  93.     long long b = (long long)b128;          // an toàn với k,n ≤ 1e18
  94.     int p = ( (k % 2) + 2 ) % 2;
  95.     auto ans = count_interval_parity(k, b, p);
  96.     for(int d=0; d<10; ++d){
  97.         if (d) cout << ' ';
  98.         cout << to_string_i128(ans[d]);
  99.     }
  100.     cout << "\n";
  101.     return 0;
  102. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
19 97
stdout
copy 
11 77 16 29 10 29 10 29 10 30
https://ideone.com/KT5fik
language:
C++14 (gcc 8.3)
created:
6 hours 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!