fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int ll;
  7.  
  8. map<vector<int>, ll> dp;
  9.  
  10. ll a[12], n;
  11.  
  12. bool is_cool(int arr[10]){
  13.     /*for(int j = 0; j < 10; j++)
  14.         cout << arr[j] << " ";
  15.     cout << endl;*/
  16.  
  17.     int len = 0, x[10], tot = 0;
  18.     for(int j = 1; j < 10; j++)
  19.         while(arr[j]--){
  20.             x[len++] = j;
  21.             tot += j;
  22.         }
  23.     if(tot % 2 != 0) return 0;
  24.  
  25.     int up = (1 << len);
  26.     for(int j = 0; j < up; j++){
  27.         int cur = 0;
  28.         for(int k = 0; k < len; k++)
  29.             if((1 << k)&j) cur += x[k];
  30.         if(cur == tot/2) return 1;
  31.     }
  32.     return 0;
  33. }
  34.  
  35. ll foo(int pos, int arr[10], int tight){
  36.     //cout << pos << " " << tight << endl;
  37.     if(pos >= n){
  38.         int temp[10];
  39.         for(int j = 0; j < 10; j++)
  40.             temp[j] = arr[j];
  41.         int t = is_cool(temp);
  42.         //cout << t << endl;
  43.         return t+1;
  44.     }
  45.  
  46.     vector<int> curr;
  47.     curr.pb(pos);
  48.     for(int j = 0; j < 10; j++)
  49.         curr.pb(arr[j]);
  50.     curr.pb(tight);
  51.  
  52.     if(dp[curr]) return dp[curr];
  53.  
  54.     ll ans = 1;
  55.     int last = (tight == 1)? a[pos] : 9, st = (pos == 0)? 1 : 0;
  56.     for(int j = st; j <= last; j++){
  57.         arr[j]++;
  58.         ll cur = foo(pos+1, arr, (tight && j == last)? 1 : 0);
  59.         arr[j]--;
  60.         ans += (cur - 1);
  61.     }
  62.     //cout << pos << " " << tight << endl;
  63.     dp[curr] = ans;
  64.     return ans;
  65. }
  66.  
  67. int main(){
  68.     ll x, y;
  69.     cin >> x >> y;
  70.     while(x != 0 && y != 0){
  71.         x--;
  72.         ll ans1 = 0, ans2 = 0;
  73.         int arr[10] = {0};
  74.  
  75.         if(x != 0){
  76.             dp.clear();
  77.             n = 0;
  78.             while(x){
  79.                 a[n++] = x % 10;
  80.                 x /= 10;
  81.             }
  82.             for(int j = 0; j < n/2; j++)
  83.                 swap(a[j], a[n - j - 1]);
  84.             ans1 = foo(0, arr, 1);
  85.             ans1--;
  86.             int len = n;
  87.             for(int j = 1; j < len; j++){
  88.                 n = j;
  89.                 dp.clear();
  90.                 memset(arr, 0, sizeof(arr));
  91.                 ans1 += (foo(0, arr, 0) - 1);
  92.             }
  93.             //cout << ans1 << " ";
  94.         }
  95.         dp.clear();
  96.         memset(arr, 0, sizeof(arr));
  97.         n = 0;
  98.         while(y){
  99.             a[n++] = y % 10;
  100.             y /= 10;
  101.         }
  102.         for(int j = 0; j < n/2; j++)
  103.             swap(a[j], a[n - j - 1]);
  104.         ans2 = foo(0, arr, 1);
  105.         ans2 --;
  106.         int len = n;
  107.         for(int j = 1; j < len; j++){
  108.             n = j;
  109.             dp.clear();
  110.             memset(arr, 0, sizeof(arr));
  111.             ans2 += (foo(0, arr, 0) - 1);
  112.         }
  113.         //cout << ans2 << endl;
  114.  
  115.         cout << (ans2 - ans1) << endl;
  116.  
  117.         cin >> x >> y;
  118.     }
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.55s 7120KB
comments (?)
stdin
copy 
1 11
12 20
1 20
3 100
6354 234363
123456789 234567891
0 0
stdout
copy 
1
0
1
9
82340
54801678
https://ideone.com/qw9NDK
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!