動的計画法を使用した問題の解法を教えてほしい

Question

前提・実現したいこと

以下に挙げるアルゴリズム問題の解き方（考え方）を教えていただきたいです。
※動的計画法を使用すると解けるそうです。

問題

1度しか使用されていない数字が1種類のみである3桁以上の正の整数を「Bナンバー」と定義します。

例：
116155　->　1度しか使用されていない数字は「6」のみなので、Bナンバーです。
176155　->　1度しか使用されていない数字は「6」と「7」の二つあるので、Bナンバーではありません。
166155　->　1度しか使用されていない数字は一つもないので、Bナンバーではありません。

整数を0から昇順に数えた時、
1番目に登場するBナンバーは 「100」
2番目に登場するBナンバーは 「101」
3番目に登場するBナンバーは 「110」
となります。

問題:
3京(3 * (10 ^ 16))番目のBナンバーを求めてください。

補足情報

• 上記問題は3～5年前（曖昧です）に参加したどこかのCTFで出題されていた問題です。

出題元のサイトが見つけられなかったため、ここで質問させていただきました。
細部は異なるかもしれませんが問題の趣旨には誤りないはずです。

• 当時のサイトのヒントに「動的計画法を使用する」とあったため、アプローチとして動的計画法を使用するのは間違いないと思います。

※ほかのアプローチでもよいので解法がわかる方は回答いただけるとありがたいです。

• CTFの開催期間は1カ月程度だったはずなので、少なくともその期間以内に解が出せるアルゴリズムでの解法をご教示願います。

（自分が当時挑戦したときは試算した計算時間が年単位になってしまって諦めました…）

その他

• 解き方だけでなくコードも提示していただけるとさらにありがたいです。
• Python3のコードだとさらにさらにありがたいです。
• 上記の問題が出題されていたCTFの詳細についてご存じの方がいらっしゃいましたら併せて情報提供いただけると助かります。

---

以上、よろしくお願いいたします。

Answer 1

• 3桁のBナンバーは何種類あるのか？
• 3桁のBナンバーをもとに4桁のBナンバーを作るにはどうすればいいだろうか？
• 同様に4桁のBナンバーをもとに5桁のBナンバーを作れるか？また、それ以外に5桁のBナンバーはないか？

Comments

[corutopi]

リアクションが遅くなってしまい申し訳ありません。
ご回答ありがとうございます。
「桁数ごとのBナンバーの総数を動的計画法で求めていく」ということでしょうか？

提示していただいたヒントをもとに考えていたら道筋が立てれそうになってきたので少し自分で考えてみたいと思います。
行き詰ったらまたコメント/追記させていただきますので、その際はお時間あればお相手していただければ幸いです。