[9度OJ 1081]递推数列 （矩阵二分乘法的运用）

[九度OJ 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

样例输出：

8359

来源：

2009年清华大学计算机研究生机试真题

--------------------------------------------------

本题最直观的方法是根据公式一步一步求出ａ(ｋ)，如下

 实现１

                      （1）
                      （2）

上面两个公式列出来，应该就会有所启发，会发现矩阵和乘法和数列递推公式之间的关系，那么，转化为矩阵之后有什么好处呢？我们要求一个数列的第n项，如果知道这个数列的通项公式就好了，可是这个递推公式的通项公式却不好求。转化为矩阵运算后，就可以很容易写出a(k),a(k-1)和a(0),a(1)之间的关系：
                 （3）
这里出现了矩阵M的(k-1)次幂，这对我们是一个启发，这时候就可以用二分法进行计算，我对二分法举一个例子：
M^5 = M*M*M*M*M; (5次乘法)
M^5 = ((M^2)^2)*M; (3次乘法)
第二种乘法运算就使用了二分法减少了乘法运算的次数。这样计算M^n算法时间复杂度可以从O(n)降低到O(lgn)，这正好符合前面提出的目标。
相应的实现如下：
#include <stdio.h>#define MOD 10000 // m = m * nvoid MatrixMul ( int m[2][2], int n[2][2] ){    int s[2][2]={{0,0},{0,0}};    int i, j, k;    for(i=0;i<2;i++)    for(j=0;j<2;j++)    for(k=0;k<2;k++)s[i][j]+=m[i][k]*n[k][j];    for(i=0;i<2;i++)    for(j=0;j<2;j++)m[i][j]=s[i][j]%MOD;}// m = m^nvoid MatrixN ( int m[2][2], int n ){    int t[2][2]={{m[0][0],m[0][1]},{m[1][0],m[1][1]}};    if (n==1) return;    else if (n%2==0)     { MatrixN(m,n/2); MatrixMul(m,m);     }    else     { MatrixN(m,n-1); MatrixMul(m,t);    }} int main(void){    int a,a0,a1,p,q,k;    int m[2][2];     while (scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k) != EOF)    {    if (k==0) a = a0;    else if (k==1) a = a1;    else    {        m[0][0] = p%MOD; m[0][1] = q%MOD;        m[1][0] = 1; m[1][1] = 0;MatrixN(m,k-1);a = m[0][0]*a1+m[0][1]*a0;    }    printf ("%d\n", a%MOD);    }    return 0;}

实现很简单，和上面的公式是对应的，就不多说了，从这里我们也可以看出数学工具对思维的巨大帮助，有了矩阵这一工具，可以很大程度上减少思维上的困难，其实用矩阵也是作乘法加法运算，但是如果不使用矩阵，就不容易想像到这样的计算过程。当初学习线性代数的时候，并没有意识到矩阵的妙用，所以需要使用时也不会用。这给我提了一个醒，学习理论，一定要搞明白这种理论有什么用处，不然不算学明白了。而遇到实际的问题想不出来时，一定需要及时补充理论知识。
另外，这里有一篇文章讲了一些矩阵乘法的知识和实现，对我有一定帮助：http://mindlee.net/2011/11/21/matrix-multiply/
（全文完，转载请注明出处：http://blog.csdn.net/on_1y/article/details/7901353）