答えは，以下の値の和です．

• \(1\) 以上 \(N\) 以下の数であって，先頭が \(1\) であるものの個数．
• \(1\) 以上 \(N\) 以下の数であって，先頭が \(11\) であるものの個数．
• \(1\) 以上 \(N\) 以下の数であって，先頭が \(111\) であるものの個数．
• \(\vdots\)

先頭に並ぶ \(1\) の個数が \(k\) 個である数 \(x\) を考えると，\(x\) は上のリストのうち最初の \(k\) 個に含まれることになるので，この変形の正当性が従います．

ここで例えば，先頭が \(111\) である数とはどのような値か考えてみます． これは，以下のいずれかに当てはまる数です．

• \(111\) 以上 \(112\) 未満の数．
• \(1110\) 以上 \(1120\) 未満の数．
• \(11100\) 以上 \(11200\) 未満の数．
• \(\vdots\)

一般化すると，\(1\cdots 10\cdots 0\) 以上 \(1\cdots 20\cdots 0\) 未満の数，という形になります．

あとは \(N\) 以下という条件を合わせて考えればよく，これは簡単です．

（\(1\cdots 10\cdots 0\) 以上 \(1\cdots 20\cdots 0\) 未満）という形の制約は，\(O(\log^2N)\) 個だけ考えればよいので，計算量も\(O(\log^2N)\) になります．