「NOTE」常系数齐次线性递推
要不是考到了,我还没发现这玩意我不是很会……
# 前置
- 多项式取模;
- 矩阵快速幂。
# 常系数齐次线性递推
描述的是这么一个问题,给定数列 \(c_1,c_2,\dots,c_k\) 以及数列 \(f\) 的前 \(k\) 项 \(f_0,f_1,\dots,f_{k-1}\),已知 \(f\) 有如下递推公式:
(n\ge m)&&f_{n}=\sum_{i=1}^kc_if_{n-i}
\end{aligned}
\]
求 \(f_n \bmod 998244353\),其中 \(n\) 可以很大,\(k\) 是 \(10^5\) 左右的数。
- 常系数:递推式的系数 \(c_i\) 均为常数;
- 齐次:这意味着递推式没有常数项(如果有常数项就别想了);
- 线性:\(f_i\) 的指数都为 \(1\)。
# 算法原理
对于这种系数为常数的问题,我们有一个通用的解法 —— 矩阵快速幂:
\]
记最后那个 \(k\times k\) 的转移方阵为 \(A\),初始列向量为 \(St\)。常规的计算方法即计算
\]
复杂度 \(\mathcal O(k^3\log n)\),主要的瓶颈在于矩阵乘法。
下面要介绍的算法给出了这样一种构造,其中 \(\{c_i\}\) 是针对 \(A^n\)(注意不仅与 \(A\) 有关,还与指数 \(n\) 有关)构造的数列 ——
&A^n=\sum_{i=0}^{k-1}c_iA^i\\
&A^n\times St=\sum_{i=0}^{k-1}c_iA^i\times St
\end{aligned}
\]
目前看来好像没有什么茄子用,仍然需要计算矩乘。但是我们真的需要 \(A^n\times St\) 这整个向量吗?实际上我们只需要 \(f_n\),即 \(A^n\times St\) 的第一项。
再看看这个式子就可以发现它的用处了:
\]
\(A^i\times St\) 的实际意义是将 \(St\) 转移 \(i\) 次。所以 \((A^i\times St)_1=f_i\),也即
\]
这样就免去了矩乘。
这就是这个算法的全部内容了?还剩下一个问题,\(\{c_i\}\) 怎么构造?
定义函数 \(C(x)\) 如下,则要求 \(C(A)=A^n\)。
\]
接下来是一些魔法……如果我们有函数 \(F(x)\) 满足
\]
且有 \(G(x)\) 满足:
\]
易得
\]
利用多项式取模对快速幂稍加改造就可以计算 \(C(x)\)。
「稍 加 改 造」
说起来倒也简单,把多项式 $x$ 拿来做快速幂,对 $F(x)$ 取模。
然后我们发现又需要构造 \(F(x)\)……如果要对一个一般的方阵求 \(F(A)=0\) 那确实很难,但常系数齐次线性递推的转移矩阵 \(A\) 因为它的结构特殊,有一个简洁的构造:
- \(f_k=1\);
- \(f_{i}=-c_{k-i}\)(\(0\le i\lt k\))。
至于为什么这样构造,就涉及到矩阵的特征向量的内容,和这个算法本身没有太紧的关联。有兴趣的读者可以参考 shadowice1984 的洛谷博客。
THE END
Thanks for reading!
我也曾 隐约想过 从这世界逃离
因为有无数次 和最优解失之交臂
那时耀眼的自己 定不会轻易容许
骄傲变得同墙角霉菌 不差毫厘
——《我也曾想过一了百了(中文填词)》 By 洛天依
> Link 我也曾想过一了百了 - Bilibili
最新文章
- html和js基础功能代码备份
- Dubbo系列(2)_RPC介绍
- 基于NodeJS的全栈式开发
- HBase介绍及简易安装(转)
- Objective-C 内存管理原则
- C++文件编程(文件流操作)
- Dockerfile 指令 VOLUME 介绍
- MySQL查看所有连接的客户端ip
- Python 递归锁
- ubuntu 环境 celery配置全解
- 多线程系列(2)线程池ThreadPool
- hadoop集群默认配置和常用配置
- Linux基础命令---yes
- SpringAOP-基于@AspectJ的简单入门
- UWP开发入门(八)——聊天窗口和ItemTemplateSelector
- Plan
- ROC曲线手画
- Spring管理事务默认回滚的异常
- Codeforces Beta Round #1 C. Ancient Berland Circus 计算几何
- 什么是jstack