互联网公司面试题之十一
问题：递推数列【BAIDU】：给定a0,a1，以及an=p*a(n-1)+q*a(n-2)中的p,q。这里n>=2。求第k数对10000的模。要求性能尽可能优化。
说明：所给出的程序的输入包括a0,a1,p,q,k，输出第k个数a(k)对10000的模。
答：初看这个题目，第一印象就是无非考考递归程序设计或者线性递推罢了。其实仔细想了想题目要求性能尽可能优化，简单地使用递归或者线性递推的设计显然不能达到要求，在实际编程中也验证了这一点，使用递归的设计方法的时候，当k增加到300左右程序就不动了，效率非常低，使用线性递推的时间复杂度可以达到O(n)，但是对于一个大k来说复杂度还是有优化的余地。思前想后，我觉得使用矩阵二分乘法来对付大k的情况还是可行的，下面算法，对超过1000的k值，利用前置矩阵计算的结果，可以大大减少计算的次数。算法的实现如下：
#include <stdio.h>typedef struct matrix{int k;long a[2][2];}Matrix;int main(){long q,p,a0,a1;int i,s,t,k;Matrix m[30];for(;scanf("%ld%ld%ld%ld%d",&a0,&a1,&p,&q,&k)!=EOF;){t=0;//For k=2m[0].k=1;m[0].a[0][0]=0;m[0].a[0][1]=q%10000;m[0].a[1][0]=1;m[0].a[1][1]=p%10000;if(k-1<=m[0].k) goto CALC;//For k=3t=1;m[1].k=2;m[1].a[0][0]=m[0].a[0][1];m[1].a[0][1]=(q*p)%10000;m[1].a[1][0]=m[0].a[1][1];m[1].a[1][1]=(q+p*p)%10000;if(k-1==m[1].k) goto CALC;//For k=4t=2;m[2].k=3;m[2].a[0][0]=m[1].a[0][1];m[2].a[0][1]=(q*q+q*p*p)%10000;m[2].a[1][0]=m[1].a[1][1];m[2].a[1][1]=(2*q*p+p*p*p)%10000;if(k-1==m[2].k) goto CALC;//For k=5t=3;m[3].k=4;m[3].a[0][0]=m[2].a[0][1];m[3].a[0][1]=(2*q*q*p+q*p*p*p)%10000;m[3].a[1][0]=m[2].a[1][1];m[3].a[1][1]=(q*q+3*q*p*p+p*p*p*p)%10000;if(k-1==m[3].k) goto CALC;//For k=6t=4;m[4].k=5;m[4].a[0][0]=m[3].a[0][1];m[4].a[0][1]=(q*q*q+3*q*q*p*p+q*p*p*p*p)%10000;m[4].a[1][0]=m[3].a[1][1];m[4].a[1][1]=(3*q*q*p+q*p*p*p+3*q*p*p+p*p*p*p*p)%10000;if(k-1==m[4].k) goto CALC;t=4;s=5;if(k-1>=10){for(;m[t].k+s<k;++t){m[t+1].k=m[t].k+s; //大k加速m[t+1].a[0][0]=(m[t].a[0][0]*m[t].a[0][0]+m[t].a[0][1]*m[t].a[1][0])%10000;m[t+1].a[0][1]=(m[t].a[0][0]*m[t].a[0][1]+m[t].a[0][1]*m[t].a[1][1])%10000;m[t+1].a[1][0]=(m[t].a[1][0]*m[t].a[0][0]+m[t].a[1][1]*m[t].a[1][0])%10000;m[t+1].a[1][1]=(m[t].a[1][0]*m[t].a[0][1]+m[t].a[1][1]*m[t].a[1][1])%10000;s+=s;}}for(;k!=m[t].k+1;){i=t;while(m[t].k+m[i].k>k-1 && i>0) --i;m[t+1].k=m[t].k+m[i].k;m[t+1].a[0][0]=(m[t].a[0][0]*m[i].a[0][0]+m[t].a[0][1]*m[i].a[1][0])%10000;m[t+1].a[0][1]=(m[t].a[0][0]*m[i].a[0][1]+m[t].a[0][1]*m[i].a[1][1])%10000;m[t+1].a[1][0]=(m[t].a[1][0]*m[i].a[0][0]+m[t].a[1][1]*m[i].a[1][0])%10000;m[t+1].a[1][1]=(m[t].a[1][0]*m[i].a[0][1]+m[t].a[1][1]*m[i].a[1][1])%10000; ++t;}CALC:{if(t==0) {if(k==0){printf("%ld\n",a0%10000);}else if(k==1){printf("%ld\n",a1%10000);}else{printf("%ld\n",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);}}else{printf("%ld\n",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);}}}return 0;}