fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     long long ways;
  6.     long long cnt[10];
  7. };
  8.  
  9. struct DigitDP {
  10.     // dp[pos][tight][started]
  11.     Node memo[20][2][2];
  12.     char vis[20][2][2];
  13.     string s;
  14.     int nlen;
  15.     int targetParity;
  16.  
  17.     static Node zeroNode() {
  18.         Node t; t.ways = 0;
  19.         for (int i = 0; i < 10; ++i) t.cnt[i] = 0;
  20.         return t;
  21.     }
  22.  
  23.     static Node addNode(const Node& a, const Node& b) {
  24.         Node r; r.ways = a.ways + b.ways;
  25.         for (int d = 0; d < 10; ++d) r.cnt[d] = a.cnt[d] + b.cnt[d];
  26.         return r;
  27.     }
  28.  
  29.     Node dfs(int pos, int tight, int started) {
  30.         if (pos == nlen) {
  31.             Node base = zeroNode();
  32.             base.ways = 1; // đã hình thành 1 số
  33.             return base;
  34.         }
  35.         if (vis[pos][tight][started]) return memo[pos][tight][started];
  36.         vis[pos][tight][started] = 1;
  37.  
  38.         Node res = zeroNode();
  39.         int lim = tight ? (s[pos] - '0') : 9;
  40.         int lastPos = (pos == nlen - 1);
  41.  
  42.         for (int d = 0; d <= lim; ++d) {
  43.             int ntight = tight && (d == lim);
  44.             int nstarted = started || (d != 0);
  45.  
  46.             // Ràng buộc chẵn/lẻ ở chữ số cuối
  47.             if (lastPos) {
  48.                 if (!nstarted) {
  49.                     // số là 0
  50.                     if ((0 % 2) != targetParity) continue;
  51.                 } else {
  52.                     if ((d % 2) != targetParity) continue;
  53.                 }
  54.             }
  55.  
  56.             Node child = dfs(pos + 1, ntight, nstarted);
  57.  
  58.             // Ghi nhận đóng góp của chữ số tại vị trí này
  59.             if (nstarted) {
  60.                 // đã bắt đầu, d thật sự xuất hiện
  61.                 if (child.ways != 0) child.cnt[d] += child.ways;
  62.             } else if (lastPos) {
  63.                 // số 0 (chưa từng start) -> có một chữ số '0'
  64.                 if (child.ways != 0) child.cnt[0] += child.ways;
  65.             }
  66.  
  67.             res = addNode(res, child);
  68.         }
  69.         memo[pos][tight][started] = res;
  70.         return res;
  71.     }
  72.  
  73.     // Đếm số lần xuất hiện mỗi chữ số trong các số <= bound
  74.     // mà chữ số cuối cùng có parity = targetParity
  75.     void solve(long long bound, int parity, long long outCnt[10]) {
  76.         for (int d = 0; d < 10; ++d) outCnt[d] = 0;
  77.         if (bound < 0) return; // rỗng
  78.  
  79.         targetParity = parity & 1;
  80.         s = to_string(bound);
  81.         nlen = (int)s.size();
  82.         memset(vis, 0, sizeof(vis));
  83.         Node ans = dfs(0, 1, 0);
  84.         for (int d = 0; d < 10; ++d) outCnt[d] = ans.cnt[d];
  85.     }
  86. };
  87.  
  88. int main() {
  89.     ios::sync_with_stdio(false);
  90.     cin.tie(nullptr);
  91.  
  92.     long long k, n;
  93.     if (!(cin >> k >> n)) return 0;
  94.  
  95.     if (n <= 0) {
  96.         for (int d = 0; d < 10; ++d) {
  97.             cout << 0 << (d == 9 ? '\n' : ' ');
  98.         }
  99.         return 0;
  100.     }
  101.  
  102.     long long L = k;
  103.     long long R;// R = k + 2*(n-1) (cẩn thận tràn nhưng theo đề chỉ dùng long long)
  104.     R = k + 2 * (n - 1);
  105.  
  106.     if (L > R) swap(L, R);
  107.  
  108.     DigitDP dp;
  109.     int parity = ((k % 2) + 2) % 2;
  110.  
  111.     long long cntR[10], cntLm2[10], ans[10];
  112.     dp.solve(R, parity, cntR);
  113.  
  114.     long long cntTmp[10] = {0};
  115.     if (L - 2 >= 0) {
  116.         dp.solve(L - 2, parity, cntLm2);
  117.     } else {
  118.         for (int d = 0; d < 10; ++d) cntLm2[d] = 0;
  119.     }
  120.  
  121.     for (int d = 0; d < 10; ++d) {
  122.         long long v = cntR[d] - cntLm2[d];
  123.         ans[d] = v;
  124.     }
  125.  
  126.     for (int d = 0; d < 10; ++d) {
  127.         cout << ans[d] << (d == 9 ? '\n' : ' ');
  128.     }
  129.     return 0;
  130. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
19 97
stdout 
10 77 16 29 10 29 10 29 10 30
https://ideone.com/HqaBug
language:
C++14 (gcc 8.3)
created:
4 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!