URAL 1057 (数位dp)

比眉伴天荒 2022-06-04 05:16 154阅读 0赞

问题描述:

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 Xand Y, being a sum of exactly K different integer degrees of B.

Example

15 20

题目题意:题目给我们了一个区间，问这个区间内有多少个数可以被表示成B^(a1)+B^(a2)+....B^(ak) 且（a1!=a2!=...!=ak)这种形式.

题目分析:先看一下这个分析报告吧！[点击打开链接][Link 1]

然后看看这个大神的博客[点击打开链接][Link 2]

鶸鸡努力中

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    const int maxn=35;
    int f[maxn][maxn];
    int X,Y,k,b;
    void init()
    {
        f[0][0]=1;
        for (int i=1;i<=32;i++) {
            f[i][0]=f[i-1][0];
            for (int j=1;j<=i;j++) {
                f[i][j]=f[i-1][j]+f[i-1][j-1];
            }
        }
    }
    int solve(int n)
    {
        int a[100],len=0,cnt=0,ans=0;
        while (n) {
            a[len++]=n%b;
            n=n/b;
        }
        for (int i=len-1;i>=0;i--) {
            if (a[i]==1) {
                ans+=f[i][k-cnt];
                cnt++;
                if (cnt==k) break;
            }
            else if (a[i]>1){
                ans+=f[i+1][k-cnt];
                break;
            }
        }
        if (cnt==k) ans++;
        return ans;
    }
    int main()
    {
        init();
        while (scanf("%d%d%d%d",&X,&Y,&k,&b)!=EOF) {
            printf("%d\n",solve(Y)-solve(X-1));
        }
        return 0;
    }

[Link 1]: https://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
[Link 2]: http://blog.csdn.net/y990041769/article/details/40515677