【Codeforces】450 B(div2)

题目链接：http://codeforces.com/problemset/problem/450/B

题意：

求这个的第n项。

题解：$f_{i+1} = f_i - f_{i-1} $

egin{pmatrix} 1 & 1\ -1 & 0 end{pmatrix} *

egin{pmatrix} f(n)& f(n-1) end{pmatrix} =

egin{pmatrix} f(n) - f(n-1) & f(n) end{pmatrix}=

egin{pmatrix} f(n+1) & f(n) end{pmatrix}

代入前两项即可。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define ll long long
 6 const int maxn = 3;
 7 const ll mod = 1e9+7;
 8 
 9 ll n,p;
10 
11 struct Matrix{
12     ll a[maxn][maxn];
13     void init(){ 
14         memset(a, 0, sizeof(a));
15         for(int i = 1; i <= maxn;i++){
16             a[i][i] = 1;
17         }
18     }
19 };
20 
21 //矩阵乘法 
22 Matrix mul(Matrix a, Matrix b){
23     Matrix ans;
24     for(int i = 1;i <= 2;++i){
25         for(int j = 1;j <= 2;++j){
26             ans.a[i][j] = 0;
27             for(int k = 1;k <= 2;++k){
28                 ans.a[i][j] = ans.a[i][j] % mod + a.a[i][k] * b.a[k][j] % mod;
29                 ans.a[i][j] %= mod;
30             }
31         }
32     } 
33     return ans;
34 }
35 
36 //矩阵快速幂 
37 Matrix qpow(Matrix a,ll b){
38     Matrix ans;
39     ans.init();
40     while(b){
41         if(b & 1)
42             ans = mul(ans,a);
43         a = mul(a,a);
44         b >>= 1;
45     }
46     return ans;
47 }
48 
49 void print(Matrix a){
50     for(int i = 1; i <= n;++i){
51         for(int j = 1;j <= n;++j){
52             cout << a.a[i][j]%mod<< " ";
53         }
54         cout << endl;
55     }
56 }
57 
58 int main(){
59     Matrix base;
60     Matrix ans;
61     int x,y,n;
62     cin>>x>>y>>n;
63     if(n == 1){
64         cout<<(mod + x) % mod<<endl;
65         return 0;
66     }
67     if( n == 2){
68         cout<<(mod + y) % mod<<endl;
69         return 0;
70     }
71 
72     ans.a[1][1] = y;ans.a[1][2] = x;
73     base.a[1][1] = 1;base.a[1][2] = 1;
74     base.a[2][1] = -1;base.a[2][2] = 0;
75     
76     ans = mul(ans,qpow(base,n-2));
77     ll res = (mod + ans.a[1][1]) % mod;
78     cout<<res<<endl;
79     return 0;
80 }