题解 | 递推数列

当k不大时可以直接模拟，时间复杂度为O(k）：

#include<stdio.h>
#include<vector>
using namespace std;

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

当k很大时，直接模拟模拟容易超时，故采用快速幂，时间复杂度可降为O(logn）：

#include<stdio.h>
#include<vector>
using namespace std;

//二阶方阵相乘
void multi(int m1[2][2], int m2[2][2], int res[2][2]) {
    res[0][0] = m1[0][0] * m2[0][0] % 10000 + m1[0][1] * m2[1][0] % 10000;
    res[0][0] %= 10000;
    res[0][1] = m1[0][0] * m2[0][1] % 10000 + m1[0][1] * m2[1][1] % 10000;
    res[0][1] %= 10000;
    res[1][0] = m1[1][0] * m2[0][0] % 10000 + m1[1][1] * m2[1][0] % 10000;
    res[1][0] %= 10000;
    res[1][1] = m1[1][0] * m2[0][1] % 10000 + m1[1][1] * m2[1][1] % 10000;
    res[1][1] %= 10000;

}

//快速幂：求A（k-1）次方
void fastermi(int A[2][2], int k, int res[2][2]) {
    if (k == 0) {
        //单位矩阵
        res[0][0] = 1;
        res[0][1] = 0;
        res[1][0] = 0;
        res[1][1] = 1;
    } else if (k % 2 == 0) {
        int temp[2][2];
        fastermi(A, k / 2, temp);
        multi(temp, temp, res);

    } else {
        int temp1[2][2];
        int temp2[2][2];
        fastermi(A, k / 2, temp1);
        multi(temp1, temp1, temp2);
        multi(temp2, A, res);

    }
}
int main() {
    int a0, a1, p, q, k;
    scanf("%d%d%d%d%d", &a0, &a1, &p, &q, &k);
    int A[2][2] = { {p, q}, {1, 0} };
    int res[2][2];
    //算A（k-1）次方
    fastermi(A, k - 1, res);//C++数组传参 = 传地址
    printf("%d\n", (res[0][0] * a1 + res[0][1] * a0) % 10000);
    return 0;
}