aab aba baa (Hard version)

2 secs 1024 MB
RedSpica

まずa0に,b1に変換します. すると,は先頭にを許した桁の進数とみなすことができます.

次に,以下の言い換えが成立します.

  • a個,b個からなる文字列のうち辞書順で何番目か 01文字列に変換して進数として見て,それより小さくて1の数が個である進数の個数

これは,桁数が同じもの同士の大小関係はそれらを文字列とみなしたときの辞書順の大小関係と一致し, 桁数が足りない場合は桁になるまで0で埋めればよいことから従います.

よって「01文字列に変換して進数として見て,それより小さくて1の数が個である進数の個数」を求めればよいです. これは桁DPという方法で求めることができ,その時の時間計算量はです.