#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為底的指數(shù)的和。那么組合數(shù)就是C(31, 16)，不知道這樣會不會超時，因為當時馬上認為這會超時，所以就放棄了這個想法。
苦思了很久，發(fā)現(xiàn)原來這問題可以轉(zhuǎn)化成2進制模式處理
例如以下數(shù)字
十進制 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
而題目條件中，符合要求的數(shù)據(jù)都是由 系數(shù)為1的K個以B為底的項相加之和
因此要符合給定區(qū)間[X, Y]，那么就可以把X和Y先轉(zhuǎn)換成對應(yīng)的符合要求的形式
假如現(xiàn)在X=365，Y=2348
那么2340就應(yīng)該轉(zhuǎn)換成10000，33343轉(zhuǎn)換成11111
這里展示的規(guī)律是：
1. 對一個B進制數(shù)D1，要構(gòu)造一個B進制數(shù)D2，D2只由0和1構(gòu)成，而且是大于等于D1的所有數(shù)里面最小的那個，那么D2的構(gòu)造方法就是
設(shè)D1長度為L1，從左到右第i位大于1，那么第i到L1位全部設(shè)為0；第i-1位加1，并且縫二進一。
例如
11234 => 100000， 2345 => 10000，0 => 1， 1110011 => 1110011
2. 對一個B進制數(shù)D1，要構(gòu)造一個B進制數(shù)D2，D2只由0和1構(gòu)成，而且是小于等于D1的所有數(shù)里面最大的那個，那么D2的構(gòu)造方法就是
設(shè)D1長度為L1，從左到右第i位大于1，那么第i到L1位全部設(shè)為1；其他位不變
例如
11234 => 11111，2345 => 1111，11011 => 11011
進行這樣的轉(zhuǎn)換之后，無論原來的X，Y是什么數(shù)，只要求出X'和Y'之前的符合條件的數(shù)，就肯定等價于原來的答案。
直到這里，已經(jīng)把原來的題目轉(zhuǎn)換成：在二進制數(shù)區(qū)間[X', Y']中，有多少個數(shù)是恰好有K個1的。（這就比原來那題意要清晰多了）
這里如果題目要求沒那么嚴格，只是求在[X，Y]內(nèi)所有任意個以B為底的項相加之和的數(shù)的個數(shù)，那么直接Y' - X'就完事了，不過要注意X'可能大于Y'，盡管X小于等于Y。
既然要求恰好K個1的數(shù)，那么也是枚舉就好，對枚舉的結(jié)果判斷是否在[X', Y']內(nèi)，但這樣其實跟一開始就枚舉沒區(qū)別。
而現(xiàn)在需要一種更快的方法。
求區(qū)間之間有多少個數(shù)字，有點麻煩，不如求小于等于X'的數(shù)的個數(shù)Nx，再求小于等Y'的數(shù)的個數(shù)Ny，那么結(jié)果就等于Ny - Nx，因此只要有一種快速計算小于等于二進制數(shù)D，而且恰好有K個1的數(shù)的個數(shù)的方法就OK了。
觀察這樣的規(guī)律：
對二進制數(shù)D=1001110001，假如要求小于等于D的數(shù)，并且恰好有4個1，那么首先要少于1000000000，肯定有C(9, 4)個（9個0代表9個可選位置，然后在里面選4個位置放1）
再求小于1001000000的，肯定有C(6, 3)個（6個0，選3個位置，不選4個的原因是有一個1已經(jīng)固定在1000000000的第一個1上了）
再求小于1001100000，有C(5, 2)個
再求小于1001110000，有C(4, 1)個
雖然1001110001還有一個1的位置，但是4個1已經(jīng)都被固定了，也就是說用4個1是怎么也組合不出在[10001110000，10001110001]之間的數(shù)（很優(yōu)雅！）
綜上，少于D的恰好有4個1的數(shù)的個數(shù)是C(6, 3) + C(5, 2) + C(4, 1)。
那如果D=1001110000，那就會少了一個，就是D本身，所以在最后處理一下，看D是否剛好符合要求就OK了。
如果D=1111呢，那么也是在最后處理一下看D是否剛好符合要求就OK了。
至此就是完整的解題思路。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
