Almost Everywhere Zero [AtCoder Beginner Contest 154 E]

https://atcoder.jp/contests/abc154/tasks/abc154_e

前提知識

• [桁DP](https://www.hamayanhamayan.com/entry/2017/04/23/212728

解説

https://atcoder.jp/contests/abc154/submissions/10002125

数がとても大きい上に、個数計算とのことなので桁DPをしよう。
数学的な解法がありそうな気もするが、自分は桁DPを実装した方が早いのでそっちでやった。

dp[dgt][isless][k] := dgt桁目まで確定していて、現時点でN以下であるかがislessであって、0でない数字がk個ある数の個数
これを一般的な桁DPの手法で計算する。
0と1～9の二通りで遷移を考えてもいいが、0～9の10通りで遷移するようにした方が実装が簡単になるので、
いつものように桁DPしよう。

string N; int K;
ll dp[101][2][5];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    int n = N.length();

    dp[0][0][0] = 1;
    rep(dgt, 0, n) rep(isless, 0, 2) rep(k, 0, K + 1) {
        int c = N[dgt] - '0';
        rep(nxt, 0, 10) {
            if (c < nxt && isless == 0) continue;

            int dgt2 = dgt + 1;
            int isless2 = isless;
            if (nxt < c) isless2 = 1;
            int k2 = k;
            if (nxt != 0) k2++;
            
            dp[dgt + 1][isless2][k2] += dp[dgt][isless][k];
        }
    }
    ll ans = dp[n][0][K] + dp[n][1][K];
    cout << ans << endl;
}