B: Similar Arrays - CODE FESTIVAL 2017 qual C | AtCoder
問題：数列Aに「似ている」数列の中で、各項を全て掛け合わせると偶数になるようなのはいくつ？（「似ている」の定義は問題文参照）
C: Inserting 'x' - CODE FESTIVAL 2017 qual C | AtCoder
問題：英小文字からなる文字列sの好きな位置に'x'を挿入して回文にできるか？できるなら何回挿入すればいい？
sを前後双方から1文字ずつ見ていって、同じか調べる
D: Yet Another Palindrome Partitioning - CODE FESTIVAL 2017 qual C | AtCoder
問題：英小文字からなる文字列sを分割する。分割された各項は、並べ替えると回文が作れるようになっていなくてはならない。最小の分割数を求める。
文字は英小文字のみという制約があるので、26種類。奇数か偶数かだけ分かればいいので、ビットフラグが使える。'a'=0x001, 'b'=0x010, 'c'=0x100, …とする。
ある文字列sに含まれる文字が奇数個ならビットを立てる。たとえば'aabbccdddef'は、d,e,fが奇数個なので、0x111000で表される。これをsのハッシュと呼ぶことにする。すると、以下に置き換えられる。
（で、ハッシュにするにはしたが、その後がわからず。普通にやるとTLEなので、動的計画法で上手いことやるんだろーなとは思いつつ、時間終了。以降、ほぼ解答の書き写しになってしまうが）
ポイントは、以下の点。
これにより、任意の文字列のハッシュが高速に求められる。その上で、問題を以下の部分問題に分割する。
$opt_i$を、$s[0, i)$の最小の分割数とする。$opt_0=0$として、i=1から順に計算する。最終的に$opt_N$が答えとなる。
いま、$opt_i$を求めることを考える。$opt_j \ (1 \le j \lt i)$は計算済みとする。
$s[0, i)$を、$s[k, i)$が回文を作れるような位置kで$s[0, k)$と$s[k, i)$に分けると、暫定的に$opt_i = opt_k + 1$となる。
具体的に考える。$s[0, i)=$'abcdabcab'とする。たとえば$k=4$として'abcd' + 'abcab'に分けると、'abcab'は回文を作れる。よって、暫定的に$opt_i ={\rm ('abcd'の最小分割数)}+1$となる。'abcd'は1文字ずつに分割するしか無いので$opt_k=4$。暫定で$opt_i=5$となる。
最終的な$opt_i$は、kを$1 \le k \lt i$の範囲で調べて、その中の最小値となる。
先ほどの例では、$k=2$として'ab' + 'cdabcab'と分けても、'cdabcab'が回文を作れる。その方が$opt_i={\rm 'ab'の最小分割数}+1=3$となり、より適した分割になる。
が、これでは$opt_{1 ... N}$の計算に$O(N)$、その各計算の中で$k=1 ... i$のループに$O(N)$、合計で$O(N^2)$かかるのでTLE。
次のポイントは、
2つの文字列のハッシュ値が同じということは、つまりs[i, j)には「各文字がちょうど偶数回ずつ出現する」ということ。回文を作れる文字列の末尾にそのような文字列をくっつけたり（取れるなら）取ったりしても、回文を作れることに変わりない。よって最適な分割数も変わらない。
これで何がいいかというと、kの具体的な値がわからなくても、たとえば「$a_k$が0x110010になるようなkの$opt_k$」は一意に決まる。
その上で、
よって、ハッシュ値$a_k$をキー、そのハッシュ値を持つ文字列の最小分割数$opt_k$を値とした辞書によるDPをおこなう。
調べるのは各$a_i$のループにつき27個で済むため、$O(N)$となり、間に合う。