原问题

给定一个数列前 k 项,并给出其 k 阶递推关系 $h_n=\sum_{i=1}^k a_ih_{n-i}$,求 $h_n$。

矩阵快速幂

大家都会矩阵快速幂的方法。

构造一个转移矩阵$A$

$$
A=\left[
\begin{matrix}
a_1 & a_2 & a_3 &\cdots & a_k\\
1 & 0 & 0 & \cdots & 0\\
0 & 1 & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & \cdots & 0
\end{matrix}
\right]
$$

用前 k 项构造初始矩阵,也是一个 k 维向量 $H_1$

$$
H_1=\left(
\begin{matrix}
h_k\\
h_{k-1}\\
h_{k-2}\\
\vdots \\
h_1
\end{matrix}
\right)
$$

即可得 $A^{n-1}H_1=H_n$。

时间复杂度 $O(k^3\log n)$。

k 如果比较大怎么办?我会卡常,jki 玄学卡常,wys 优化

多项式取模优化

前置知识

1. 矩阵的特征值

对于矩阵 $A$和一个 n 维向量 $x$,如果有一个值 $\lambda$满足 $Ax=\lambda x$,则我们称 $\lambda$为矩阵 $A$的特征值。

2. 矩阵的特征多项式

简单的缩好像就是特征方程再移项?

我们把之前的那个方程移项得 $(A-\lambda E)x=0$,显然若 x 有非零解,那么需要满足

$$
|A-\lambda E|=
\left|
\begin{matrix}
a_{11}-\lambda & a_{12} & a_{13} & \cdots & a_{1k}\\
a_{21} & a_{22}-\lambda & a_{23} & \cdots & a_{2k}\\
a_{31} & a_{32} & a_{33}-\lambda & \cdots & a_{3k} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_{k1} & a_{k2} & a_{k3} & \cdots & a_{kk}-\lambda
\end{matrix}
\right|
=0
$$

这其实是一个一元 k 阶方程,即特征方程。我们记 $f_A(x)=|A-xE|$,称矩阵 A 的特征多项式

3.Cayley-Hamilton 定理

$f_A(A)=0$。具体的证明可以看 widipedia,因为我也不会

为了方便记忆,有一个著名的伪证:$f_A(A)=|A-AE|=0$。

4. 拉普拉斯展开

对于行列式 A,我们定义它的关于第 i 行第 j 列的余子式 $M_{ij}$为原行列式删除第 i 行和第 j 列之后剩下的 k-1 阶行列式。

拉普拉斯展开是一个有关行列式的值的等式,按第 i 行展开得到如下等式

$$|A|=\sum_{j=1}^k(-1)^{j-1}a_{ij}|M_{ij}|$$

类似的,我们也可以对第 j 列展开

$$|A|=\sum_{i=1}^k(-1)^ia_{ij}|M_{ij}|$$

5. 多项式取模

$f(x)=g(x)p(x)+r(x)$

它们满足 $deg(r)<deg(g)<deg(f)$。

优化

我们知道如果给矩阵的某一行全部元素全部变为相反数,那么矩阵的行列式也会变成相反数,那么我们可以做这样一个操作,并记作 $g$:

$$
g(x)=(-1)^kf_A(x)=\left|
\begin{matrix}
x-a_1 & -a_2 & -a_3 &\cdots & -a_k\\
-1 & x & 0 & \cdots & 0\\
0 & -1 & x & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & \cdots & x
\end{matrix}
\right|
$$

为了求 $g(x)$的表达式,我们可以按照第一行对其进行拉普拉斯展开:

$$g(x)=x^k-\sum_{i=1}^k a_ix^{k-i}$$

由于我们要求的东西就是 $A^n$,那不妨构造一个这样的式子:

$$x^n=g(x)p(x)+r(x)$$

令 $x=A$则有 $A^n=g(A)p(A)+r(A)$

由之前的 Cayley-Hamilton 定理我们知道 $g(A)=(-1)^kf_A(A)=0$。那么我们就得到了 $A^n=r(A)$,而 $deg(r)<k$。为了方便,我们不妨看作 $deg(r)=k-1$。

那么我们怎么求 $r(A)$呢?原来的取模板子显然不可取,因为 n 可能很大,数组都开不下。考虑用倍增,即

$x^2\bmod g(x)=(x^1\bmod g(x))^2\bmod g(x),x^4\bmod g(x)=(x^2\bmod g(x))^2\bmod g(x)$

考虑用快速幂实现,这需要做两个操作:

  • 1. 多项式乘法
    • 暴力 $O(k^2)$
    • FFT$O(k\log k)$
  • 2. 多项式取模
    • 暴力 $O(k^2)$,跳过中间的零项 $O(kt)$
    • FFT$O(k\log k)$,限制多,有时用不了?

你问我怎么暴力取模?当然是模拟大除法啊

至此,我们已经得到了 $A^n=\sum_{i=0}^{k-1} r_iA^i$,再在两边乘上初始矩阵 $H_1$即得

$$H_{n+1}=\sum_{i=0}^{k-1} r_iH_{i+1}$$

由于 $H$是一个 n 维向量,而且中间涉及到的数乘及加法的运算,对于每一行是独立的,直接把第 k 行上的运算提出来就得到

$$h_{n+1}=\sum_{i=0}^{k-1}r_ih_{i+1}$$

时间复杂度常数较大的 $O(k^2\log n)$,或者常数更大的 $O(k\log k\log n)$,fft 的话要注意精度问题,mod 较大就可能有问题。

相关题目

看了这么久,然而貌似应用不多?

bzoj4161

hdu4914

NOI2017 泳池

分类: 文章

2 条评论

yzh · 2018年8月17日 8:50 下午

OvO

楼下都这么虚伪了吗 Orz

为啥大家不能坦诚相待呢

XZYQvQ · 2018年8月17日 2:18 下午

OvO

泥萌都这么强了吗 Orz

看来我 tcl,我 GUN 了

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注