思路

我们先用前缀和将问题转化为求范围内满足条件的数的个数-范围内满足条件的数个数.我们设当前我们在求范围内满足条件的数.
我们可以考虑一棵二叉树,往左走表示第位为,往右走为.(表示深度;第位表示最高位,以此类推;这里是进制时).这样走到叶子节点都会得到一个数,我们的任务就是找出恰好往右走了次,结果得到的数不超过的路径条数.
事实上我们不需要建出二叉树,只是这样可以使问题更形象
我们记录答案与一个计数变量(表示前面有几位选了).先将在进制下每一位求出来存在数组中(是最高位,是次高位,共有位),从枚举到,如果当前,我们就有两种选择,一种是使当前位为,还有一种是使当前位为.如果,i位及之后怎么走都不会超过,于是答案就加上并直接退出.如果,选的话答案加上,选的话使加一并继续枚举低位.如果,怎么样都得选,于是继续枚举低位.注意两个问题:的时候直接退出;最终时要使答案+1(样例就有这种情况,算一下样例就明白了).
复杂度.(主要是预处理,事实上预处理阶乘就可以做到,不过没什么必要)

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }

clock_t t_bg, t_ed;
int K, B, X, Y, w[50], n, ans;
int f[50][50];

int calc( int x ){
    n = 0; while( x ) w[++n] = x % B, x /= B;
    int ans(0), c(0);
    fd( i, n, 1 ){
        if ( w[i] == 1 ){
            ans += f[i - 1][K - c];
            if ( ++c > K ) return ans;
        } else if ( w[i] > 1 )
            return ans += f[i][K - c];
    } return ans + ( c == K );
}

signed main(){
    t_bg = clock();
    scanf( "%d%d%d%d", &X, &Y, &K, &B );
    f[0][0] = 1;
    fp( i, 1, 30 ){
        f[i][0] = 1;
        fp( j, 1, 30 ) f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
    } printf( "%d\n", calc(Y) - calc(X - 1) );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}