[ACM] ural 1057 Amount of degrees (数位统计)

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[ACM] ural 1057 Amount of degrees (数位统计),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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 20
2
2
3
Problem Source: Rybinsk State Avia Academy
数位统计的第一题。看的刘聪的论文:浅谈数位类统计问题http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
[ACM] ural 1057 Amount of degrees (数位统计)_数位统计
作完这道题。认为数位统计真的很是奇异。不需要一个数一个数的去枚举推断,在推断一个数的时候,把比它小的数全都推断了出来,效率高。当中也有组合的运用。当高位肯定后,后面几位就随便取就可以。

题目中当B不是二进制时:
[ACM] ural 1057 Amount of degrees (数位统计)_ios_02
为何这样作呢? 一个数可以化成题意中给的形式,其B进制数中系数中应该不是0,就是1,假设从左到右找到系数>1,那么这个数确定是不符合题意的,应该使其化为1,这就使得原数小了一些,为了避免漏掉一些数,应使改动的这一位后面的所有位都变为1,这样是最大的且不超过n的B进制中仅仅包括0和1的数。这样化完之后依照二进制作就可以了。

代码:
#include <iostream>
#include <string.h>
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<<j);
            break;
        }
        else
            ans+=(b[i]<<i);
    }
    return ans;
}

int cal(int x,int k)
{
    int tot=0,ans=0;
    for(int i=31;i>0;i--)
    {
        if(x&(1<<i))//第i位为1(从0開始的),那么后面还剩下i个数字,后面的第一个数字为0,从i-1个数字中随意挑k-tot个
        {
            ++tot;
            if(tot>k)
                break;
            x=x^(1<<i);//1变为0
        }
        if((1<<(i-1))<=x)
            ans+=c[i-1][k-tot];
    }
    if(tot+x==k)//考虑x这个数自己
        ++ans;
    return ans;
}

int main()
{
    init();
    while(cin>>X>>Y>>K>>B)
        cout<<cal(change(Y),K)-cal(change(X-1),K)<<endl;
    return 0;
}