【题目链接】click here~~
【题目大意】
Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate fn modulo1000000007(109+7).
【解题思路】时使用矩阵快速幂即可,得#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <math.h>using namespace std;const long long MOD=1e9+7;#define LL long longstruct Matrlc{long long mapp[2][2];} ans,base;Matrlc unit={1,0,0,1};Matrlc mult(Matrlc a,Matrlc b){Matrlc c;for(int i=0; i<2; i++)for(int j=0; j<2; j++){c.mapp[i][j]=0;for(int k=0; k<2; k++)c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%MOD;c.mapp[i][j]%=MOD;}return c;}void pow1(LL n){base.mapp[0][0] =1;base.mapp[0][1] = -1;base.mapp[1][0] = 1;base.mapp[1][1] = 0;ans.mapp[0][0] = ans.mapp[1][1] = 1;// ans 初始化为单位矩阵ans.mapp[0][1] = ans.mapp[1][0] = 0;while(n){if(n&1) ans=mult(ans,base);base=mult(base,base);n>>=1;}}int main(){LL X,Y,N,i,j;scanf("%lld%lld%lld",&X,&Y,&N);if(N==1) printf("%lld\n",(X%MOD+MOD)%MOD);else if(N==2) printf("%lld\n",(Y%MOD+MOD)%MOD);else{pow1(N-2);LL result=(((ans.mapp[0][0]*Y+ans.mapp[0][1]*X)%MOD)+MOD)%MOD;printf("%lld\n",result);}return 0;}
，片的时光如浮云般流过，我们的青春单薄的穿梭在蓝天之上。
