1057. Amount of Degrees

Time limit: 1.0 second

Memory limit: 64 MB

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

4+2

0,

18 = 2

4+2

1,

20 = 2

4+2

2.

Input

The first line of input contains integers 

X and 

Y, separated with a space (1 ≤ 

X ≤ 

Y ≤ 2

31−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	output
15 2022	3

Problem Source: Rybinsk State Avia Academy

数位统计的第一题。看的刘聪的论文：浅谈数位类统计问题http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html

做完这道题。认为数位统计真的非常奇异。不须要一个数一个数的去枚举推断，在推断一个数的时候，把比它小的数全都推断了出来，效率高。当中也有组合的运用。当高位确定后，后面几位就随便取就能够。

题目中当B不是二进制时：

为什么这样做呢？ 一个数能够化成题意中给的形式，其B进制数中系数中应该不是0，就是1，假设从左到右找到系数>1，那么这个数肯定是不符合题意的，应该使其化为1，这就使得原数小了一些，为了不漏掉一些数，应使改动的这一位后面的全部位都变为1，这样是最大的且不超过n的B进制中仅仅包括0和1的数。这样化完以后依照二进制做就能够了。

代码：

#include 
       
        #include 
        
         using namespace std;int X,Y,K,B;int c[40][40];void init()//组合数{    c[0][0]=1;    for(int i=1;i<=31;i++)    {        c[i][0]=c[i-1][0];        for(int j=1;j<=i;++j)            c[i][j]=c[i-1][j]+c[i-1][j-1];    }}int change(int n){    int b[40];    int len=0;    while(n)    {        b[len++]=n%B;        n/=B;    }    int ans=0;    for(int i=len-1;i>=0;i--)    {        if(b[i]>1)        {            for(int j=i;j>=0;j--)                ans+=(1<
         
          0;i--)    {        if(x&(1<
          
           k)                break;            x=x^(1<
           
            >X>>Y>>K>>B)        cout<
            
             <