Xmas Contest 2016 F解説

F問題の解説です。


K次回文をreverseしたものはK次回文です。
K回の操作で回文になるのなら、下図のように逆操作を行えばそれもまた回文になります。

f:id:snuke:20161227200128p:plain

この問題では答えをmod2で求めれば良いので、回文でないようなK次回文はreverseしたものと相殺して消えるので、元々回文であるようなK次回文についてしか考える必要はありません。

  • K=0のときは回文の個数を求めればいいです。回文の個数は適当なDPで求まります。
  • K>=2のときは追加、置換*K-2、削除とすればもとの文字列に戻すことが出来るので、これも回文の個数を求めればいいだけです。
  • K=1のときは「もとが回文」かつ「1長いものまたは1短いものも回文」でなければならず、どの文字とどの文字が同じでなければならないかを考えると、すべての文字が同じ文字列しか条件を満たさないということがわかります。(下図参照)

f:id:snuke:20161227201930p:plain