矩阵快速幂 -- 斐波那契数列
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int N; struct Matrix{ long long m[2][2]; }; Matrix Mul(Matrix A, Matrix B) { Matrix ret; for(int i = 0; i < 2; i ++) { for(int j = 0; j < 2; j ++) { ret.m[i][j] = 0; for(int k = 0; k <2; k ++) ret.m[i][j] += A.m[i][k] * B.m[k][j] % mod; } } return ret; } Matrix Pow(Matrix A, long long N) { Matrix ret; ret.m[0][0] = 1; ret.m[0][1] = 0; ret.m[1][0] = 0; ret.m[1][1] = 1; while(N) { if(N & 1) ret = Mul(ret, A); A = Mul(A, A); N /= 2; } return ret; } int main() { scanf("%d", &N); Matrix ans, A; ans.m[0][0] = 1; ans.m[0][1] = 0; A.m[0][0] = 1; A.m[0][1] = 1; A.m[1][0] = 1; A.m[1][1] = 0; ans = Mul(ans, Pow(A, N - 1)); printf("%lld ", ans.m[0][0]); return 0; }