pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Grand Contest 012 C: Tautonym Puzzle

http://agc012.contest.atcoder.jp/tasks/agc012_c

解法

空の列も良い文字列だとみなす。

順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。

  • A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。
  • A←A+[foo], B←[foo]+B とすると A+B のパターン数は X+1 になる。

これを利用することで 4log(N) 個の要素で構築できる。