[Spoj] BALNUM - Balanced Numbers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : BALNUM - Balanced Numbers
Source            : Spoj
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted

 
#include "bits/stdc++.h"
 
using namespace std;
 
#define FI              freopen("in.txt", "r", stdin)
#define FO              freopen("out.txt", "w", stdout)
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define FOR(i, n)       for (int i = 1; i <= n; i++)
#define For(i, n)       for (int i = 0; i < n; i++)
#define ROF(i, n)       for (int i = n; i >= 1; i--)
#define Rof(i, n)       for (int i = n-1; i >= 0; i--)
#define FORI(i, n)      for (auto i : n)
#define eb              emplace_back
#define ll              long long
#define ull             unsigned long long
#define All(a)          a.begin(), a.end()
#define endl            '\n'
#define lb              lower_bound
#define mod             1000000007
 
inline int setbit(int mask, int pos)      { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)    { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)   { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)   { return (bool)(mask & (1 << pos)); }
 
static const int maxn = 1e3 + 5;
static const int logn = 18;
 
ull dp[22][1100][1100];
bool memoize[22][1100][1100];
int a[22];
 
 
inline ull solve(int pos, int mask = 0, int usedbit = 0, bool flag = 1, bool take = 0)
{
      if (pos < 0)
      {
            For(i, 10)
            {
                  if (i&1) // odd digit
                  {
                        if (checkbit(usedbit, i) && checkbit(mask, i)) return 0;
                  }
                  else // even digit
                  {
 
                        if (checkbit(usedbit, i) && !checkbit(mask, i)) return 0;
                  }
            }
            return 1;
      }
      ull &ret = dp[pos][mask][usedbit];
      bool &mem = memoize[pos][mask][usedbit];
      if (!flag && take && mem) return ret;
      int loop = 9;
      if (flag) loop = a[pos];
      ull sum = 0;
      For(i, loop+1)
      {
            if (!take && i == 0) sum += solve(pos-1, 0, 0, 0);
            else sum += solve(pos-1, togglebit(mask, i), setbit(usedbit, i), flag & i == a[pos], 1);
      }
      if (!flag && take) mem = 1, ret = sum;
      return sum;
}
 
inline ull solveDP(ull num)
{
      int len = 0;
      while (num)
      {
            a[len++] = num % 10;
            num /= 10;
      }
      return solve(len-1, 0, 0, 1, 0);
}
 
int main()
{
      //FI;
      memset(memoize, 0, sizeof memoize);
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            ull num1, num2;
            cin >> num1 >> num2;
            ull ans = solveDP(num2) - solveDP(num1-1);
            cout << ans << endl;
      }
}