题目1081：递推数列

题目描述：: 给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。求第k个数对10000的模。

输入：: 输入包括5个整数：a0、a1、p、q、k。

输出：: 第k个数a(k)对10000的模。

样例输入：

20 1 1 14 5

样例输出：

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4  
 5  
 6 using namespace std;
 7  
 8 const int  MOD = 10000;
 9  
10  
11 /*
12 A(k)     = (p q)^(k-1)  *a1  
13 A(k-1)   = (1 0)        *a0
14 */
15  
16  
17 inline void MatrixMul( int m[][2], int n[][2] ) 
18 {
19     int s[2][2];
20     memset(s,0,sizeof(s));
21  
22     int i;
23     int j;
24     int k;
25  
26     for(i = 0; i < 2; i++)
27         for(j = 0; j < 2; j++)
28             for( k = 0; k < 2; k++)
29                 s[i][j] += m[i][k]*n[k][j];
30  
31     for(i = 0; i < 2; i++)
32         for(j = 0; j < 2; j++)
33             m[i][j] = s[i][j]%MOD;
34  
35 }
36  
37  
38 void MatrixN ( int m[][2], int n )
39 {
40     int t[2][2]={{m[0][0],m[0][1]},{m[1][0],m[1][1]}};
41  
42     if (n == 1) 
43         return;
44     else if ( n%2 == 0) 
45     { 
46         MatrixN(m,n/2); 
47         MatrixMul(m,m); 
48     }
49     else
50     { 
51         MatrixN(m,n-1); 
52         MatrixMul(m,t);
53     }
54 }
55  
56 int main(void)
57 {
58     int a;
59     int a0;
60     int a1;
61     int p;
62     int q;
63     int k;
64  
65     int m[2][2];
66  
67     while (cin >> a0 >>a1 >> p >> q >> k )
68     {
69         if (k == 0) 
70             a = a0;
71         else
72             if (k == 1)
73                 a = a1;
74             else
75            {
76                 m[0][0] = p%MOD; 
77                 m[0][1] = q%MOD;
78                 m[1][0] = 1; 
79                 m[1][1] = 0;
80  
81                 MatrixN(m,k-1);
82  
83                 a = m[0][0] * a1 + m[0][1] * a0;
84            }
85         cout<<a%MOD<<endl;
86     }
87     return 0;
88 }