桁,bit

int main() {
    string N; cin >> N;
    int n = N.size();
    int K; cin >> K;
    ll dp[110][2][4];
    REP(i, 110) {
        REP(j, 2) {
            REP(k, 4) {
                dp[i][j][k] = 0;
            }
        }
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k <= K; ++k) {
                int x;
                x = j ? 9 : N[i] - '0';
                for (int d = 0; d <= x; ++d) {
                    if (d != 0) {
                        if (k < K) {
                            dp[i + 1][j || (d < x)][k + 1] += dp[i][j][k];
                        }
                    }
                    else {
                        dp[i + 1][j||(d<x)][k] += dp[i][j][k];
                    }
                }
            }
        }
    }
    cout << dp[n][0][K] + dp[n][1][K] << endl;
    return 0;
}