递推数列

题目链接：https://www.nowcoder.com/practice/d0e751eac618463bb6ac447369e4aa25?tpId=40&tqId=21352&tPage=1&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking

题目描述

给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。求第k个数对10000的模。

输入描述:

输入包括5个整数：a0、a1、p、q、k。

输出描述:

第k个数a(k)对10000的模。

示例1

输入

20 1 1 14 5

输出

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <stack>
 7 using namespace std;
 8 const int mod=10000;
 9 int a[10010];
10 int p,q,k;
11 void init()
12 {
13     for(int i=2;i<10010;i++){
14         a[i]=p*a[i-1]+q*a[i-2];
15         a[i]%=mod;
16     }
17 }
18 int main()
19 {
20     while(cin>>a[0]>>a[1]>>p>>q>>k){
21         init();
22         cout<<a[k]<<endl;
23     }
24     return 0;
25 }