SSOJ2922Fibonacci第n项
3399+
作者：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项。
程序实现
