tqyaaaaang's Blog

特征多项式优化线性递推

特征多项式优化线性递推

【特征多项式优化线性递推】

比较推荐这一篇论文:矩阵乘法递推的优化

大概只需要看第三部分就行了

【线性递推】

特征多项式可以用来优化一些线性递推,一般是给定前k项\({x_1}...{x_k}\),以及向量\({a_1}...{a_k}\),满足下列递推式:

$$ {x_n} = \sum_{i=1}^{k} { {a_i} * {x_{n-i}} }\ \ \ \ \ ( n > k ) $$

问题是求\(x_n\)

这当然可以用矩阵乘法+快速幂来做,复杂度: \(\Theta(k^3\ log\ n)\),这是NOIP难度,就不说了。

【特征多项式】

可以写出矩阵快速幂时候的转移矩阵\(M\)的特征多项式,就可以得到

$$ {M^n} = \sum_{i=1}^{k} { {a_i} * {M^{n-i}} } \tag{1} $$

具体证明可以参考开头给出的那篇论文。(但是其实只需要把这个式子记下来就行了

有了这个式子,就可以把所有\(M^n\)表示成\( \sum_{i=1}^{k} { {b_i} * {M^i} } \)的形式,这样就可以用多项式\(\{b_i\}\)来表示\(M^n\)。这样矩阵乘法就变成了两个矩阵对应的多项式的乘法(想一想,为什么?)。多项式乘法之后会出现超过k次项,用1式就可以把对应的项降次,就变回k次多项式。

这样的话,我们就可以得到\(M^n\)的对应的\(\{b_i\}\)的多项式,也就可以知道\(\{M^n\}\)了。

例如:
$$ f_i = f_{i-1} + f_{i-2} $$
这样的话有
$$ M^i = M^{i-1} + M^{i-2} $$
于是,应该发现,
$$
M =
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}\\
M^2 =
\begin{bmatrix}
2 & 1 \\
1 & 1
\end{bmatrix}
$$

\(M^1\)对应的多项式\(b_i\)为\(\{1,0\}\)
\(M^2\)对应的多项式为\(\{0,1\}\)
\(M^4={M^2}*{M^2}\),为\(\{0,0,0,1\}\)
由于出现了\(4\)次方,用\((1)\)式化简一次,得\(\{0,1,1\}\)
再化简一次,得\(\{1,2\}\)

于是,
$$
M^4 = 2 * M^2 + M =
\begin{bmatrix}
5 & 3\\
3 & 2
\end{bmatrix}
$$

但是直接这样还不行,因为直接还原\(M^n\)的话又退化到\(\Theta(n^3)\)了。但是注意到,求解\(x_n\)的时候是用\(M^n * \vec v\),这里\(\vec v\)是一个初始向量,由这个矩阵的定义可以知道,\(x_i = M^i * \vec v\) (其实矩阵乘矩阵应该也是矩阵,但是乘出来应该是一个\(k*1\)的矩阵,其实\(x_i\)就是其中的第1项,所以我们方便起见就这么表示)。注意到
$$
\begin{array} {l}
x_n = M^n * \vec v\\
\ \ \ \ = ( \sum_{i=1}^{k} { {b_i} * {M^i} } ) * \vec v\\
\ \ \ \ = \sum_{i=1}^{k} { {b_i} * {M^i} * {\vec v} }\\
\ \ \ \ = \sum_{i=1}^{k} { {b_i} * {x_i} }\\
\ \ \ \ = \sum_{i=1}^{k} { {b_i} * {a_i} }\\
\end{array}
$$

所以分别乘一下初项就好了。

这样的话,直接把矩阵乘法替换成对应多项式的乘法,就可以快速求出矩阵的对应的向量\(\{b_i\}\),套上快速幂,就可以优化了。

写起来非常简单,大概和矩乘+快速幂差不多。

复杂度: \(\Theta(k^2\ \log\ n)\)

【FFT优化】

如果转移很简单的话(如HDU4914那样),可以用FFT来优化多项式乘法那一部分,但是把高次项化成\(k\)次以内好像不行。具体来说,有一个m项的向量\(\{p_i\}\),

$$ {x_n} = \sum_{i=1}^{m} { {a_i} * {x_{n-p_i}} }\ \ \ \ \ ( n > k ) $$

此时复杂度: \(\Theta( k * m + k\ \log\ k\ \log\ n\ ) \)

【多项式取模优化】

如果转移不简单怎么办?

瓶颈就在乘法时超出 \(k\) 次项化到 \(k\) 次以内这里。回头再考虑转移矩阵的特征多项式,也就是:

$$ f_M(\lambda) = \lambda^k - \sum_{i=1}^k ( a_i * \lambda^{k-i} ) $$

由Cayley-Hamilton定理知,\(f_M(M) = 0\),这里 \(M\) 是原转移矩阵。继续用之前的表示法, \(f_M(M)\) 就相当于一个多项式 \(\{-a_k, -a_{k-1}, \ldots, -a_2, -a_1, 1\}\)。

于是对于 \(k * 2 - 1\) 次多项式 \(p'\),把超出 \(k\) 次项压到 \(k\) 次以内就相当于求一个 \(k\) 次多项式 \(p\),满足 \(p = p'\)。由于 \(f_M(M) = 0\),我们可以利用这一点,有

$$ p(x) = D(x) * f_M(M) + p'(x) $$

由于 \(f_M(M)\) 是一个 \(k\) 次多项式,这里 \(p'\) 就是 \(p\) 对 \(f_M(M)\) 取模的结果。于是利用多项式取模就可以继续优化了。 ( 不知道多项式取模?丢个链接 : 多项式除法及求模 )

复杂度: \(\Theta( k\ \log\ k\ \log\ n\ ) \)

【例题】

(点击链接可以访问对应题目的Blog)

POJ 2118
HDU 4914

Tianqi Yang

View Comments
Navigation