lanqiaoOJ 1180：斐波那契数列 ← 矩阵快速幂

【题目来源】
https://www.lanqiao.cn/problems/1180/learning/

【题目描述】
定义斐波那契数列数列为 F1=1，F2=1，Fn=Fn-1+Fn-2，n＞2。
给定一个正整数 n，求 Fn 在模 10^9+7 的值。

【输入格式】
第1行为一个整数 T，表示测试数据数量。
接下来的 T 行每行包含一个正整数 N。
1≤T≤10^4，1≤N≤10^18。

【输出格式】
输出共 T 行，每行包含一个整数，表示答案。

【输入样例】
6
1
2
3
4
5
1000000000

【输出样例】
1
1
2
3
5
21

【算法分析】
本题（lanqiaoOJ 1180）与洛谷 P1962 的分析思路一样。

【算法代码】

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn=2;
const int MOD=1e9+7;
LL n;struct Matrix {LL m[maxn][maxn];Matrix() { //Constructor in structmemset(m,0,sizeof m);}
};Matrix mul(Matrix a, Matrix b) {Matrix ans;for(int i=0; i<2; i++)for(int j=0; j<2; j++)for(int k=0; k<2; k++)ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;return ans;
}void fastPow(LL n) {Matrix base,t;base.m[0][0]=1,base.m[0][1]=1;base.m[1][0]=1,base.m[1][1]=0;t.m[0][0]=1,t.m[0][1]=1; //f[2]=1,f[1]=1while(n) {if(n&1) t=mul(t,base);base=mul(base,base);n=n>>1;}cout<<t.m[0][0]<<endl;
}int main() {int T;cin>>T;while(T--) {cin>>n;if(n==1) cout<<"1"<<endl;else fastPow(n-2);}return 0;
}/*
in:
6
1
2
3
4
5
1000000000out:
1
1
2
3
5
21
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143227091
https://mp.weixin.qq.com/s/Az68VdFnRDUZ8vczKwRB4g
https://www.cnblogs.com/zxsoul/articles/14407155.html