题解 | 递推数列

因为运算次数可能比较多，使用递归函数可能会导致栈溢出进而促成超时，故而还是使用一个数组作为存储递归值的单位从而降低耗时。本题直接将递归规律写出，所以并不难。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS

int main()
{
    int a0, a1, p, q, k;
    std::cin >> a0 >> a1 >> p >> q >> k;
    std::vector<int> a(k + 1);
    a[0] = a0 % 10000;
    a[1] = a1 % 10000;
    for (int i = 2; i < k + 1; i++)
    {
        a[i] = p * a[i - 1] % 10000 + q * a[i - 2] % 10000;
        a[i] %= 10000;
    }
    std::cout << a.back() << std::endl;
    return 0;
}