原题链接：Jzzhu and Sequences
题意：
给你一个线性递推式 \(f_i = f_{i-1}+f_{i+1} \Rightarrow f_{i+1} = f_i-f_{i-1} \Rightarrow f_{i} = f_{i-1}- f_{i-2}\) , \(f_1= x\space ,\space f_{2}=y\)。求 \(f_n\space \% \space10^9+7\)
思路：
对于这个关系式我们就可以利用矩阵快速幂来求解
code:
#include <bits/stdc++.h> #define ll long long using namespace std; const int MOD = 1e9+7; //矩阵快速幂 void mat_mult(ll a[2][2],ll b[2][2]){ ll c[2][2]; memset(c,0,sizeof(c)); for(int k = 0;k<2;k++){ for(int i = 0;i<2;i++){ for(int j=0;j<2;j++){ c[i][j] = (c[i][j]%MOD + a[i][k]*b[k][j]%MOD)%MOD; } } } memcpy(a,c,sizeof(c)); } ll s[2][2] = {1,0,0,1};//对角矩阵初始化 void mat_pow(int t){ ll x[2][2] = {0,1,-1,1}; while(t){ if(t&1){ mat_mult(s,x); } mat_mult(x,x); t >>= 1; } } int main(){ int a,b; cin>>a>>b; int t; cin>>t; if(t==1) cout<<(a+MOD)%MOD<<endl; else{ mat_pow(t-2); ll ans = ((a * s[1][0] % MOD+ b * s[1][1] % MOD) % MOD + MOD) % MOD; printf("%lld\n",ans); } }转载于:https://www.cnblogs.com/Tianwell/p/11385025.html
