2進数で考える． \(d_{a}\) で \(a\) の桁数を表す． \(a \leq b\) ならば \(d_{a} \leq d_{b}\) となる．
今の問題設定では， \(d(A_{i})\) は \(i\) に対して真に単調増加となる．
解法
if \(60 < N\) : ans = 0
else
前処理: \(k \in N\) に対して \([0,M)\) の中で \(k\) 桁の数の個数を数えておき， それを \(C_{k}\) とおく． \(C_{k} = min(max(0, M-2^{k}), 2^{k})\) ．
後処理: \(i\) に対する \(dp\) ． 直前の数が何桁かだけ分かっていれば十分なので，
\(dp_{i,k} := A_{[0,i)}\) の決め方の個数，直前が \(k\) 桁とする．
\(ans = \sum_{k} dp{N,k}\)．
if \(60 < N\) : ans = 0
else
前処理: \(k \in N\) に対して \([0,M)\) の中で \(k\) 桁の数の個数を数えておき， それを \(C_{k}\) とおく． \(C_{k} = min(max(0, M-2^{k}), 2^{k})\) ．
後処理: \(i\) に対する \(dp\) ． 直前の数が何桁かだけ分かっていれば十分なので，
\(dp_{i,k} := A_{[0,i)}\) の決め方の個数，直前が \(k\) 桁とする．
\(ans = \sum_{k} dp{N,k}\)．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
