题目链接：

思路：好久没接触数位dp了=.=!，搞了这么久！一类记忆化搜索。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define FILL(a,b) memset(a,b,sizeof(a)) 7 typedef long long ll; 8  9 ll dp[33][2][33];10 int n,digit[33];11 12 13 ll dfs(int pos,int pre,int sum,int doing)14 {15     if(pos==-1)return sum;16     if(!doing&&dp[pos][pre][sum]!=-1)return dp[pos][pre][sum];17     ll ans=0;18     int end=doing?digit[pos]:1;19     for(int i=0;i<=end;i++){20         ans+=dfs(pos-1,i,sum+(pre==i&&i==1),doing&&i==end);21     }22     if(!doing)dp[pos][pre][sum]=ans;23     return ans;24 }25 26 ll Solve(int n)27 {28     int pos=0;29     while(n){30         digit[pos++]=(n&1);31         n>>=1;32     }33     return dfs(pos-1,0,0,1);34 }35 36 int main()37 {38     FILL(dp,-1);39     int _case,t=1;40     scanf("%d",&_case);41     while(_case--){42         scanf("%d",&n);43         printf("Case %d: %lld\n",t++,Solve(n));44     }45     return 0;46 }