1585： 【例 1】Amount of Degrees

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 683 通过数: 360
【题目描述】
原题来自：NEERC 2000 Central Subregional，题面详见 Ural 1057。

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：

17=24+20
18=24+21
20=24+22
【输入】
第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。

【输出】
只包含一个整数，表示满足条件的数的个数。

【输入样例】
15 20
2
2
【输出样例】
3
【提示】
数据范围与提示：

对于全部数据，1≤X≤Y≤231−1,1≤K≤20,2≤B≤10。

思路：
数位dp原来不只是4维的qwq