aab aba baa (Hard version)

2 secs 1024 MB
RedSpica's icon RedSpica

まずSSa0に,b1に変換します. すると,SSは先頭に00を許した(A+B)(A+B)桁の22進数とみなすことができます.

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

  • SSaAA個,bBB個からなる文字列のうち辞書順で何番目か \Rightarrow SS01文字列に変換して22進数として見て,それより小さくて1の数がBB個である22進数の個数+1+1

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

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