205.斐波那契
205. 斐波那契 - AcWing题库 |
---|
难度:中等 |
时/空限制:1s / 64MB |
总通过数:3220 |
总尝试数:4747 |
来源: 《算法竞赛进阶指南》 |
算法标签 数学知识矩阵乘法快速幂 |
题目内容
在斐波那契数列中,
F i b 0 = 0 , F i b 1 = 1 , F i b n = F i b n − 1 + F i b n − 2 Fib_{0}=0,Fib_{1}=1,Fib_{n}=Fib_{n-1}+Fib_{n-2} Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2
(n>1)。
给定整数 n,求 F i b n Fib_{n} Fibn mod 10000。
输入格式
输入包含不超过 100 组测试用例。
每个测试用例占一行,包含一个整数 n。
当输入用例 n=−1 时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个整数表示结果。
每个结果占一行。
数据范围
0≤n≤2×10^9
输入样例:
0
9
999999999
1000000000
-1
输出样例:
0
34
626
6875
题目解析
怕溢出,求第n项模10000的结果,这样就不需要写高i精度
不超过100组数据
对于每一个n,求斐波那契数列第n项模10000的结果
数据范围是0~20亿
不能用递推的方法来做,计算量是2000亿
如何优化
斐波那契数列有通项公式
a n = 1 ÷ 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] a_{n}=1\div \sqrt{ 5 } [\left( \frac{1+\sqrt{ 5 }}{2} \right)^n-\left( \frac{1-\sqrt{ 5 }}{2} \right)^n ] an=1÷5[(21+5)n−(21−5)n]
但是这个式子不适合这道题,需要做高精度,而且还要把n项精确求出来,没办法求余数
用矩阵乘法快速幂的方式,容易取余数
如果可以把一道题目转换成矩阵的乘法来计算的话,就可以用快速幂来优化
先把递推的方法用一个矩阵表示出来
因为每一项都和前两项有关系,可以把 a n − 1 a_{n-1} an−1和 a n a_{n} an放到一个矩阵中,是一个1x2的矩阵
乘以一个2x2的矩阵,就可以得到一个新的1x2的矩阵
新的1x2的矩阵就是每一项往后递推, a n a_{n} an和 a n + 1 a_{n+1} an+1
如何构造矩阵,从定义来看
根据矩阵乘法规则
[ a n − 1 a n ] × [ 01 11 ] = [ a n a n + 1 ] \begin{bmatrix}{} a_{n-1} \qquad an \end{bmatrix} \times \begin{bmatrix}{} 0 1 \\ 11 \end{bmatrix}= \begin{bmatrix}{} a_{n} \qquad a_{n+1} \end{bmatrix} [an−1an]×[0111]=[anan+1]
把矩阵第一个元素的下标当作矩阵的下标
A n = A n − 1 × F A_{n}=A_{n-1} \times F An=An−1×F
同理
A n = A n − 2 × F × F A_{n}=A_{n-2} \times F \times F An=An−2×F×F
… \dots …
A n = A 0 × F ⋯ × F A_{n}=A_{0} \times F\dots \times F An=A0×F⋯×F
矩阵乘法有结合律
A n = A 0 × F n A_{n}=A_{0} \times F^n An=A0×Fn
= [ 0 , 1 ] × [ 01 11 ] n =\begin{bmatrix}{} 0,1 \end{bmatrix} \times \begin{bmatrix}{} 0 1 \\ 11 \end{bmatrix}^n =[0,1]×[0111]n
求矩阵的n次方,可以类似用整数的快速幂来求
快速幂能用的前提是具有结合律
快速幂求法,时间复杂度是 O ( log n ) O(\log n) O(logn)
矩阵乘法,复杂度再乘8
总共2万4的计算量,能过
如果用C++实现矩阵乘法的话,需要存1x2的数组和2x2的数组,还需要写两个函数,比较麻烦
如何只写一个函数
把1x2的矩阵扩充一下,下面加两个0,结果还是不变的
代码
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int MOD = 10000;void mul(int a[][2], int b[][2])
{//先定义一下结果数组int c[2][2] = {0};for (int i = 0; i < 2; i ++)for (int j = 0; j < 2; j ++)for (int k = 0; k < 2; k ++)c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;memcpy (a, c, sizeof c);//把c数组赋值到a上
}int fib(int n)
{int a[2][2] = {0, 1, 0, 0};int f[2][2] = {0, 1, 1, 1};//快速幂while (n){//如果n是奇数的话if (n & 1) mul(a, f);mul(f, f);n >>= 1;}return a[0][0];
}int main()
{int n;//逗号表达式,值等于最后一个表达式的值,这两个式子的值其实就是n!=-1while (cin >> n, n != -1)cout << fib(n) << endl;return 0;
}