ABC215 E Chain Contestant
この問題は$ 10種類のコンテストしか登場しないことに注目して, bitDPを用いて解くことができる.
$ dp_{i, j, k} := 今まで$ i回のコンテストが開催されていて, すでにひとかたまりでの出場を終えたコンテストの種類の集合が$ jで, 最後に出場したコンテストの種類が$ kの場合の数 とおく.
便宜上コンテストの名称を$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9の数字に置き換えると, 遷移は次のようになる.
$ dp_{i + 1, j, k} = dp_{i + 1, j, k} + dp_{i, j, k} ($ i番目のコンテストに出場しない場合)
$ i番目のコンテストに出場できる($ jに$ S_iが含まれない)場合
$ dp_{i + 1, j, S_i} = dp_{i + 1, j, S_i} + dp_{i, j, k}($ k = S_iのとき)
$ dp_{i + 1, j | (2^{S_i}), S_i} = dp_{i + 1, j | (2^{S_i}), S_i} + dp_{i, j, k}]($ k \neq S_iのとき)
答えは$ dp_{N, j, k}の総和となる.
よって, $ K = 10とおくと, この問題を$ O(NK2^K)で解くことができた.