# 特征多项式和常系数线性齐次递推学习笔记

n \times n 的矩阵 A 的特征多项式定义为

p(\lambda )=\det(\lambda I-A)

p(A) = O

A^n = A^n \bmod p(A)

#### shlw loves matrix I

1. p(x)
\begin{aligned} p(\lambda) &=\det(\lambda I-A) \\ &= \det\left( \begin{bmatrix} \lambda -c_1 & -c_2 & \cdots & -c_{k-1} & -c_k \\ -1 & \lambda & \cdots & 0 & 0 \\ 0 & -1 & \cdots & \lambda & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & \lambda \end{bmatrix} \right) \\ &= \lambda^n - \sum_{i=1}^{n} c_i \lambda^{n-i} \end{aligned}
1. x^n \bmod p(x) 直接多项式快速幂 + 多项式取模即可。 拉板子 233 ！
2. A 代入 x^n \bmod p(x)\vec f = \begin{pmatrix} f_{k-1} \\ f_{k-2} \\ f_{k-3} \\ \vdots \\ f_0 \end{pmatrix} ，则 f_k = [A^i \vec f]_k 。故：
\begin{aligned} f(n) & =\left[A^n \vec{f}\right]_ k \\ & = \left[\sum_{i=0}^{k-1} g_i A^i \vec{f}\right]_ k \\ & = \sum_{i=0}^{k-1} g_i \left[A^i \vec{f}\right]_ k \\ & = \sum_{i=0}^{k-1} g_i f_i \end{aligned}

#### shlw loves matrix II

1. p(x) 代入 x = 0 \cdots k 的值分别求出对应的 p(x) 。 暴力展开拉格朗日插值的式子，复杂度 O(k^4)
2. x^n \bmod p(x) 暴力多项式快速幂 + 多项式取模即可，复杂度 O(k^2 \log n)
3. A 代入 x^n \bmod p(x) 暴力把矩阵代入多项式即可。

### 已有 4 条评论

1. Thanks very nice blog!

2. Hi! Behold is an interesting offering for you. I can send your commercial offers or messages through feedback forms. Mailing is made in the same way as you received this message.
Details on this link. http://bit.ly/2TXdkWy
When you register using this link, you will receive a 20% discount on your first purchase. http://bit.ly/2GM1zQ9
It's time to finish.

1. 喵喵喵？好好说话不要冒充外国人。

3. Valuable information. Lucky me I found your website by chance, and I am stunned why this
twist of fate did not came about earlier! I bookmarked
it.

LOJ150 挑战多项式

» 下一篇