fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1LL << (n))
  6. #define TASK ""
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8. #define lc(n) (n << 1)
  9. #define rc(n) ((n << 1) | 1)
  10.  
  11. #define fi first
  12. #define se second
  13. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  14. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  15.  
  16. #define mii map<int,int>
  17. #define umi unordered_map<int, int>
  18. #define pii pair<int,int>
  19. #define vi vector<int>
  20.  
  21. using namespace std;
  22.  
  23. const int oo = 1e18;
  24. const int mod = 1e9 + 7;
  25. const int nmax = 2e5 + 8;
  26. const int base = 311;
  27.  
  28. int q, dp[19][2][2][2][2][2][2][2][2][2][2][2];
  29.  
  30. int sol(int pos, int ck, int d[], string &x){
  31.     if(pos == 19){
  32.         int cnt = 0;
  33.         for(int i = 0; i <= 9; ++i){
  34.             cnt += (d[i] & 1);
  35.         }
  36.         return cnt <= 1 && ck;
  37.     }
  38.     if(dp[pos][ck][d[1]][d[2]][d[3]][d[4]][d[5]][d[6]][d[7]][d[8]][d[9]][d[0]] != -1)
  39.         return dp[pos][ck][d[1]][d[2]][d[3]][d[4]][d[5]][d[6]][d[7]][d[8]][d[9]][d[0]];
  40.     int lim = 9;
  41. //    if(ok) lim = x[pos] - '0';
  42.     int cur = 0;
  43.     for(int i = 0; i <= lim; ++i){
  44.         if(ck || i != 0) d[i] ^= 1;
  45.         cur += sol(pos + 1, ck || (i != 0), d, x);
  46.         if(ck || i != 0) d[i] ^= 1;
  47.     }
  48.     return dp[pos][ck][d[1]][d[2]][d[3]][d[4]][d[5]][d[6]][d[7]][d[8]][d[9]][d[0]] = cur;
  49. }
  50. int calc(int pos, int ok, int ck, int d[], string &x){
  51.     if(pos == 19){
  52.         int cnt = 0;
  53.         for(int i = 0; i <= 9; ++i){
  54.             cnt += (d[i] & 1);
  55.         }
  56.         return cnt <= 1 && ck;
  57.     }
  58.     if(!ok) return sol(pos, ck, d, x);
  59.     int lim = x[pos] - '0';
  60.     int cur = 0;
  61.     for(int i = 0; i <= lim; ++i){
  62.         if(ck || i != 0) d[i] ^= 1;
  63.         cur += calc(pos + 1, ok & (i == lim), ck || (i != 0), d, x);
  64.         if(ck || i != 0) d[i] ^= 1;
  65.     }
  66.     return cur;
  67. }
  68. void add(string &x){
  69.     while(x.size() < 19){
  70.         x = "0" + x;
  71.     }
  72. }
  73. bool check(string &s){
  74.     int d[10];
  75.     memset(d, 0, sizeof d);
  76.     for(int i = 0; i < s.size(); ++i){
  77.         int x = s[i] - '0';
  78.         d[x]++;
  79.     }
  80.     int cnt = 0;
  81.     for(int i = 0; i <= 9; ++i){
  82.         cnt += (d[i] & 1);
  83.     }
  84.     return cnt <= 1;
  85. }
  86. int d[11];
  87. int range(string &x){
  88.     memset(d, 0, sizeof d);
  89.     return calc(0, 1, 0, d, x);
  90. }
  91. main(){
  92.     fast;
  93.     openfile();
  94.     cin >> q;
  95.     memset(dp, -1, sizeof dp);
  96.     while(q--){
  97.         string l, r;
  98.         cin >> l >> r;
  99.         int v = check(l);
  100.         add(l), add(r);
  101.         memset(d, 0, sizeof d);
  102.         cout << range(r) - range(l) + v << '\n';
  103.     }
  104. }
  105.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4aIcan
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!