SRM428 Div2 1000

問題

aがn個とzがm個により構成される文字列が辞書順に並んでいる．k番目(1-based)にくる文字を返す．もし，kが文字列の個数を超える場合は空文字列を返す．
n,m<=100,k<=10^9

考え方

いくつかパターンを書いてみると気付く．k番目の文字列の先頭にくる文字は，kが{n+m-1}_C_{n-1}より大きいか小さいかで決まる．もしkのほうが小さい場合はaがくるので，n--する，kのほうが大きい場合はzがくるので，m--してk-={n+m-1}_C_{n-1}する．n,mのどちらかが0になったら残っているほうの文字を並べて返す．

反省

Combinationの値がかなり大きくなってしまうことがあるので，うまく計算しないといけない．(ある程度より大きくなったら-1を返すなど)