https://noshi91.hatenablog.com/entry/2023/02/27/160945

概要

問題の解法と、巧妙な (当社比) 定数倍高速化の方法を書く。この高速化の方法は、heno239 さんに教えてもらった方法を式変形で導出しようとしていたら思いついた。 heno239 さんの手法は理解できていないので説明できないが、恐らく最終的に得られる式は同じだろうと思う。

問題文

https://qoj.ac/files/ucup/statements/statements-1-5.pdf

解法

https://noshi91.hatenablog.com/entry/2023/02/26/135340

この DP を、部分文字列の長さも管理できるように改造する。

$\displaystyle \text{dp} \lbrack i \rbrack \lbrack c \rbrack : = \sum _ {k = 0} ^ {\infty} ( ( S _ 0, S _ 1, \dots, S _ {i - 1} )$ の長さ $k$ の部分列であって $c$ で終わるものの種類数 $) x ^ k$

$\text{sum}$ は使わない。使うと上手く高速化ができなかったのだが、恐らく $\text{dp}$ の線形結合で表現されてしまうから無駄な情報となり、式変形の妨げになるのだと思う。遷移は以下のようになる。

\begin{align} \begin{pmatrix} \text{dp} \lbrack i + 1 \rbrack \lbrack 0 \rbrack \cr \text{dp} \lbrack i + 1 \rbrack \lbrack 1 \rbrack \end{pmatrix} = A _ {S _ i} \begin{pmatrix} \text{dp} \lbrack i \rbrack \lbrack 0 \rbrack \cr \text{dp} \lbrack i \rbrack \lbrack 1 \rbrack \end{pmatrix} + b _ {S _ i} \end{align} \begin{align} A _ c = \begin{cases} \begin{pmatrix} x & x \cr 0 & 1 \end{pmatrix} & \quad ( c = 0 ) \cr \begin{pmatrix} 1 & 0 \cr x & x \end{pmatrix} & \quad ( c = 1 ) \end{cases} , ~ b _ c = \begin{cases} \begin{pmatrix} x \cr 0 \end{pmatrix} & \quad ( c = 0 ) \cr \begin{pmatrix} 0 \cr x \end{pmatrix} & \quad ( c = 1 ) \end{cases} \end{align}

従って、アフィン変換 $v \mapsto A _ {S _ i} v + b _ {S _ i}$ を全て合成したものが得られればよい。複数の多項式の総積を求めるときと同様、 $S$ を半分に分けてそれぞれでの合成を求め、それらを FFT を用いて合成する分割統治法で $\Theta ( n ( \log ( n ) ) ^ 2 )$ のアルゴリズムが得られる。このとき $1$ 回の合成に必要な DFT と IDFT の回数の合計は $16$ 回になるが、もっと高速化したい。

ここで、高校数学における実数列の漸化式 $a _ {i + 1} = c a _ i + b$ の解き方に着想を得る。もし $\tilde{a} = c \tilde{a} + b$ となるような $\tilde{a}$ を発見できたならば、辺々を引くことで $(a _ {i + 1} - \tilde{a}) = c (a _ i - \tilde{a})$ となり、 $a _ i - \tilde{a}$ は単純な積の漸化式を持つというものである。同様に、もし $v = A _ {c} v + b _ {c}$ を満たす $v$ が $c$ に依存せずにとれたならば、アフィン変換ではなく $2 \times 2$ 行列の積を求めるだけで良くなる。計算してみると、 $v = \begin{pmatrix} x ( 1 - 2x ) ^ {-1} \cr x ( 1 - 2x ) ^ {-1} \end{pmatrix}$ が唯一条件を満たすことが分かる。ここで、 $( 1 - 2x ) ^ {-1}$ は有理関数体で考えてもいいし、形式的冪級数環で考えてもいい。というのも、最終的には何らかの多項式行列 $A$ に対して $A( -v ) + v$ を計算することになるわけだが、 $(1 - 2x) (A (-v) + v)$ は多項式の範囲で計算できて、そのあと $1 - 2x$ で割る部分も結果が多項式になる以上は何で考えても同じことである。

余談

$v = A _ {c} v + b _ {c}$ を満たす $v$ が $c$ に依存せずにとれるのは何故だろうか。成分が $2$ つなのに対して式は $4$ つあるので、 $v$ の存在は明らかではない。厳密でない議論だが、次のようなものが思いついた。

元の DP の意味に立ち返ると、このアフィン変換によって不変というのは、 $1$ つの文字を末尾に追加しても部分列の種類数があらゆる文字数について変化しないような状態と言える。すると、任意の $k$ について長さ $k$ の部分列を全て含むような、仮想的な無限長の文字列を考えてみると良さそうだ。このとき $\displaystyle \text{dp} \lbrack \ast \rbrack \lbrack 0 \rbrack = \text{dp} \lbrack \ast \rbrack \lbrack 1 \rbrack = \sum _ {k = 1} ^ { \infty } 2 ^ {k - 1} x ^ k = x (1 - 2x) ^ {-1}$ となる。