Timus OJ 1057 數位dp

Timus OJ 1057 數位dp

http://acm.timus.ru/problem.aspx?space=1&num=1057

 

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 exactlyK 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 = 24+20,
18 = 24+21,
20 = 24+22.

Input

The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231?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

/**
Timus OJ 1057 數位dp
題目大意：求出在給定區間內由多少個數可以表示為k個不同的b的冪之和
解題思路：對於一個數n，可以求比它小的數的個數有多少個滿足條件，首先將n轉化為b進制，然後用二進制表示狀態，如果b進制下第i位上的數為1，那麼對應二進制數為1，
           如果為0對應二進制位為0，如果b進制下第i位上的數大於1，那麼從第i為往後的二進制位全部置1，得到一個二進制數ans那麼該問題就轉化為求所有小於等於ans
           的二進制數中含有m個1的數有多少個？dp[i][j]表示i二進制位數含j個1的數有多少個，采用記憶化搜索寫挺方便
*/
#include 
#include 
#include 
#include 
using namespace std;
int x,y,k,b;
int bit[35],dp[35][65];
int dfs(int len,int num,int flag,int first)
{
    if(len<0)return num==k;
    if(flag==0&&dp[len][num]!=-1)
        return dp[len][num];
    int ans=0;
    int end=flag?bit[len]:1;
    for(int i=0;i<=end;i++)
    {
        int t=first&&(i==0);
        ans+=dfs(len-1,t?0:num+(i==1),flag&&i==end,t);
    }
    if(flag==0)
        dp[len][num]=ans;
    return ans;
}
int solve(int n)
{
    int len=0;
    while(n)
    {
        bit[len++]=n%b;
        n/=b;
    }
    int ans=0;
    for(int i=len-1;i>=0;i--)
    {
        if(bit[i]>1)
        {
            for(int j=i;j>=0;j--)
                ans|=(1<>=1;
    }
    return dfs(len-1,0,1,1);
}
int main()
{
    while(~scanf("%d%d%d%d",&x,&y,&k,&b))
    {
        memset(dp,-1,sizeof(dp));
        printf("%d\n",solve(y)-solve(x-1));
    }
    return 0;
}