度的数量

首先解释一下就是，这里的f表示的是，枚举到第i位，且已经有了j个不同的b的幂次方的数量

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 35;
int f[N][N];//枚举第i位且上一位是j的数量
int num[N];
int len;
int k, b;
int dfs(int pos, int cnt, int limit)
{
    if(!pos) return cnt == k;//枚举到了最后一位的下一位，看看是不是k个1
    
    if(!limit && ~f[pos][cnt]) return f[pos][cnt];//如果没有限制并且被搜过，直接返回
    int res = 0, up = limit ? min(num[pos], 1) : 1;//找一下上限，这里大于1肯定不行，就直接取1
    int lim = limit ? num[pos] : b - 1;//记录真实按道理能到达的上限，来确定limit
    for (int i = 0; i <= up; i ++ )
    {
        if(i == 1 && cnt == k) continue;//如果是1并且已经有了k个，就直接跳过
        res += dfs(pos - 1, cnt + (i == 1), limit && i == lim);
    }
    
    if(!limit) f[pos][cnt] = res;//如果没有限制就更新一下f的值
    //因为有限制的话跟没有限制搜出来的res不同，没有限制的用到的更多，有限制只能用一次
    return res;
}

int cal(int x)
{
    memset(f, -1, sizeof f);
    len = 0;
    while(x) num[++ len] = x % b, x /= b;
    return dfs(len, 0, 1);
}
int main()
{
    int l, r;
    cin >> l >> r >> k >> b;
    cout << cal(r) - cal(l - 1) << endl;
    return 0;
}

不要62

这里的集合就是枚举第i位，并且上一位是j的数量

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

int num[20];
int f[20][10];

int dfs(int pos, int pre, bool limit) {
	if(pos == -1) return 1;
	if(!limit && ~f[pos][pre]) return f[pos][pre];
	int res = 0, up = (limit ? num[pos] : 9);
	for(int i = 0; i <= up; ++i) {
		if(i == 4) continue;
		if(pre == 6 && i == 2) continue;
		res += dfs(pos - 1, i, limit && i == up);
	}
	if(!limit) f[pos][pre] = res;
	return res;
}

int cal(int n) {
	int pos = 0;
	while(n) {
		num[pos++] = n % 10;
		n /= 10;
	}
	return dfs(pos - 1, 0, 1);
}

void work() {
	memset(f, -1, sizeof f);
	int l, r;
	while(scanf("%d %d", &l, &r) && r) {
		printf("%d\n", cal(r) - cal(l - 1));
	}
}

int main() {
	work();
	return 0;
}