4

「NOTE」常系数齐次线性递推

 2 years ago
source link: https://luckyglass.github.io/2021/21May23rdArt3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

要不是考到了，我还没发现这玩意我不是很会……

  • 多项式取模；
  • 矩阵快速幂。

# 常系数齐次线性递推

描述的是这么一个问题，给定数列 c1,c2,…,ck 以及数列 f 的前 k 项 f0,f1,…,fk−1，已知 f 有如下递推公式：

(n≥m)fn=∑i=1kcifn−i

求 fnmod998244353，其中 n 可以很大，k 是 105 左右的数。

  • 常系数：递推式的系数 ci 均为常数；
  • 齐次：这意味着递推式没有常数项（如果有常数项就别想了）；
  • 线性：fi 的指数都为 1。

# 算法原理

对于这种系数为常数的问题，我们有一个通用的解法 —— 矩阵快速幂：

[fnfn+1⋮fn+k−1]=[010⋯0001⋯0000⋯0⋮⋮⋮⋱⋮ckck−1ck−2⋯c1]×[fn−1fn⋮fn+k−2]

记最后那个 k×k 的转移方阵为 A，初始列向量为 St。常规的计算方法即计算

An×St

复杂度 O(k3log⁡n)，主要的瓶颈在于矩阵乘法。

下面要介绍的算法给出了这样一种构造，其中 {ci} 是针对 An（注意不仅与 A 有关，还与指数 n 有关）构造的数列 ——

An=∑i=0k−1ciAiAn×St=∑i=0k−1ciAi×St

目前看来好像没有什么茄子用，仍然需要计算矩乘。但是我们真的需要 An×St 这整个向量吗？实际上我们只需要 fn，即 An×St 的第一项。

再看看这个式子就可以发现它的用处了：

(An×St)1=∑i=0k−1(ciAi×St)1=∑i=0k−1ci(Ai×St)1

Ai×St 的实际意义是将 St 转移 i 次。所以 (Ai×St)1=fi，也即

fn=∑i=0k−1cifi

这样就免去了矩乘。

这就是这个算法的全部内容了？还剩下一个问题，{ci} 怎么构造？

定义函数 C(x) 如下，则要求 C(A)=An。

C(x)=∑i=0k−1cixi

接下来是一些魔法……如果我们有函数 F(x) 满足

F(A)=∑i=0kfiAi=0

且有 G(x) 满足：

xn=G(x)F(x)+C(x)→C(x)=xnmodF(x) An=G(A)F(A)+C(A)=C(A)

利用多项式取模对快速幂稍加改造就可以计算 C(x)。

「稍 加 改 造」

然后我们发现又需要构造 F(x)……如果要对一个一般的方阵求 F(A)=0 那确实很难，但常系数齐次线性递推的转移矩阵 A 因为它的结构特殊，有一个简洁的构造：

  • fk=1；
  • fi=ck−i（0≤i<k）。

至于为什么这样构造，就涉及到矩阵的特征向量的内容，和这个算法本身没有太紧的关联。有兴趣的读者可以参考 shadowice1984 的洛谷博客。

THE END

Thanks for reading!

我也曾 隐约想过 从这世界逃离
因为有无数次 和最优解失之交臂
那时耀眼的自己 定不会轻易容许
骄傲变得同墙角霉菌 不差毫厘

——《我也曾想过一了百了(中文填词)》 By 洛天依

> Link 我也曾想过一了百了 - Bilibili


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK