競技プログラミング用 知識集積所
ABC458F - Critical Misread
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- Aho–Corasick法※的な発想（そのものではない）
- Trie木※的な発想（そのものではない）
- 行列計算※
- ダブリング※
- 剰余類環
考え方
この手の問題でよくある方法は、各文字列の何文字目まで完成済かで分類して動的計画法。
しかし今回それをやると、10^10個要素をもつデータを10^9回更新することになって、とても無理。
これをどうにかする。
しかし今回それをやると、10^10個要素をもつデータを10^9回更新することになって、とても無理。
これをどうにかする。
まず、今回は連続部分列の指定があるため、10^10個の要素のほとんどは絶対に起こりえない。
そして、起こりえるものは、sの各文字列が何文字完成しているかより、むしろDPしながら作っている文字列の末尾何文字かで管理した方が手っ取り早い。
そして、起こりえるものは、sの各文字列が何文字完成しているかより、むしろDPしながら作っている文字列の末尾何文字かで管理した方が手っ取り早い。
ということで、作成中文字列の末尾に何があったら特別扱いする必要があるかを考える。
単純に考えるとsの各文字の先頭から何文字かとったものということになるが、本当に単純にやると問題が発生する。
例えば、sの中に'a'で始まるものが複数あった場合、末尾が'a'であることはどちらの文字列の作りかけなのか判別がつかない。
そこで、Trie木※的な発想で、「sの各文字の先頭から何文字かとってできることがある文字列」1つ1つに頂点を割り当てておくことにする。
すると、「どれを作っているかわからないが、とりあえず何かの完成に向かう文字列を持っている」という情報を持つことができる。
単純に考えるとsの各文字の先頭から何文字かとったものということになるが、本当に単純にやると問題が発生する。
例えば、sの中に'a'で始まるものが複数あった場合、末尾が'a'であることはどちらの文字列の作りかけなのか判別がつかない。
そこで、Trie木※的な発想で、「sの各文字の先頭から何文字かとってできることがある文字列」1つ1つに頂点を割り当てておくことにする。
すると、「どれを作っているかわからないが、とりあえず何かの完成に向かう文字列を持っている」という情報を持つことができる。
この木の頂点は最大でsの総文字数+1個、つまり最大101個である。
それぞれ事前に末尾にsのどれかの要素を持つか調べておく。
（sの要素そのものだけでは不十分なことに注意）
それぞれ事前に末尾にsのどれかの要素を持つか調べておく。
（sの要素そのものだけでは不十分なことに注意）
さて、そこからAho–Corasick法※的な発想で、遷移行列を考える。
各頂点に相当する文字列の後ろに'a'から'z'の文字を順番につけてみる。
付けた文字列に対応する頂点があればそこへの遷移を1つ加算。
なければ対応頂点があるようになるまで前から順に1文字ずつ削除していき、見つけた対応頂点への遷移を1つ加算。
ただし、遷移前後どちらかが末尾にsのどれかの要素を持つ文字列だった場合は無視する。
101個の文字列に対して26文字を付けて、文字削除が最大11回くらいなので、計算量的には余裕。
各頂点に相当する文字列の後ろに'a'から'z'の文字を順番につけてみる。
付けた文字列に対応する頂点があればそこへの遷移を1つ加算。
なければ対応頂点があるようになるまで前から順に1文字ずつ削除していき、見つけた対応頂点への遷移を1つ加算。
ただし、遷移前後どちらかが末尾にsのどれかの要素を持つ文字列だった場合は無視する。
101個の文字列に対して26文字を付けて、文字削除が最大11回くらいなので、計算量的には余裕。
あとは、この行列をダブリング※でn乗し、第0行の総和を取ればよい。
101×101行列だとしても、101^3*logN回の計算は十分間に合う。
101×101行列だとしても、101^3*logN回の計算は十分間に合う。
答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
