[Light OJ] 1032 - Fast Bit Calculations

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1032 - Fast Bit Calculations
Source            : Light Online Judge
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted
Type - 2

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll               long long
 
ll dp[35][4][2][35];
bool memoize[35][4][2][35];
 
inline ll compute(int pre, int now)
{
      return pre == 1 && now == 1;
}
 
inline ll solve(string &a, int limit, int indx = 0, int small = 0, int pre = 0, int adj = 0)
{
      if (indx >= limit) return adj;
      ll &ret = dp[indx][small][pre][adj];
      bool &mem = memoize[indx][small][pre][adj];
      if (mem) return ret;
      mem = 1;
      int loop = 1;
      int num = a[indx] - '0';
      if (small == 0) loop = num;
      ll sum = 0;
      for (int i = 0; i <= loop; i++)
      {
            int newSmall = small | (i < num);
            sum += solve(a, limit, indx+1, newSmall, i, adj + compute(pre, i));
      }
      return ret = sum;
}
 
inline string toBin(ll num)
{
      if (num == 0) return "0";
      string s = "";
      while (num)
      {
            if (num & 1) s += '1';
            else s += '0';
            num >>= 1;
      }
      reverse(s.begin(), s.end());
      return s;
}
 
int main()
{
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            ll num;
            cin >> num;
            string bin = toBin(num);
            memset(memoize, 0, sizeof memoize);
            ll sum = solve(bin, bin.size());
            cout << "Case " << tcase << ": " << sum << endl;
      }
}