Jzzhu and Sequences
Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate fn modulo 1000000007 (109 + 7).
Input
The first line contains two integers x and y(|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).
Output
Output a single integer representing fn modulo 1000000007 (109 + 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 (109 + 7)equals (109 + 6).
解题思路：
本题给出一个运算公式 f( i ) = f( i - 1) + f(i + 1)给出两个整数分别为前两项的值，之后给出一个整数n，要求求出第n项的值。
我们首先将公式变形一下
f( i ) = f( i - 1 ) + f( i + 1 ) ⇔ f( i + 1 ) = f( i ) - f( i - 1 ) ⇔ f( i ) = f( i - 1 ) - f( i - 2 )
之后我们将相邻两项计入一个2 * 1的矩阵中
n大于3时计算n - 2次方即可得出答案
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod = 1e9+7; 5 const int maxn = 2; 6 struct matrix{ 7 LL mat[maxn][maxn]; //mat存放矩阵 8 matrix operator *(const matrix &a)const{ //重载运算符* 9 matrix ans; 10 for(int i = 0; i < 2; i++){ //遍历行 11 for(int j = 0; j < 2; j++){ //遍历列 12 ans.mat[i][j] = 0; 13 for(int k =0; k < 2; k++){ //固定k进行矩阵乘法 14 ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * a.mat[k][j] % mod) % mod; 15 } 16 } 17 } 18 return ans; 19 } 20 }; 21 matrix power(matrix a, LL b){ //矩阵快速幂，与普通快速幂几乎没有区别 22 matrix ans; //答案矩阵 23 memset(ans.mat, 0, sizeof(ans.mat)); 24 for(int i = 0; i < 2; i++){ 25 ans.mat[i][i] = 1; 26 } 27 //以上为初始化单位矩阵 28 while(b){ 29 if(b & 1){ //b按位与1匹配 30 ans = ans * a; 31 } 32 b >>= 1; 33 a = a * a; 34 } 35 return ans; 36 } 37 int main() 38 { 39 LL x ,y, n; 40 41 while(scanf("%lld%lld", &x, &y) != EOF){ //输入x与y 42 matrix a; 43 scanf("%lld", &n); //输入n 44 a.mat[0][0] = 1; 45 a.mat[0][1] = -1; 46 a.mat[1][0] = 1; 47 a.mat[1][1] = 0; 48 //初始化矩阵 49 //n为1或2单独判断 50 if(n == 1){ 51 printf("%lldn", (x % mod + mod) % mod); 52 }else if(n == 2){ 53 printf("%lldn", (y % mod + mod) % mod); 54 }else{ //n>=3 55 a = power(a, n - 2); //计算矩阵a的n - 2次方 56 LL ans = (((a.mat[0][0] * y + a.mat[0][1] * x) % mod) + mod ) % mod; 57 58 printf("%lldn", ans); 59 } 60 } 61 return 0; 62 }
[FnFn−1]=[Fn−1+Fn−2Fn−1]=[Fn−1×1+Fn−2×1Fn−1×1+Fn−2×0]=[1110]×[Fn−1Fn−2]=[1110]n−1×[F1F0]=[1110]n−1×[10]
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
