一般に計算量が文字の種類数に依存せず \(O(N^3)\) となる解法を説明します。以下、文字の定義など公式解説に準拠します。

同様の方針で、 DP を高速化することを考えます。

DP の定義はこうでした。

\(dp[i][j] := \) ( \(p_n = i, q_n = j\) となるような \(T = T_1, T_2, \cdots ,T_n\) の個数)

\(i\) を固定したときに、すべての \(j \ (q_1 \leq j \leq N)\) に対して \(dp[i][j]\) からの遷移を計算することが実は計算量 \(O(N)\) でできます。

ある \(a, b\) について考えたとき、 \(dp[i][j]\) から \(dp[a][b]\) へ遷移するような \(j\) は \(1\) つの区間をなします。また、 \(dp[i][j]\) からの遷移先と \(dp[i][j + 1]\) からの遷移先は高々 \(1\) つしか変わらないので、 \(i\) を固定したとき遷移先として考える必要があるのは高々 \(N\) 個です。

遷移を表す区間は \(\sigma\) の前計算により定数時間で求められます。dp の累積和を持っておくことで、 \(i\) を固定したとき \(dp[i][*]\) からの遷移をまとめて \(O(N)\) で行うことができて、全体で計算量 \(O(N^3)\) です。

提出コード