问题：递推数列【BAIDU】：给定a0,a1，以及an=p*a(n-1)+q*a(n-2)中的p,q。这里n>=2。求第k数对10000的模。[color=darkred]要求性能尽可能优化。[/color]

说明：所给出的程序的输入包括a0,a1,p,q,k，输出第k个数a(k)对10000的模。

答：初看这个题目，第一印象就是无非考考递归程序设计或者线性递推罢了。其实仔细想了想题目要求性能尽可能优化，简单地使用递归或者线性递推的设计显然不能达到要求，在实际编程中也验证了这一点，使用递归的设计方法的时候，当k增加到300左右程序就不动了，效率非常低，使用线性递推的时间复杂度可以达到O(n)，但是对于一个大k来说复杂度还是有优化的余地。思前想后，我觉得使用矩阵二分乘法来对付大k的情况还是可行的，下面算法，对超过1000的k值，利用前置矩阵计算的结果，可以大大减少计算的次数。算法的实现如下：


#include

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 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 ",a0%10000);
}else if(k==1){
printf("%ld ",a1%10000);
}else{
printf("%ld ",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);
}
}else{
printf("%ld ",(a0*m[t].a[0][1]+a1*m[t].a[1][1])%10000);
}
}

}
return 0;
}





运行结果：

[img]http://dl.iteye.com/upload/attachment/0062/1266/30ee6692-ca13-3e5d-a2e6-80a6525ac262.jpg[/img]