题目链接
Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate fn modulo 1000000007 (10^9?+?7).
Input
The first line contains two integers x and y (|x|,?|y|?≤?10^9). The second line contains a single integer n (1?≤?n?≤?2*10^9).
Output
Output a single integer representing fn modulo 1000000007 (10^9?+?7).
Examples
Input
2 3
3
Output
1
Input
0 -1
2
Output
1000000006
Note
In the first sample, f2?=?f1?+?f3, 3?=?2?+?f3, f3?=?1.
In the second sample, f2?=??-?1; ?-?1 modulo (10^9?+?7) equals (10^9?+?6).
AC代码:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct matrix{
long long int mat[3][3];
}A,B;
long long int mod(long long int n){
if(n > 0)return n % 1000000007;else if(n < 0)return (n + 1000000007) % 1000000007;else return 0;
}
matrix mul(matrix a,matrix b){
matrix tmp;memset(tmp.mat,0,sizeof(tmp.mat));for(int i = 0;i < 3;i++)for(int j = 0;j < 3;j++)for(int k = 0;k < 3;k++){
tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j];tmp.mat[i][j] = mod(tmp.mat[i][j]);} return tmp;
}
matrix pow_mat(matrix a,int n){
matrix ans;memset(ans.mat,0,sizeof(ans.mat));for(int i = 0;i < 3;i++)ans.mat[i][i] = 1;while(n){
if(n & 1)ans = mul(ans,a);a = mul(a,a);n >>= 1;}return ans;
}
int main(){
long long int x,y,n;scanf("%lld%lld%lld",&x,&y,&n);if(n == 1)printf("%lld\n",mod(x)); else if(n == 2)printf("%lld\n",mod(y));else if(n == 3)printf("%lld\n",mod(y - x + 1000000007));else{
A.mat[0][0] = x,A.mat[0][1] = y,A.mat[0][2] = y - x;B.mat[0][0] = 0,B.mat[0][1] = 0,B.mat[0][2] = 0;B.mat[1][0] = 1,B.mat[1][1] = 0,B.mat[1][2] = -1;B.mat[2][0] = 0,B.mat[2][1] = 1,B.mat[2][2] = 1;B = pow_mat(B,n - 3); printf("%lld\n",mod(mul(A,B).mat[0][2]));} return 0;
}