#include
<
iostream
>
using
namespace
std;
int
X,Y,K,B;
int
X_value[
33
]
=
{
0
}, X_len;
int
Y_value[
33
]
=
{
0
}, Y_len;
unsigned
long
long
count_Y, count_X, ret;
void
to_base(
int
base
,
int
*
new_value,
int
*
value_len,
int
value) {
int
mod, div, len
=
0
;
while
( value ) {
div
=
value
/
base
;
mod
=
value
%
base
;
new_value[len
++
]
=
mod;
value
=
div;
}
*
value_len
=
len;
}
void
to_little_bigger() {
int
len
=
X_len, i;
for
(i
=
len
-
1
;i
>=
0
&&
X_value[i]
<=
1
;i
--
) ;
if
( i
<
0
)
return
;
X_value[i
+
1
]
+=
1
;
for
(
int
j
=
i
+
1
;j
<
len;j
++
) {
X_value[j
+
1
]
+=
X_value[j]
/
2
;
X_value[j]
%=
2
;
}
if
(X_value[len]
==
1
)
X_len
++
;
if
( i
+
1
>
0
)
memset(X_value,
0
,
sizeof
(
int
)
*
(i
+
1
));
}
void
to_little_smaller() {
int
len
=
Y_len, i;
for
( i
=
len
-
1
;i
>=
0
&&
Y_value[i]
<=
1
;i
--
) ;
if
( i
<
0
)
return
;
for
( ;i
>=
0
;i
--
)
if
( Y_value[i]
!=
1
)
Y_value[i]
=
1
;
}
int
tmp[
32
]
=
{
0
};
unsigned
long
long
C(
int
m,
int
n) {
int
i;
if
( n
==
0
||
n
==
m )
return
1
;
if
( n
>
m
||
m
==
0
||
n
<
0
)
return
0
;
memset(tmp,
0
,
sizeof
(
int
)
*
32
);
for
(
int
j
=
0
;j
<
n;j
++
) tmp[j]
=
j
+
1
;
unsigned
long
long
ret
=
1
;
for
(i
=
m
-
n
+
1
;i
<=
m;i
++
) {
ret
*=
i;
for
(
int
j
=
0
;j
<
n;j
++
) {
if
(tmp[j]
!=
-
1
&&
(ret
%
tmp[j])
==
0
) {
ret
/=
tmp[j];
tmp[j]
=
-
1
;
}
}
}
return
ret;
}
unsigned
long
long
count_combination(
int
*
value,
int
len,
int
K) {
int
i,k;
unsigned
long
long
count
=
0
;
for
(i
=
0
,k
=
len
-
1
;k
>=
0
;k
--
) {
if
(value[k]
==
1
) {
count
+=
C(k,K
-
i);
i
++
;
}
}
return
count;
}
int
main() {
cin
>>
X
>>
Y;
cin
>>
K;
cin
>>
B;
to_base(B, X_value,
&
X_len, X);
to_base(B, Y_value,
&
Y_len, Y);
to_little_bigger();
to_little_smaller();
count_Y
=
count_combination(Y_value, Y_len, K);
count_X
=
count_combination(X_value, X_len, K);
ret
=
count_Y
-
count_X;
int
cnt
=
0
;
for
(
int
i
=
0
;i
<
Y_len;i
++
) {
if
( Y_value[i]
==
1
)
cnt
++
;
}
if
( cnt
==
K ) ret
++
;
cout
<<
ret
<<
endl;
return
0
;
}
一开始的想法是枚举，最坏的情况下是
1到2^31-1中，由16个 以2为底的指数的和。那么组合数就是C(31, 16)，不知道这样会不会超时，因为当时马上认为这会超时，所以就放弃了这个想法。
苦思了很久，发现原来这问题可以转化成2进制模式处理
例如以下数字
十进制 365 五进制 2430 <=> 2* 5^3 + 4* 5^2 + 3* 5^1 + 0 * 5^1
十进制 2348 五进制 33343 <=> 3* 5^4 + 3* 5^3 + 3* 5^2 + 4* 5^1 + 3* 5^0
而题目条件中，符合要求的数据都是由 系数为1的K个以B为底的项相加之和
因此要符合给定区间[X, Y]，那么就可以把X和Y先转换成对应的符合要求的形式
假如现在X=365，Y=2348
那么2340就应该转换成10000，33343转换成11111
这里展示的规律是：
1. 对一个B进制数D1，要构造一个B进制数D2，D2只由0和1构成，而且是大于等于D1的所有数里面最小的那个，那么D2的构造方法就是
设D1长度为L1，从左到右第i位大于1，那么第i到L1位全部设为0；第i-1位加1，并且缝二进一。
例如
11234 => 100000， 2345 => 10000，0 => 1， 1110011 => 1110011
2. 对一个B进制数D1，要构造一个B进制数D2，D2只由0和1构成，而且是小于等于D1的所有数里面最大的那个，那么D2的构造方法就是
设D1长度为L1，从左到右第i位大于1，那么第i到L1位全部设为1；其他位不变
例如
11234 => 11111，2345 => 1111，11011 => 11011
进行这样的转换之后，无论原来的X，Y是什么数，只要求出X'和Y'之前的符合条件的数，就肯定等价于原来的答案。
直到这里，已经把原来的题目转换成：在二进制数区间[X', Y']中，有多少个数是恰好有K个1的。（这就比原来那题意要清晰多了）
这里如果题目要求没那么严格，只是求在[X，Y]内所有任意个以B为底的项相加之和的数的个数，那么直接Y' - X'就完事了，不过要注意X'可能大于Y'，尽管X小于等于Y。
既然要求恰好K个1的数，那么也是枚举就好，对枚举的结果判断是否在[X', Y']内，但这样其实跟一开始就枚举没区别。
而现在需要一种更快的方法。
求区间之间有多少个数字，有点麻烦，不如求小于等于X'的数的个数Nx，再求小于等Y'的数的个数Ny，那么结果就等于Ny - Nx，因此只要有一种快速计算小于等于二进制数D，而且恰好有K个1的数的个数的方法就OK了。
观察这样的规律：
对二进制数D=1001110001，假如要求小于等于D的数，并且恰好有4个1，那么首先要少于1000000000，肯定有C(9, 4)个（9个0代表9个可选位置，然后在里面选4个位置放1）
再求小于1001000000的，肯定有C(6, 3)个（6个0，选3个位置，不选4个的原因是有一个1已经固定在1000000000的第一个1上了）
再求小于1001100000，有C(5, 2)个
再求小于1001110000，有C(4, 1)个
虽然1001110001还有一个1的位置，但是4个1已经都被固定了，也就是说用4个1是怎么也组合不出在[10001110000，10001110001]之间的数（很优雅！）
综上，少于D的恰好有4个1的数的个数是C(6, 3) + C(5, 2) + C(4, 1)。
那如果D=1001110000，那就会少了一个，就是D本身，所以在最后处理一下，看D是否刚好符合要求就OK了。
如果D=1111呢，那么也是在最后处理一下看D是否刚好符合要求就OK了。
至此就是完整的解题思路。
