ABC202 D aab aba baa
辞書順の問題は前から決めていくのがよい. ここで次のような判定問題を解くこととする.
「今$ i - 1文字目まで決まっている(0-indexed, $ i = 0の場合はまだ何も決まっていないとする). $ i文字目を決めるとき, 'b'を使っても辞書順で$ K番目(1-indexed)を超えないか?」
この判定問題は一旦$ i文字目にaを使うと仮定して, $ i + 1文字目から末尾までの文字の決め方が何通りかを求めることによって解ける. これは残りの文字aの数($ i文字目に使うaも残っていないとする)を$ Aとおくと, $ _{N - i - 1} C _{A} となる. よって場合の数が求まったため, 元の判定問題も$ O(1)で解くことができた.
これを繰り返すことで$ O(N)でこの問題を解くことができる.