桁DPでn以下の非負整数の個数を求める

nは0以上10^18以下の整数とする。例えば123を入力すると124が出力される。下のソースコード中のコメントでi桁の整数と言ったとき、最上位の桁（i-1桁目）が0でもよいとする。最下位ビットを0桁目と呼んでいる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;

    constexpr int N = 60;
    // dp[i][0] : 2進法でi桁の非負整数で「nの下i桁」以下のものの個数
    // dp[i][1] : 2進法でi桁の非負整数で上記以外のものの個数
    ll dp[N + 1][2] = {};
    dp[0][0] = 1; // nの下0桁は0、0桁の非負整数は0のみ、よって該当するものは1個
    // 代えて dp[0][1] = 1 とすればn未満の非負整数の個数がわかる

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2; j++) {
            for (int d = 0; d < 2; d++) { // i桁目に付ける数字
                // 「nの下i+1桁」以下とそれ以外、どちらへ遷移するか
                int j1 = d + j > (n >> i & 1);
                // dがnのi桁目より大きければ「nの下i+1桁」より大きくなることが確定
                // jが1であれば、dがnのi桁目と等しくても大きくなる
                dp[i + 1][j1] += dp[i][j];
            }
        }
    }
    cout << dp[N][0] << endl;

    return 0;
}

10進法で考える別解。入力は文字列としてsで受け取っている。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    ll dp[20][2] = {};
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 2; j++) {
            for (int d = 0; d < 10; d++) {
                int j1 = d + j > s[i] - '0';
                dp[i][j1] += dp[i + 1][j];
            }
        }
    }
    cout << dp[0][0] << endl;

    return 0;
}