题解 | #递推数列#

直接进行迭代计算，实测用递归方式实现的话会造成超时。

#include<cstdio>
int main(){
    int a0, a1, a2, p, q, k;
    scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k);
    for(int i = 1; i < k; i++){
        a2 = a1 * p + a0 * q;        //类似斐波那契数列的迭代思想
        a2 %= 10000;
        a0 = a1;
        a1 = a2;
    }
    printf("%d\n",a2);
    return 0;
}

使用了矩阵的思想进行迭代

#include <iostream>
using namespace std;
struct matrix {
    int m[2][2];
};
matrix multiply(matrix a, matrix b) {//矩阵乘法
    matrix ans;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ans.m[i][j] = 0;
            for (int k = 0; k < 2; k++)
                ans.m[i][j] += (a.m[i][k] * b.m[k][j])%10000;//中间结果取模，否则不能通过测试
        }
    }
    return ans;
}
matrix fastPower(matrix a, int k) {//矩阵快速幂
    matrix ans;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (i == j) ans.m[i][j] = 1;
            else ans.m[i][j] = 0;
        }
    }
    while (k != 0) {
        if (k % 2 == 1) {
            ans = multiply(ans, a);
        }
        a = multiply(a, a);
        k /= 2;
    }
    return ans;
}
int main() {
    int a0, a1, p, q, k;
    while (cin >> a0 >> a1 >> p >> q >> k) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        matrix temp;
        temp.m[0][0] = p;
        temp.m[0][1] = q;
        temp.m[1][0] = 1;
        temp.m[1][1] = 0;
        temp = fastPower(temp, k - 1);
        int ak = ((temp.m[0][0] * a1) % 10000 + (temp.m[0][1] * a0) % 10000) % 10000;
        cout << ak  << endl;
    }
}