lightoj1032

CODE

#include <iostream>
#include <cstring>
using namespace std;
int n,ncase;
long long dp[40][2][40];
int dig[40];
long long dfs(int len,int pre,int sta,int up,int first)
{
        //cout << len <<' '<<pre<<' '<<sta<<' '<<up<<' '<<first<<endl;
        if(len==0)
        {
                if(first)
                        return 0;
                return sta;
        }
        if(!up&&dp[len][pre][sta]!=-1)return dp[len][pre][sta];
        int a = up?dig[len]:1;
        long long res=0;
        for(int i=0;i<=a;i++)
        {
                if(first)
                        res+=dfs(len-1,i,0,up&&i==a,first&&i==0);
                else
                {
                        if(i==1&&pre==1)
                                res+=dfs(len-1,i,sta+1,up&&i==a,first&&i==0);
                        else
                                res+=dfs(len-1,i,sta,up&&i==a,first&&i==0);
                }
        }

        if(!up) dp[len][pre][sta]=res;
        return res;
}
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                cin >> n;
                memset(dp,-1,sizeof(dp));
                int len =0;
                while(n)
                {
                        dig[++len]=n%2;
                        n/=2;
                }

                cout << "Case "<<++ncase<<": "<<dfs(len,0,0,1,1)<<endl;
        }
        return 0;
}