C. Classy Numbers

方法：数位dp
状态表达：dp(x, num)表示从0到x中，各位上有不超过num位非0数字的数的个数
我们每次对最高位进行分类讨论
k表示的是与x同位的最小数，例如65535的k就是10000，19的k就是10，详情见代码
设最高位数字为now， x为cnt位的数
1、填0，那么ans += dp(k - 1, num)
2、填1~now - 1，那么就是组合数的问题了，剩下的cnt - 1位中挑出0~num - 1位，其中每位都有1~9九种填法，于是就是ans += $(now - 1) \times \sum_{i = 0}^{num - 1}C_{cnt - 1}^i \times 9^i$
3、填now，ans += dp(x % k, num - 1)
递归求解即可，注意递归边界

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
ULL c[20][5];
ULL f[20];
ULL dp(ULL x, int num) {
    if (num == 0) return 1;
    ULL k = 1, cnt = 1;
    while (x >= k) k *= 10, cnt ++;
    k /= 10, cnt --;
    if (cnt <= num) return x + 1;
    ULL now = x / k, ans = 0;
    //0
    ans += dp(k - 1, num);
    //1~now - 1
    ULL tmp = 0;
    for (int i = 0; i <= num - 1; i ++ ) tmp += c[cnt - 1][i] * f[i];
    ans += (now - 1) * tmp;
    //now
    ans += dp(x % k, num - 1);
    return ans;
}
inline void solve() {
    ULL l, r; cin >> l >> r;
    cout << dp(r, 3) - dp(l - 1, 3) << endl;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    for (int i = 0; i <= 18; i ++ ) {
        f[i] = pow(9, i);
        for (int j = 0; j <= min(i, 3); j ++ ) {
            if (j > i) continue;
            else if (i == 0 || j == 0) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    int t; cin >> t;
    while (t -- )
        solve();
    return 0;
}