题解 | #递推数列#

//此题一看就大概知道有两种限制，递归的时间复杂度和整数的表示范围，由于an=p*a(n-1) + q*a(n-2)
//可知，an对10000取余的结果只由a(n-1),a(n-2)中不超过10000的部分决定，所以每次ai算完后对10000取余即可
#include "stdio.h"
using namespace std;
int a[10000]={0};

int main(){
    int a0,a1,p,q,k;
    scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k);
    a[0]=a0;
    a[1]=a1;
    for (int i = 2; i <= k; ++i) {
        a[i]=a[i-1]*p+a[i-2]*q;
        if(a[i]>10000)
            a[i]=a[i]%10000;
    }
    printf("%d",a[k]);
}