//不超时解法--数位DP
//不遍历每个数，而是按位统计每个数字在每一位上出现的次数
//利用前缀和思想：count(a, b) = count(0, b) - count(0, a-1)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 统计[1, x]中数字d出现的次数
ll count(ll x, int d) {
    if (x <= 0) return 0;    
    ll res = 0;
    ll power = 1;   
    while (power <= x) {
        ll high = x / (power * 10);
        ll curr = (x / power) % 10;
        ll low = x % power;      
        if (d > 0) {
            if (curr < d) {
                res += high * power;
            } else if (curr == d) {
                res += high * power + low + 1;
            } else {
                res += (high + 1) * power;
            }
        } 
        else { // d == 0
            if (high > 0) {
                if (curr == 0) {
                    res += (high - 1) * power + low + 1;
                } else {
                    res += high * power;
                }
            }
        }      
        power *= ...