题解 - 帖子

把给的十进制数转化为B进制数，各个数位上除了0就是1才符合条件

f[i][j]为前i位j个1的数量

初始化就是个组合数，自己想吧

这个数位DP模板题挺好想的

#include <iostream>

using namespace std;

const int N = 35;

int f[N][N];

int k,B;

void init()
{
	for(int i = 0;i <= N;i ++)
		for(int j = 0;j <= i;j ++)
			if(!j) f[i][j] = 1;
			else if(i && j) f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int x)
{
	if(!x) return 0;
	int a[N] = {0};
	int l = 0;
	int last = 0;
	int ans = 0;
	while(x)
	{
		a[++ l] = x % B;
		x /= B;
	}
	for(int i = l;i >= 1;i --)
	{
		if(a[i])
		{
			ans += f[i - 1][k - last];
			if(a[i] > 1)
			{
				if(k - last - 1 >= 0) ans += f[i - 1][k - last - 1];
				break;
			}
			else{
				last ++;
				if(last > k) break;
			}
		}
		if(i == 1 && k == last) ans ++;
	}
	return ans;
}

int main()
{
	init();
	int l,r;
	cin >> l >> r >> k >> B;
	cout << dp(r) - dp(l - 1);
	return 0;
}