SSOJ2922Fibonacci第n项
3294+
作者:crxis 发布:2020-12-25 分类:矩阵
题目大意:求Fibonacci数列第n项,n很大,结果很大,输出模m的结果。
题目描述
大家都知道 Fibonacci 数列吧,f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。
现在问题很简单,输入 n和 m,求 fn mod m 。
输入格式
输入 n,m。
输出格式
输出 fn mod m。
样例
5 1000
5
数据范围与提示
对于 100%的数据, 1≤n≤2×109,1≤m≤109+10。
解题思路
斐波拉契数列:1、1、2、3、5、8……从第三项开始等于前两项之和。
定义矩阵:
a b
0 0
如何得到矩阵:
b a+b
0 0
只需要乘以矩阵:
0 1
1 1
乘1次,就矩阵左上角就第2项目,乘n-1次,矩阵左上角就是第n项。