题目链接：

思路：考虑二进制数字的情况，可以写成一个二叉树的形式，然后考虑区间[i……j]中满足的个数=[0……j]-[0……i-1]。

所以统计树高为i，中有j个1的数的个数。

对于一个二进制数字，求出每次向右转时的左子树内的个数。

对于非二进制数字，就转换为二进制数字后再求解。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 120;int dp[maxn][maxn];typedef long long LL;void Init() //初始化，dp[i][j]代表高度为i的二进制树中恰好有j个1的数的个数 {    dp[0][0]=1;    for(int i=1;i<=31;i++){        dp[i][0]=dp[i-1][0];        for(int j=1;j<=i;j++)        dp[i][j]=dp[i-1][j]+dp[i-1][j-1];    }}int change(int x,int b) //b进制转换为2进制 {    int tot=0,ans=0;LL tmp=1;    while(tmp*b<=x){        tmp*=b;tot++;    }    while(tmp){        if(x>=tmp){            ans+=(1<
         
          0;i--){        if(x&(1<
          
           k) break;            x=x^(1<