[LOJ10220]Fibonacci 第 n 项

题目

题目描述

大家都知道Fibonacci数列把,\(f_1=1,f_2=1,f_3=2,f_4=3,f_n=f_{n-1}+f_{n-2}\)
现在问题很简单,输入\(n\)和\(m\),求\(f_n mod m\)

输入格式

输入\(n,m\)

输出格式

输出\(f_n mod m\)

样例输入

样例输出

数据范围与提示

对于\(100\%\)的数据,\(1\le n \le 2\times 10^9,1\le m\le 10^9 + 10\)

题解

看到这个数据范围,就知道这肯定不能够一般地递推了。
于是我们要介绍一个工具来帮助我们计算这个数列——矩阵乘法
两个矩阵的乘法仅当第一个矩阵A的列数和第二个矩阵B的行数相等的时候才能定义
就举个例子好了


\(\begin{bmatrix}1&0&2\\ -1&3&1\end{bmatrix} \times \begin{bmatrix} 3&1 \\ 2&1\\ 1&0\end{bmatrix}=\begin{bmatrix}(1\times3+0\times2+2\times0)&(1\times1+0\times1+2\times0) \\ (-1\times3+3\times2+1\times1)&(-1\times1+3\times1+1\times0)\end{bmatrix}\)

那么我们根据这个性质,可以定义两个矩阵,一个是数值矩阵用来存贮递推时的数据,需要有一个初始值,还有一个是递推矩阵用来定义如何递推。
在这道里,我们可以初始化数值矩阵为:


\(\begin{bmatrix}f_2&0\\f_1&0\end{bmatrix}\)

而我们定义递推矩阵为:

\(\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

每次用数值矩阵乘递推矩阵,得到的新矩阵中,数列的下标正好是原来的下标+1,递推得以进行。(请读者自己动手体会一下,不然你永远只为停留在“哇,这个算法好神奇”这个层面)
而对于乘法的递推,我们很容易就想到快速幂,于是这道题就完美解决。
至于如何定义数值矩阵递推矩阵,我认为还是要多自己思考,多做几次就会了。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注