18 = 24+21,
20 = 24+22.
Input
2 ≤ B ≤ 10).
Output
Sample
Input
15 20
2 2
Output
3
所求的数为互不相等的幂之和，亦即其B 进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。
很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。
本题区间满足区间减法，因此可以进一步简化问题：令count[i..j]表示[i..j]区间内合法数的个数，则count[i..j]=count[0..j]-count[0..i-1]。换句话说，给定n，我们只需求出从0 到n有多少个符合条件的数。
假设n=13，其二进制表示为1101，K=3。我们的目标是求出0 到13中二进制表示含3个1 的数的个数。为了方便思考，让我们画出一棵高度为4 的完全二叉树：
为了方便起见，树的根用0 表示。这样，这棵高度为4 的完全二叉树就可以表示所有4位二进制数（0..24-1），每一个叶子节点代表一个数。其中，红色路径表示n。所有小于n的
数组成了三棵子树，分别用蓝色、绿色、紫色表示。因此，统计小于13 的数，就只需统计这三棵完整的完全二叉树：统计蓝子树内含3 个1的数的个数、统计绿子树内含2 个1 的数的个数（因为从根到此处的路径上已经有1 个1），
以及统计紫子树内含1个1 的数的个数。
注意到，只要是高度相同的子树统计结果一定相同。而需要统计的子树都是“右转”时遇到的。当然，我们不能忘记统计n 本身。实际上，在算法最初时将n 自加1，可以避免讨论n
本身，但是需要注意防止上溢。剩下的问题就是，如何统计一棵高度为i的完全二叉树内二进制表示中恰好含有j个1的数的个数。这很容易用递推求出：设f[i,j]表示所求，则分别统计左右子树内符合条件数的个数
，有f[i,j]=f[i-1,j]+f[i-1,j-1]。
这样，我们就得出了询问的算法：首先预处理f，然后对于输入n，我们在假想的完全二叉树中，从根走到n所在的叶子，每次向右转时统计左子树内数的个数。
最后的问题就是如何处理非二进制。对于询问n，我们需要求出不超过n的最大B进制表示只含0、1的数：找到n 的左起第一位非0、1 的数位，将它变为1，并将右面所有数位设为1。将得到的B进制表示视为二进制进行询问即可。
代码如下：
#include <bits/stdc++.h> using namespace std;
int f[][],d[];
void init ()//其实这就是个杨辉三角形
{
memset(f,,sizeof f);
f[][]=;
for (int i=;i<=;++i)
{
f[i][]=;
for (int j=;j<=i;++j)
f[i][j]=f[i-][j-]+f[i-][j];
}
}
int calc (int x,int k)
{
int tot=,ans=;
for (int i=;i>;--i)
{
if (x&(<<i))//x的第i+1位是不是1
{
tot++;
//printf("i=%d tot=%d\n",i,tot);
if (tot>k)
break;
x^=(<<i);//把这位削成0
}
if (<<(i-)&x)//能否右转，能则统计左子树，即i-1位选0
{
//printf("i-1=%d tot=%d f=%d\n",i-1,tot,f[i-1][k-tot]);
ans+=f[i-][k-tot];
} }
if (tot+x==k)//如果全都是1，则没有统计，++ans补上
ans++;
//printf("ans=%d\n",ans);
return ans;
}
int transfer (int b,int x)//将x,y转换成等价的二进制数
{
int m=,ans=;
while (x)
{
d[m++]=x%b;
x/=b;
}
for (int i=m-;i>=;--i)
{
if (d[i]>)
{
for (int j=i;j>=;j--)
ans|=(<<j);
}
else
ans|=d[i]<<i;
}
return ans;
}
int main()
{
//freopen("de,txt","r",stdin);
long long int x,y;
int k,b;
init();
while (~scanf("%lld%lld",&x,&y))
{
scanf("%d %d",&k,&b);
x=transfer(b,x-);
y=transfer(b,y);
printf("%d\n",calc(y,k)-calc(x,k));
}
return ;
}
论文参照《浅谈数位类统计问题》 作者：山东省青岛第二中学 刘聪