题目描述：

给定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

样例输出：

8359

1 #include 
       
         2 #include 
        
          3 #include 
         
           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)        *a014 */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     else50     { 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         else72             if (k == 1)73                 a = a1;74             else75            {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<
          
           <