[UVA] 12866 - Combination

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12866 - Combination
Source            : UVA Online Judge
Category          : Number Theory, Dynamic Programing
Algorithm         : Lukas Theorem, Digit DP
Verdict           : Accepted




#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll         unsigned long long int   
  
ll dp[70][70];  
bool memoize[70][70];  
int a[70];  
  
inline ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)  
{  
      if (pos < 0) return (1LL << one);  
      ll &ret = dp[pos][one];  
      bool &mem = memoize[pos][one];  
      if (!flag && take && mem) return ret;  
      ll sum = 0;  
      int loop = 1;  
      if (flag) loop = a[pos];  
      for (int i = 0; i <= loop; i++)  
      {  
            if (!take && i == 0) sum += solve(pos-1, 0, 0, 0);  
            else sum += solve(pos-1, one + (i == 1), flag & i == a[pos], 1);  
      }  
      if (!flag && take) mem = 1, ret = sum;  
      return sum;  
}  
  
inline ll digitDP(ll n)  
{  
      if (n < 0) return 0;  
      int len = 0;  
      while (n)  
      {  
            a[len++] = n % 2;  
            n /= 2;  
      }  
      return solve(len-1);  
}  
  
int main()  
{  
      ll a, b;  
      while (scanf("%llu %llu", &a, &b) == 2)  
      {  
            if (a == 0 && b == 0) break;  
            ll sum = digitDP(b);  
            if (a > 0) sum -= digitDP(a-1);  
            printf("%llu\n", sum);  
      }  
}