Timus Online Judge 1057. Amount of Degrees（数位dp）-白红宇

Timus Online Judge 1057. Amount of Degrees（数位dp）

阅读量：7013 次

发布时间：2019-06-28

本文共 1803 字，大约阅读时间需要 6 分钟。

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 [

Y] and being a sum of exactly

K different integer degrees of

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

18 = 2

4+2

20 = 2

4+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

Sample

input	output
15 2022	3

/*题意: 求一个区间的 degree进制的1的个数为k的数的个数思路:数位dp,一定要注意是1个个数为k  dp[i][j][k] 代表到达了i位的j进制还差k个1详细注意的地方写在了代码中*/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define bug printf("hihi\n")#define eps 1e-8typedef long long ll;using namespace std;#define N 35int dp[33][15][33];int degree,k;int bit[N];int dfs(int pos,int degree,int t,bool bound){ if(t<0) return 0; if(pos==0) return t ? 0:1; if(!bound&&dp[pos][degree][t]>=0) return dp[pos][degree][t]; int up=bound ? min(bit[pos],1):1; int ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos-1,degree,t-i,bound&&i==bit[pos]); //必须是bit[pos]，不能是uo if(!bound) dp[pos][degree][t]=ans; return ans;}int solve(int x){ int i,j; int len=0; while(x) { bit[++len]=x%degree; x/=degree; } return dfs(len,degree,k,true);}int main(){ int i,j,le,ri; memset(dp,-1,sizeof(dp)); while(~scanf("%d%d",&le,&ri)) { scanf("%d%d",&k,°ree); printf("%d\n",solve(ri)-solve(le-1)); } return 0;}