[ural1057][Amount of Degrees] (数位dp+进制模型)

Discription

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 ⁴+2 ⁰,
18 = 2 ⁴+2 ¹,
20 = 2 ⁴+2 ².

Input

The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 2 ³¹−1). The next two lines contain integersK 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.

Example

input	output
15 20 2 2	3

Solution

中文大意：给定你一个区间[X,Y]，问区间内可以表示为k个b的次方和的数有多少

可以套用进制模型，k个b的次方的和，转化为b进制后即含有k个1的b进制数（当然，其余为0，因为正好是幂的和，所以只可能包含了0或1）

先考虑简单的二进制情况，按照套路，我们可以对数的个数预处理一下

设f[i][j]表示i长度的二进制数正好含有j个1的个数

f[i][j]=f[i-1][j-1]+f[i-1][j]

处理b进制中大于1的情况：把求出的b进制串从高到低枚举，第一个大于1的位视为1，之后也全部视为1

之后把b进制视为2进制求解即可（满足区间减法，相减一下就行，当然因为算的时候都没有考虑这个限制数本身，所以用Ans(Y+1)-Ans(x)才能求出正解）

#include<stdio.h>

int f[][],n,m,_k,_b,len,zt[];

void bin_P() {

    for(int i=; i<=; i++) {

        f[i][]=,f[i][]=i;

        for(int j=; j<=i; j++)

            f[i][j]=f[i-][j-]+f[i-][j]; } }

int getans(int x) {

    for(len=; x; x/=_b)

        zt[++len]=x%_b;

    int res=,q=_k;

    for(int i=len; i; i--)

        if(zt[i]) {

            if(zt[i]>)

                return res+f[i-][q-]+f[i-][q];

            else res+=f[i-][q],q--;

            if(q<)return res; }

    return res; }

int main() {

    bin_P();

    scanf("%d%d%d%d",&n,&m,&_k,&_b);

    printf("%d\n",getans(m+)-getans(n));

    return ; }

秒客网