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

前回。

10進法バージョン。10を2に変えれば2進法で処理することもできる。

0桁の非負整数は0のみ、非負整数nに対しnの下0桁は0とする。

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

using T = array<ll, 2>;

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

    T dp = {};
    dp[0] = 1; // i桁の非負整数の個数（最初i=0）
    dp[1] = 1; // i桁の非負整数のうち「nの下i桁」以下のものの個数

    for (ll t = n; t > 0;) {
        T p = {};
        int d0 = t % 10; t /= 10;
        for (int d = 0; d < 10; d++) {
            p[0] += dp[0];
            if (d <= d0) p[1] += dp[d == d0];
        }
        dp = p;
    }

    cout << dp[1] << endl;

    return 0;
}