一本通数位DP小结（更新中）

// 先转化为前缀和
// 从头到尾枚举每一位: 这一位的贡献为前面的位都相同, 这一位比原来更小, 后面的位任意的方案书
#include <vector>
#include <stdio.h>
#include <string.h>
int k, b;
int C[35][35]; // 组合数
int dp(int n) {
	if(!n) return 0;
	std::vector<int> num;
	while(n) num.push_back(n % b), n /= b;
	n = num.size();
	int res = 0, last = 0; // res 为答案, last 为当前 1 的个数
	for(int i = n - 1; i >= 0; i --) {
		int x = num[i];
		if(x) { // 这一位非0: 可以选择
			res += C[i][k - last]; // 这一位填0的情况(假设前面若干位都是)
			if(x > 1) { // 这一位可以尝试填1
				if(k - last - 1 >= 0) res += C[i][k - last - 1];
				break; // 由于只能填0或1,则
			} else // 只能选0: 如果1过多,跳过
				if(++ last > k) break;
		}
		if(!i && last == k) res ++; // 最后一位的贡献
	}
	return res;
}
int main() {
	int l, r; scanf("%d%d%d%d", &l, &r, &k, &b);
	for(int i = 0; i <= 34; i ++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j ++)
			C[i][j] = C[i-1][j] + C[i-1][j-1];
	}
	printf("%d\n", dp(r) - dp(l - 1));
	return 0;
}

#include <vector>
#include <stdio.h>
#include <string.h>
int f[15][10]; // 共有 i 位, 最高位为 j 的答案
int dp(int n) {
    if (!n)
        return 1; // 0满足条件

    std::vector<int> num;

    while (n)
        num.push_back(n % 10), n /= 10;

    int res = 0, last = 0; // last 为上一位

    for (int i = num.size() - 1; i >= 0; i --) {
        int x = num[i];

        for (int j = last; j < x; j ++)
            res += f[i + 1][j]; // 第i位填 j, 后面的随便填

        if (x < last)
            break; // 不能够保留

        last = x;

        if (!i)
            res ++; // 0满足条件
    }

    return res;
}
int main() {
    for (int i = 0; i < 10; i ++)
        f[1][i] = 1;

    for (int i = 2; i < 15; i ++)
        for (int j = 0; j < 10; j ++)
            for (int k = j; k < 10; k ++)
                f[i][j] += f[i - 1][k];

    int l, r;

    while (scanf("%d%d", &l, &r) == 2)
        printf("%d\n", dp(r) - dp(l - 1));

    return 0;
}

#include <math.h>
#include <vector>
#include <stdio.h>
#include <string.h>
int f[15][10]; // 总共 i 位数, 首位为 j 的方案数
int dp(int n) {
    if (!n)
        return 0; // 0不算

    std::vector<int> num;

    while (n)
        num.push_back(n % 10), n /= 10;

    int res = 0, last = -2;

    for (int i = num.size() - 1; i >= 0; i --) {
        int x = num[i];

        for (int j = (i == num.size() - 1); j < x; j ++) // 首位不能是0
            if (abs(j - last) >= 2)
                res += f[i + 1][j]; // 可以选的位

        if (abs(x - last) >= 2)
            last = x;
        else
            break; // 填不下去了

        if (!i)
            res ++; // 0结尾
    }

    for (int i = 1; i < (int)num.size(); i ++)
        for (int j = 1; j < 10; j ++)
            res += f[i][j]; // 位数不足的

    return res;
}
int main() {
    for (int i = 0; i < 10; i ++)
        f[1][i] = 1;

    for (int i = 2; i < 15; i ++)
        for (int j = 0; j < 10; j ++)
            for (int k = 0; k < 10; k ++)
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];

    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", dp(r) - dp(l - 1));
    return 0;
}