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

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

根据 Cayley–Hamilton theorem ,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) 暴力把矩阵代入多项式即可。

没错你看这个 II 怎么比 I 还简单 233 ...

参考资料

由于笔者非常比较懒,大部分的式子直接从 https://cmxrynp.github.io/2019/01/17/characteristic-polynomial/ 贺了过来。

none

已有 3 条评论

  1. 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. 喵喵喵?好好说话不要冒充外国人。

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