ABC 401-500/ABC425F - Inserting Process - 競技プログラミング用 知識集積所

---

問題

ABC425F

必要知識

B以下レベルの内容は省略

• bitDP※
  • bit全探索※
  • 動的計画法
• 剰余類環

考え方

まともに数えていては間に合わないので、工夫して数えることになる。
途中で現れる文字列は2^22通りまでなので、各文字列に対して「それを作る方法は何通りか？」を順に求める動的計画法でよい。
ただし、文字列をキーにするmap※を使うと、キー用の文字列処理のせいでN倍になってしまうらしく、ちょっと間に合わない。
本番中の誤答例

そこで、何文字目を拾った文字列なのかをbitで表してbitDP※で処理する。
この際、基本的には1つbitを消したものの文字列の列の作り方を合計すればよい。
ただし、文字列が"abbcd"みたいになっている場合にうっかり"abcd"相当のものを2つ足してはいけない。
そこで、消すビットを前からか後ろからかで順番に調査して、消したbitに対応する位置の文字が前回と同じだった場合には和に計上しないという方法を取ればよい。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。

解答例

解答例

注意点

別解