Lightoj 1032 - Fast Bit Calculations

http://lightoj.com/volume_showproblem.php?problem=1032

1. #include <bits/stdc++.h>
2. using namespace  std;
3. #define ll long long int
4. vector <int> bits;
5. ll DP[35][2][2][35];
6. ll dp(ll pos, ll prev,ll issmall,ll couple){
7.     if(pos == bits.size()){
8.         return couple;
9.     }
10.     if(DP[pos][prev][issmall][couple]!=-1){
11.         return DP[pos][prev][issmall][couple];
12.     }
14.     ll ret = 0;
15.     ll mx = 1;
16.     if(!issmall) mx =  bits[pos];
17.         for(int i = 0; i <=mx; i++){
18.             ret+= dp(pos+1,i, (issmall|(i<bits[pos])),((prev==1 &&i==1)+ couple));
19.         }
20.         DP[pos][prev][issmall][couple] = ret;
21.         return ret;
22. }
24. ll convert(ll n)
25. {
26.     bits.clear();
27.     while(n!= 0){
28.         bits.push_back(n%2);
29.         n = n/2;
30.     }
31.     reverse(bits.begin(), bits.end());
32.     return dp(0, 0, 0, 0);
33. }
34. int main()
35. {
36.     ll ts;
37.     cin>>ts;
38.     for(int i = 1; i <= ts; i++){
39.     ll n;
40.     cin>>n;
41.     memset(DP, -1, sizeof(DP));
42.     ll ans = convert(n);
43.     cout<<"Case "<<i<<": "<<ans<<endl;
44.     }
46.     return 0;
47. }