题解 | #递推数列#

直接用递归生成会导致A(n-1)和A(n)进行两次独立计算从而超时

借鉴动态规划中的缓存数组，让每个结果只算一次

#include<iostream>

using namespace std;
int An(int a0,int a1,int p,int q,int n){
	int* A = (int*)malloc(sizeof(int)*(n+1));//还有A0
	A[0] = a0;
	A[1] = a1;
	for(int i=2;i<=n;i++){
		A[i] = (p*A[i-1]%10000+q*A[i-2]%10000)%10000;
	}
	return A[n];
}	
int main(){//习题6.11  清华大学  递推数列
	 
    int a0,a1,p,q,k;
    while(cin>>a0>>a1>>p>>q>>k){
        cout<<An(a0,a1,p,q,k)<<endl;
    }
    
    return 0;
}