15 20

2

2

3

/*

题意: 求一个区间的 degree进制的1的个数为k的数的个数

思路:数位dp,一定要注意是1个个数为k  dp[i][j][k] 代表到达了i位的j进制还差k个1

详细注意的地方写在了代码中

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<set>

#include<map>

#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-8

typedef long long ll;

using namespace std;

#define N 35

int 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;

}