作为一个既搞数竞，又搞物竞，又搞信竞的人我很清楚这题肯定可以不用数位DP来做

这其实就是一个简单的数学题，把这个整数转换成B进制，你就会发现一个很神奇的事情：

B的幂变成(100...0)

不同的B的幂之和变成了0和1的排列 那么，只需要把[X,Y]中的所有数都写成B进制，然后这些数里面恰好有K个1，其余都是0就行

搞定！！！

#include <bits/stdc++.h>
using namespace std;

string change_M(int x,int m)
{
	string ans = "";
	while(x > 0)
	{
		char ch = '0' + x % m;
		ans = ch + ans;
		x /= m;
	}
	return ans;
}

int S(string s)
{
	int len = s.size(),sum = 0;
	for(int i = 0;i < len;i++)
	{
		if(s[i] > '1') return -1;
		sum += (s[i] - '0');
	}
	return sum;
}

int main()
{
	int s,m,x,y;
	scanf("%d%d%d%d",&x,&y,&s,&m);
	int cnt = 0;
	for(int i = x;i <= y;i++)
	{
		if(S(change_M(i,m)) == s) cnt++;
	}
	printf("%d",cnt);
	return 0;
}

然后...

TE了。。。

这题还真的不简单，因为Y最大可是2^31 - 1

经过一晚上的抢救之后，也是终于做出来了复杂度低一点的办法，代码如下：(把string吃了)

#include <bits/stdc++.h>
using namespace std;
 
const int N = 50;
 
int h[N];
int f[N][N];
int k, x, y, b;
 
int solve(int x) 
{
    int top = -1;
    while (x) 
	{
        int p = x % b;
        x /= b;
        h[++top] = p;
    }
    int tot = 0, ans = 0;
    for (int i = top; i >= 0; --i) 
	{
        if (h[i] == 1) 
		{
            ++tot;
            if (tot > k + 1)
                break;
            if (i > 0)
                ans += f[i - 1][k - tot + 1];
        } else if (h[i] > 1) 
		{
            ans += f[i][k - tot];
            return ans;
        }
    }
    if (tot == k)
        ++ans;
    return ans;
}
 
int main() 
{
    scanf("%d%d%d%d", &x, &y, &k, &b);
    f[0][0] = 1;
    f[0][1] = 1;
    for (int i = 1; i <= 31; i++) 
	{
        f[i][0] = 1;
        for (int j = 1; j <= i + 1; j++) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
    }
    --x;
    int ans = solve(y) - solve(x);
    printf("%d\n", ans);
    return 0;
}