考虑 $1$ ~ $n$ 满足条件的数的个数 dp(n)

所以我们的所求为：dp(R) - dp(L-1)

组合数的初始化，使用递推公式即可。

考虑组合数，我们对这个数字转换成 $B$ 进制后的每一位进行处理，假设分解后的位数为 $n+1$ 位，$last$ 为可取 $1$ 的个数。

• 这一位是 $0$ ，那么可以考虑从后面的所有位中选 $K-last$ 个数的选法，$C_i^{k-last}$
• 这一位 $\gt 1$ ，比如 $4$ ，那么可以取 $1,2,3,4$
  • 取 $1$ 后，剩下的只能是后面所有的位中选 $K-last-1$ 个数， $C_i^{k-last-1}$
  • 为什么不考虑其他情况，因为本题是求 $1$ 的个数
• 这一位 $=1$ ，直接取 $last$++，为啥不能和上面的情况归到一类呢？因为我们要保证组合出来的数都要比 $n$ 小，如果直接组合数的话，可能组合出来的就比 $n$ 大了，所以我们要在下一位判断。

把上述的情况加起来，还要算上最后一种：取到最后一位，并且 $last$ 为 $K$ 了，答案加 $1$

核心代码：

const int N = 35;
int f[N][N]; // 存组合数
int X, Y, 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 f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int n)
{
	if (!n) return 0; // 边界判断，n为0
	vector<int> nums; // 存B进制下分解后的每一位的数字
	
	while (n) nums.pb(n % B), n /= B;
	
	int res = 0;
	int last = 0; // 取1的个数
	for (int i = nums.size() - 1; i >= 0; i--)
	{
		int x = nums[i];
		if (x) // x不为0
		{
			res += f[i][K - last]; // 当前取0
			if (x > 1) // 当这一位 > 1 ，我们只能取 1
			{
				if (K - last - 1 >= 0) res += f[i][K - last - 1];
				break; // 因为我们是从最高位依次判断的，所以我们可以直接算出来后面的方案数，因为那些方案组成的数字一定不会超过原来的数字。
			}
			else // 等于1的情况
			{
				last++;
				if (last > K) break;
			}
		}
		if (!i && last == K) res++;	// 到了这里，说明原来的那个数n也是满足条件的，要加一个
	}
	
	return res;
}