fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef loc
  5.     #include "loc_debug.h"
  6. #else
  7.     #define pr(...)
  8.     #define pra(a,n)
  9.     #define praa(a,n,m)
  10.     #define prl()
  11. #endif
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15. #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  16. #define mp make_pair
  17. #define pb push_back
  18. #define eb emplace_back
  19. #define all(x) (x).begin(), (x).end()
  20. #define sz(a) int(a.size())
  21. #define rep(i, s, n)  for(int i = s; i <= n; ++i)
  22. #define rev(i, n, s)  for(int i = n; i >= s; --i)
  23. #define fore(x, a) for(auto &&x : a)
  24. #define fill(a, x) memset((a), (x), sizeof(a))
  25. #define tcase int __t; cin >> __t; rep(tc, 1, __t)
  26. #define F first
  27. #define S second
  28. #define gc getchar
  29.  
  30. const int mod = 1000000007;
  31. #define _ %mod
  32. const int N = 100005;
  33.  
  34. vector<vector<int>> a;
  35. bool canp[N];
  36.  
  37.  
  38. bool can(vector<int> b) {
  39.     int sum = 0;
  40.     fore(x, b) {
  41.         sum += x;
  42.     }
  43.     if(sum & 1) {
  44.         return 0;
  45.     }
  46.     vector<bool> v(sum / 2 + 1, 0);
  47.     v[0] = 1;
  48.     fore(x, b) {
  49.         rev(i, sum / 2, x) {
  50.             v[i] = v[i] || v[i - x];
  51.         }
  52.     }
  53.     return v[sum / 2];
  54. }
  55.  
  56. void go(int sum, vector<int> b) {
  57.     a.eb(b);
  58.     if(sz(b) >= 10) {
  59.         return;
  60.     }
  61.     rep(i, b.empty() ? 1 : b.back(), 9) {
  62.         if(sum + i > 84) {
  63.             break;
  64.         }
  65.         vector<int> c(b);
  66.         c.eb(i);
  67.         go(sum + i, c);
  68.     }
  69. }
  70.  
  71. int dp[11][2][N];
  72. int b[11];
  73. map<ll, int> lb;
  74. int ns[N][10];
  75.  
  76. int dodp(int p, bool c, int w) {
  77.     if(p == -1) {
  78.         return canp[w];
  79.     }
  80.     int &res = dp[p][c][w];
  81.     if(res == -1) {
  82.         res = 0;
  83.         rep(i, 0, 9) {
  84.             if(c || (i <= b[p])) {
  85.                 res += dodp(p - 1, c || (i < b[p]), ns[w][i]);
  86.             }
  87.         }
  88.     }
  89.     return res;
  90. }
  91.  
  92. int count(ll x) {
  93.     fill(dp, -1);
  94.     rep(i, 0, 10) {
  95.         b[i] = int(x % 10);
  96.         x /= 10;
  97.     }
  98.     int res = dodp(10, 0, 0);
  99.     return res;
  100. }
  101.  
  102. int main() {
  103.     fast_io;
  104.     go(0, vector<int>());
  105.     sort(all(a));
  106.     rep(i, 0, sz(a) - 1) {
  107.         canp[i] = can(a[i]);
  108.     }
  109.     rev(i, sz(a) - 1, 0) {
  110.         ll cur = 0;
  111.         rep(j, 0, sz(a[i]) - 1) {
  112.             cur = 10 * cur + a[i][j];
  113.         }
  114.         lb[cur] = i;
  115.     }
  116.     rep(i, 0, sz(a) - 1) {
  117.         rep(k, 0, 9) {
  118.             ll cur = 0;
  119.             bool done = 0;
  120.             if(k == 0) {
  121.                 done = 1;
  122.             }
  123.             rep(j, 0, sz(a[i]) - 1) {
  124.                 cur *= 10;
  125.                 if((!done) && k <= a[i][j]) {
  126.                     cur += k;
  127.                     cur *= 10;
  128.                     done = 1;
  129.                 }
  130.                 cur += a[i][j];
  131.             }
  132.             if(!done) {
  133.                 cur = 10 * cur + k;
  134.             }
  135.             if(lb.find(cur) != lb.end()) {
  136.                 ns[i][k] = lb[cur];
  137.             }
  138.         }
  139.     }
  140.     while(true) {
  141.         ll l, r;
  142.         cin >> l >> r;
  143.         if(l == 0 || r == 0) {
  144.             break;
  145.         }
  146.         cout << count(r)  - count(l - 1) << endl;
  147.     }
  148.     return 0;
  149. }
  150.  
Success #stdin #stdout 0.19s 27220KB
comments (?)
stdin
copy 
1 4000000000
1 4000000000
0 0
stdout
copy 
1979516311
1979516311
https://ideone.com/wHAL6j
language:
C++14 (gcc 8.3)
created:
6 years 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!