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

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. gamefly free trial

Thanks very nice blog!

2. Echeneis

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.
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. memset0

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

3. cialis

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 挑战多项式

» 下一篇