Amount of Degrees（数位dp）

题目链接：传送门

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

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

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

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

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn = ;

int dp[maxn][maxn];

typedef long long LL;

void Init() //初始化，dp[i][j]代表高度为i的二进制树中恰好有j个1的数的个数

{

    dp[][]=;

    for(int i=;i<=;i++){

        dp[i][]=dp[i-][];

        for(int j=;j<=i;j++)

        dp[i][j]=dp[i-][j]+dp[i-][j-];

    }

}

int change(int x,int b) //b进制转换为2进制

{

    int tot=,ans=;LL tmp=;

    while(tmp*b<=x){

        tmp*=b;tot++;

    }

    while(tmp){

        if(x>=tmp){

            ans+=(<<tot);

            x-=tmp;

        }

        tmp/=b;tot--;

    }

    return ans;

}

int cal(int x,int k) //求二进制中k个数组成x的组合的个数

{

    int tot=,ans=;

    for(int i=;i>;i--){

        if(x&(<<i)){ //统计当前位是否为1

            tot++;

            if(tot>k) break;

            x=x^(<<i);

        }

        if((<<(i-))<=x) ans+=dp[i-][k-tot];  //统计左子树中的个数

    }

    if(tot+x==k) ans++; //判断端点是否由k个数组成

    return ans;

}

int main(void)

{

    int x,y,k,b;

    Init();

    while(~scanf("%d%d%d%d",&x,&y,&k,&b)){

        printf("%d\n",cal(change(y,b),k)-cal(change(x-,b),k));

    }

    return ;

}