URAL 1057 Amount of Degrees （数位dp）

Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.

Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:

17 = 2⁴+2⁰,
18 = 2⁴+2¹,
20 = 2⁴+2².

Input

The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 2³¹−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

Output

Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.

Sample

Input

15 20

2 2

Output

所求的数为互不相等的幂之和，亦即其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进制表示视为二进制进行询问即可。

代码如下：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 int f[35][35],d[35];
 5 void init ()//其实这就是个杨辉三角形
 6 {
 7     memset(f,0,sizeof f);
 8     f[0][0]=1;
 9     for (int i=1;i<=31;++i)
10     {
11         f[i][0]=1;
12         for (int j=1;j<=i;++j)
13         f[i][j]=f[i-1][j-1]+f[i-1][j];
14     }
15 }
16 int calc (int x,int k)
17 {
18     int tot=0,ans=0;
19     for (int i=31;i>0;--i)
20 {
21     if (x&(1<<i))//x的第i+1位是不是1
22         {
23             tot++;
24             //printf("i=%d tot=%d
",i,tot);
25             if (tot>k)
26             break;
27             x^=(1<<i);//把这位削成0
28         }
29         if (1<<(i-1)&x)//能否右转，能则统计左子树，即i-1位选0
30         {
31             //printf("i-1=%d tot=%d f=%d
",i-1,tot,f[i-1][k-tot]);
32             ans+=f[i-1][k-tot];
33         }
34 
35     }
36     if (tot+x==k)//如果全都是1，则没有统计，++ans补上
37     ans++;
38     //printf("ans=%d
",ans);
39     return ans;
40 }
41 int transfer (int b,int x)//将x,y转换成等价的二进制数
42 {
43     int m=0,ans=0;
44     while (x)
45     {
46         d[m++]=x%b;
47         x/=b;
48     }
49     for (int i=m-1;i>=0;--i)
50     {
51         if (d[i]>1)
52         {
53             for (int j=i;j>=0;j--)
54             ans|=(1<<j);
55         }
56         else
57         ans|=d[i]<<i;
58     }
59     return ans;
60 }
61 int main()
62 {
63     //freopen("de,txt","r",stdin);
64     long long int x,y;
65     int k,b;
66     init();
67     while (~scanf("%lld%lld",&x,&y))
68     {
69         scanf("%d %d",&k,&b);
70         x=transfer(b,x-1);
71         y=transfer(b,y);
72         printf("%d
",calc(y,k)-calc(x,k));
73     }
74     return 0;
75 }

论文参照《浅谈数位类统计问题》作者：山东省青岛第二中学刘聪