yukicoder No.741 AscNumber(Easy)

問題

https://yukicoder.me/problems/no/741

10進数表示をしたときに桁が昇順に並んでいる数字を AscNumber とする。
10N 未満の AscNumber がいくつあるか求めよ。

考え方

[0, 9] の数字から重複を許して N 個選んだ時の数を昇順に並べると1つの AscNumber になる。全単射の関係になっており、よって AscNumber の数の個数は、 [0, 9] の数字から重複を許して N 個選ぶ場合の数と同じである。

よって {}_{10} \mathrm{H}_N = {}_{N + 9} \mathrm{C}_N が解になる。

ポイント

  • 対応で数える

類題

雑記

桁DPでも解けますが、再帰で呼び出すと Stack Overflow になります。