ABC 305 G — Banned Substrings

考察

禁止文字列の長さは全て6以下なので、現在までの文字列へ次の一文字を付けたとき新しく禁止列が現れるかは、現在の末尾5文字以下と追加文字だけで判定できる。

末尾情報の状態数は空文字を含む長さ0から5までの二進文字列で有限だが、Nは10^18で一文字ずつDPできない。各文字追加は同じ線形遷移を反復するため、遷移行列のN乗としてまとめられる。

棄却する候補: 長さごと・末尾状態ごとのDPを1文字ずつN回更新する。

状態数は小さくてもNが10^18なので、反復回数をそのまま消化できない。

採用する候補: 長さ5以下の安全な末尾を状態とするオートマトンを作り、その遷移行列を二分累乗する。

禁止判定に必要な履歴を有限状態へ圧縮でき、固定遷移の巨大回数反復を指数のビット数だけの行列積へ変えられる。

文字cを追加した列のsuffixのどれかが禁止列と一致した遷移だけを除く。一度禁止列を含んだ状態を保持する必要はなく、安全なprefix間の遷移だけで最終文字列を数えられる。

追加後に残すのは末尾min(5,現在長+1)文字で十分である。長さ6の禁止列も、遷移判定時には保存中の5文字と新文字を合わせて確認できる。

a,bからなる長さ0..5の安全な文字列を状態として列挙する。各状態へaまたはbを足し、末尾に禁止列があれば捨て、なければ末尾5文字以下の次状態へ向けて遷移行列の要素を1増やす。空状態の単位ベクトルへ行列のN乗を作用させ、全状態成分を合計する。

典型の発動条件

禁止substringの有限オートマトン

発動条件: 禁止パターンの最大長が小さく、文字を末尾へ追加しながら回避列を数えるとき。

新しい違反を判定できる末尾だけを状態にし、安全な文字追加を有向遷移にする。

線形DPの行列累乗

発動条件: 小さい固定状態間の同じ線形遷移を、非常に多い回数繰り返すとき。

一文字追加の遷移行列を二分累乗し、長さ10^18までの反復を飛ばす。

問題固有の要素

最大禁止長6に対して保存長は6ではなく5でよく、6文字目を追加する瞬間に違反を検出してから古い先頭を捨てる。

別の問題へ持ち帰る視点: 局所パターンを避ける逐次構成では、判定時に追加要素も使えるため、状態が保持すべき履歴は最大パターン長−1まで縮められる。

正当性

新しく出来る禁止substringは必ず追加文字を末尾に含む。最長6なので旧末尾5文字と新文字で全て検出できる。安全prefixだけの遷移を残すと、そのpathと禁止列を一度も含まない文字列が全単射になる。各追加が同じ遷移なのでN乗の空状態からの全成分和が長さNのsafe列数。

実装上の注意

  • 短い禁止列も含め、追加後の文字列の全suffixを照合する。禁止列自身を状態から除くだけでは、その列を既に内部へ含む長い状態を誤って残す可能性がある。
  • 行列の向きとベクトルの左右を統一し、N=1や空状態からの最初の遷移で転置ミスを検査する。積ごとに998244353で剰余を取る。

復習の核

  • 最大長2の禁止列で末尾1文字オートマトンを手で作り、『禁止列を新たに作るのは末尾だけ』という局所性を確認してから、保存長5と行列累乗へ一般化する。

計算量と制約

時間

O(S³ log N+M·S·6)、S≤1+2+4+8+16+32=63。末尾状態行列を累乗する。

空間

O(S²+Σ|s_i|)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq10^{18}; 1\leq M\leq126; N and M are integers.; s _ i is a non-empty string of length at most 6 consisting of a and b.; s _ i\neq s _ j\ (1\leq i\lt j\leq M)

出典

分類・前提・執筆情報

掲載状態: 収録済み

Banned Substrings の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 有限状態automatonの構成

主題
  • 有限状態automatonの構成: 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
追加で学ぶ技能
  • automaton上のDP・行列遷移: 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
既習技能

主タグ: automaton上のDP・行列遷移 有限状態automatonの構成

補助タグ: 線形遷移・行列累乗

執筆: abc-explanation-author1.1.1 / revision 1

学習の位置

体系上の位置: 有限状態automatonの構成

  • 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
  • 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

先に読む単元:

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題