CF923E题解

· · 题解

这里有我对谱分解一些个人理解，希望能帮助到各位

前置知识：线性变换，特征值，特征向量，矩阵求逆，基变换。

你可能需要看以下视频：

特征向量

矩阵对角化

下面来进入正题，由于我们学的是 OI ，所以下面的讲解侧重于理解而不侧重于严谨。但如果有本质上的错误还望指出

矩阵谱分解

我们先回顾一下矩阵对角化，将一个 n 阶矩阵 A 视为一个线性变换，如果其有 n 个线性无关的特征向量（这些向量在经过此线性变换后只受到拉伸作用），我们选取这 n 个特征向量为基组成一个新的系，我们令 Q 是由 A 的 n 个线性无关的特征向量组成的矩阵，\Lambda 是由每个向量对应的特征值所组成的对角矩阵，那么在原系下的 A 变换就可以被新系下的 \Lambda 变换所代替。

先给出谱分解式子：

A = Q\Lambda Q^{-1} \Leftrightarrow \Lambda = Q^{-1}(AQ)

我们来从线性变换的角度理解一下：Q 左乘一个 A 矩阵代表着对 Q 中的向量实施 A 变换，又根据基变换知识和上文，向量左乘矩阵 Q^{-1} 是指将该向量从旧系转化为由 Q 中向量组成的基形成的新系，也就对应着旧系下 A 变换在新系中的变换，也就是 \Lambda 变换。

回到本题

递推矩阵为：

\left[ \begin{matrix} &1,&\frac{1}{2},& \frac{1}{3},&\cdots, &\frac{1}{n+1}\\ &0,&\frac{1}{2},&\frac{1}{3}, &\cdots, &\frac{1}{n+1}\\ &\vdots,&\vdots,&\vdots, &\ddots, &\vdots\\ &0, &0,&0, &\cdots, &\frac{1}{n + 1} \end{matrix} \right]

给其算 m 次方显然超时，我们考虑谱分解，对于上三角矩阵，先考虑求其特征值 \lambda，据定义，有：

\begin{aligned} A\vec{v} &= \lambda I\vec{v}\\ (A-\lambda I)\vec{v} &= \vec0 \end{aligned}

由于 v 是非零向量，我们可以看成 矩阵 A-\lambda I 对其实施了线性变换，而却把一个非零向量变成了零向量，说明 \vec{v} 一定受到了降维打击，所以矩阵 A-\lambda I 的行列式为 0，又因其为上三角矩阵，所以其行列式为主对角线所有元素相乘，这样就很容易地解出了其特征值分别为 1,\frac{1}{2},\frac{1}{3},\cdots,\frac{1}{n+1}。

现在来考虑解出特征向量，我们把 \lambda 代回，得

\left[ \begin{matrix} &1-\lambda,&\frac{1}{2}, \frac{1}{3},&\cdots, &\frac{1}{n+1}\\ &0,&\frac{1}{2}-\lambda,\frac{1}{3}, &\cdots, &\frac{1}{n+1}\\ &\vdots,&\vdots, &\ddots, &\vdots\\ &0, &0, &\cdots, &\frac{1}{n + 1}-\lambda \end{matrix} \right] \times \vec{v} = \vec{0}

展开后行行相减，得：

\begin{aligned} (1-\lambda)v_1 + \lambda v_2 &=0\\ (\frac{1}{2}-\lambda)v_2 + \lambda v_3 &=0\\ (\frac{1}{3}-\lambda)v_3 + \lambda v_4 &=0\\ \vdots \end{aligned}

我们发现，将解得的 \lambda 带入后，会出现一个自由元，而自由元以下的未知数均为 0，钦定自由元为 1，则我们可解出自由元以上的所有未知数，所以我们解得的特征向量 v_k = \sum_{i = 0}^n(-1)^{i + k}\binom{k}{i} \vec{e_{i+1}} 组成的矩阵 Q 为：

\left[ \begin{matrix} &1,&-1, &1, &-1&\cdots, &(-1)^n\\ &0,&1,&-2, &3, &\cdots, &(-1)^{n + 1}\binom{n}{1}\\ &0,&0,&1, &3,&\cdots, &(-1)^n\binom{n}{2}\\ &\vdots,&\vdots, &\vdots, &\vdots, &\ddots, &\vdots\\ &0, &0, &\cdots, &\cdots,&\cdots,&1 \end{matrix} \right]

对该矩阵求逆我使用的是代数余子式法，得到的结果把上面矩阵所有含 (-1) 的若干次方项都去掉就行了。

设初始向量为 \vec{p}， 我们要求 A^m \vec{p} = Q\Lambda^m Q^{-1} \vec{p}，考虑利用结合率从右往左计算，我们只需要知道 Q\vec{p} 与 Q^{-1}\vec{p} 如何快速计算就可以了，我们用 Q\vec{p} 举例：

\begin{aligned} (Q\vec{p})_i &= \sum_{k = 0}^n Q_{i,k}·p_{k}\\ &=\frac{(-1)^i}{i !} \sum_{k = 0}^i (-1)^j k!p_k \frac{1}{(k-i)!} \end{aligned}

是个差卷积的形式，把其中一个多项式翻转一下 NTT 一边乘出来把结果再翻转一边就行了。