互联网公司面试题之十一

问题：递推数列【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=2
		m[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=3
		t=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=4
		t=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=5
		t=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=6
		t=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;
}

运行结果：