URAL 1057 Amount of Degrees 数位DP *

题目地址：http://acm.timus.ru/problem.aspx?space=1&num=1057

思路来源：浅谈数位类统计问题

现在才发现数位问题可以转化为一棵二叉搜索树的问题去理解

1.先将B进制转化为2进制

对于询问n，我们需要求出不超过n的最大B进制表示只含0、1的数：找到n的左起第一位非0、1的数位，将它变为1，并将右面所有数位设为1。将得到的B进制表示视为二进制进行询问即可。

2.求出该2进制内含k个1的数量

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL d[32][32];
LL digit[32];
void init()
{d[0][0]=1;for(LL i=1;i<=31;++i){d[i][0]=1;         //任何位没有一的情况只有一种for(LL j=1;j<=i;++j)d[i][j]=d[i-1][j]+d[i-1][j-1]; //左子树+右子树}
}
LL turn(LL n,LL b)
{LL len=0;while(n){digit[len++]=n%b;n/=b;}LL ans=0; bool ok=false;for(LL i=len-1;i>=0;i--){if(digit[i]>1) ok=true;if(ok||digit[i]) ans|=1<<i;}return ans;
}
LL solve(LL n,LL k){  //[0,n]LL tot=0,ans=0;for(LL i=31;i>0;--i){if((1<<i)&n){tot++;if(tot>k) break;n^=1<<i;}if ((1<<(i-1))<=n)  //要保证比n小才能累加（累加上0的左子树）ans+=d[i-1][k-tot];}if(tot+n==k) ans++;return ans;
}
int main(int argc, char const *argv[])
{LL x,y,k,b;init();while(cin>>x>>y>>k>>b)cout<<solve(turn(y,b),k)-solve(turn(x-1,b),k)<<endl;return 0;
}