题目链接：http://codeforces.com/problemset/problem/450/B
题意很好懂，矩阵快速幂模版题。
1 /* 2 | 1, -1 | | fn | 3 | 1, 0 | | fn-1 | 4 */ 5 #include <iostream> 6 #include <cstdio> 7 #include <cstring> 8 using namespace std; 9 typedef __int64 LL; 10 LL mod = 1e9 + 7; 11 struct data { 12 LL mat[3][3]; 13 }; 14 15 data operator* (data a , data b) { 16 data res; 17 for(int i = 1 ; i <= 2 ; i++) { 18 for(int j = 1 ; j <= 2 ; j++) { 19 res.mat[i][j] = 0; 20 for(int k = 1 ; k <= 2 ; k++) { 21 res.mat[i][j] = ((a.mat[i][k]*b.mat[k][j] % mod) + res.mat[i][j]) % mod; 22 } 23 } 24 } 25 return res; 26 } 27 28 data operator^ (data a , LL n) { 29 data res; 30 for(int i = 1 ; i <= 2 ; i++) { 31 for(int j = 1 ; j <= 2 ; j++) { 32 res.mat[i][j] = (i == j); 33 } 34 } 35 while(n) { 36 if(n & 1) 37 res = a * res; 38 a = a * a; 39 n >>= 1; 40 } 41 return res; 42 } 43 44 int main() 45 { 46 data res; 47 LL n; 48 cin >> res.mat[2][1] >> res.mat[1][1] >> n; 49 if(n == 1) { 50 cout << (res.mat[2][1] % mod + mod) % mod << endl; 51 } 52 else if(n == 2) { 53 cout << (res.mat[1][1] % mod + mod) % mod << endl; 54 } 55 else { 56 data a; 57 a.mat[2][1] = a.mat[1][1] = 1; 58 a.mat[2][2] = 0; 59 a.mat[1][2] = -1; 60 a = a ^ (n - 2); 61 res = a * res; 62 cout << (res.mat[1][1] % mod + mod) % mod << endl; 63 } 64 }